# US 2012/0254251 A1 · SYSTEMS AND METHODS FOR EFFICIENT TOP-k APPROXIMATE SUBTREE MATCHING

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254251 A1
- Document ID: US20120254251A1
- Status: Published application
- Kind: A1
- Application number: 13/411,494
- Filed: 2012-03-02
- Published: 2012-10-04
- Earliest claimed: 2011-03-03
- Assignees: The Governors of the University of Alberta
- Inventors: Denilson Barbosa; Nikolaus Augsten; Michael Böhlen; Themis Palpanas
- Web page: https://patentgrep.com/patent/US20120254251A1

## CPC

- G06F 16/30: of unstructured textual data (document management systems G06F16/93)
- G06F 16/8373: {Query execution}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Systems and method for searching for approximate matches in a database of documents represented by a tree structure. A fast solution to the Top-k Approximate Subtree Matching Problem involves determining candidate subtrees which will be considered as possible matches to a query also represented by a tree structure. Once these candidate subtrees are found, a tree edit distance between each candidate subtree and the query tree is calculated. The results are then sorted to find those with the lowest tree edit distance.

## Claims

### Claim 1

A method for sorting nodes in a document tree to determine a number of closest approximations to a query represented by a query tree, the method comprising:
a) determining a limit size of subtrees of said document tree to be considered;
b) determining candidate subtrees of said document tree, each candidate subtree of said document tree having a size equal to or less than said limit size and each candidate subtree is not a subtree of another subtree having a size less than or equal to said limit size;
c) for each candidate subtree, determining a tree edit distance between said candidate subtree and said query tree;
d) sorting candidate subtrees in accordance with their respective tree edit distances with said query tree, in order to determine which candidate subtrees have least tree edit distances with said query tree;
wherein said tree edit distance is a cost to convert contents of one subtree into contents of a second subtree.

### Claim 2 (depends on 1)

A method according to claim 1 wherein said candidate subtrees are stored in a memory buffer.

### Claim 3 (depends on 1)

A method according to claim 1 wherein subtrees of candidate subtrees are removed from consideration as candidate subtrees.

### Claim 4 (depends on 2)

A method according to claim 2 wherein said memory buffer is a ring buffer.

### Claim 5 (depends on 2)

A method according to claim 2 wherein a number of nodes which can be stored in said memory buffer is equal to or less than said limit size.

### Claim 6 (depends on 1)

A method according to claim 1 wherein said nodes are processed in an order such that the root node of said document tree is processed last.

### Claim 7 (depends on 1)

A method according to claim 1 wherein only candidate subtrees which exist in the document tree are processed for step c).

### Claim 8

Computer-readable media having encoded thereon computer readable and computer executable instructions which, when executed, executes a method for sorting nodes in a document tree to determine a number of closest approximations to a query represented by a query tree, the method comprising:
a) determining a limit size of subtrees of said document tree to be considered;
b) determining candidate subtrees of said document tree, each candidate subtree of said document tree having a size equal to or less than said limit size and each candidate subtree is not a subtree of another subtree having a size less than or equal to said limit size;
c) for each candidate subtree, determining a tree edit distance between said candidate subtree and said query tree;
d) sorting candidate subtrees in accordance with their respective tree edit distances with said query tree, in order to determine which candidate subtrees have least tree edit distances with said query tree;
wherein said tree edit distance is a cost to convert contents of one subtree into contents of a second subtree.

### Claim 9 (depends on 8)

Computer-readable media according to claim 8 wherein said candidate subtrees are stored in a memory buffer.

### Claim 10 (depends on 8)

Computer-readable media according to claim 8 wherein subtrees of candidate subtrees are removed from consideration as candidate subtrees.

### Claim 11 (depends on 9)

Computer-readable media according to claim 9 wherein said memory buffer is a ring buffer.

### Claim 12 (depends on 9)

Computer-readable media according to claim 9 wherein a number of nodes which can be stored in said memory buffer is equal to or less than said limit size.

### Claim 13 (depends on 8)

Computer-readable media according to claim 8 wherein said nodes are processed in an order such that the root node of said document tree is processed last.

### Claim 14 (depends on 8)

Computer-readable media according to claim 8 wherein only candidate subtrees which exist in the document tree are processed for step c).

### Claim 15

A method for determining which subtrees in a document tree most closely approximate a given query tree, the method comprising:
a) determining a limit size of subtrees of said document tree to be considered;
b) determining candidate subtrees of said document tree, each candidate subtree of said document tree being, at most, equal in size to said limit size;
c) for each candidate subtree, determining a cost to convert contents of said candidate subtree into contents of said query tree;
d) sorting candidate subtrees in accordance with costs for converting said candidate subtrees into said query tree,
e) determining which candidate subtrees have lowest costs for converting said candidate subtrees into said query tree, candidate subtrees having lowest costs for being converted into said query tree being subtrees which most closely approximate said query tree.

### Claim 16 (depends on 15)

A method according to claim 15 wherein subtrees which are a subtree of another subtree having a size which is, at most, equal to said limit size are excluded from being a candidate subtree.

### Claim 17 (depends on 15)

A method according to claim 15 further comprising the step of determining which candidate subtrees exist in said document tree.

### Claim 18 (depends on 17)

A method according to claim 17 wherein candidate subtrees which do not exist in said document tree are not processed according to step c).

### Claim 19 (depends on 15)

A method according to claim 15 wherein candidate subtrees are stored in a ring buffer.

### Claim 20 (depends on 19)

A method according to claim 19 wherein unsuitable candidate subtrees are pruned from said buffer.
