System, method and technique for searching structured databases
First Claim
1. A method of searching a database comprising a plurality of records for at least one said record that at least approximately matches a search request, wherein data values in each of the records are organized in at least one field, the method including:
- creating a first tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of a field of said database record, wherein leaf child nodes of the first tree data structure include a link to another tree data structure;
creating at least one further tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of said database record, wherein leaf child nodes of the further tree data structure include a link to said database record;
traversing the first tree data structure to find at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path;
traversing at least one of the further tree data structures identified by the link of the leaf node of at least one said path, the traversal of the at least one further tree data structure finding at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path; and
outputting data relating to said database record identified by the link of the leaf child node of the paths with the best scores;
wherein the traversing of said tree data structure includes a node determination process, the node determination process including;
checking the data content of a node of the tree data structure, andif the node contains data identifying another tree data structure, or group of nodes, then performing the traversal on that other tree data structure, orif the node does not contain data identifying another tree data structure then, for each child node of that node, computing a score based on a match between the search request and the match data associated with the child node.
5 Assignments
0 Petitions
Accused Products
Abstract
Searching a database involves creating an access structure including a first tree data structure having a root node and at least one child node. Each child node is associated with match data corresponding to a data value of a field of a database record. Leaf child nodes of the first tree data structure include a link to another tree data structure in the access structure. Leaf child nodes of a further tree data structure include a link to a database record. The tree structures are traversed and scores are computed for the paths traversed that reflect the level of matching between the match pattern data of the nodes in a path and a search request to identify a database record that best matches the request.
-
Citations
17 Claims
-
1. A method of searching a database comprising a plurality of records for at least one said record that at least approximately matches a search request, wherein data values in each of the records are organized in at least one field, the method including:
-
creating a first tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of a field of said database record, wherein leaf child nodes of the first tree data structure include a link to another tree data structure; creating at least one further tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of said database record, wherein leaf child nodes of the further tree data structure include a link to said database record; traversing the first tree data structure to find at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path; traversing at least one of the further tree data structures identified by the link of the leaf node of at least one said path, the traversal of the at least one further tree data structure finding at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path; and outputting data relating to said database record identified by the link of the leaf child node of the paths with the best scores; wherein the traversing of said tree data structure includes a node determination process, the node determination process including; checking the data content of a node of the tree data structure, and if the node contains data identifying another tree data structure, or group of nodes, then performing the traversal on that other tree data structure, or if the node does not contain data identifying another tree data structure then, for each child node of that node, computing a score based on a match between the search request and the match data associated with the child node. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A computing apparatus that is configured to enable searching of a database comprising a plurality of records for at least one said record that at least approximately matches a search request, wherein data values in each of the records are organized in at least one field, the computing apparatus including a memory, and a processor embodied with the memory, the computing apparatus further including:
-
a first tree creator for creating a first tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of a field of a database record, wherein leaf child nodes of the first tree data structure include a link to another tree data structure; a further tree creator for creating at least one further tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of a database record, wherein leaf child nodes of the further tree data structure include a link to said database record; a tree traversal mechanism for traversing the first tree data structure to find at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path; a further tree traversal mechanism for traversing at least one of the further tree data structures identified by the link of the leaf node of at least one said path, the traversal of the at least one further tree data structure finding at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path, and an output generator for outputting data relating to said database record identified by the link of the leaf child node of the paths with the best scores; wherein the traversing of said tree data structure includes a node determination process, the node determination process including; checking the data content of a node of the tree data structure, and if the node contains data identifying another tree data structure, or group of nodes, then performing the traversal on that other tree data structure, or if the node does not contain data identifying another tree data structure then, for each child node of that node, computing a score based on a match between the search request and the match data associated with the child node. - View Dependent Claims (14, 15, 16)
-
-
17. A computer program product comprising a computer storage medium having computer program code embodied on said storage medium for processing data, when the computer program code is executed, to make the computer perform a procedure to search a database comprising a plurality of records for at least one said record that at least approximately matches a search request, wherein data values in each of the records are organized in at least one field, wherein the procedure includes:
-
creating a first tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of a field of a database record, wherein leaf child nodes of the first tree data structure include a link to another tree data structure; creating at least one further tree data structure having a root node and at least one child node, each said child node being associated with match data corresponding to a data value of a database record, wherein leaf child nodes of the further tree data structure include a link to said database record; traversing the first tree data structure to find at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path; traversing at least one of the further tree data structures identified by the link of the leaf node of at least one said path, the traversal of the at least one further tree data structure finding at least one path between its root node and at least one of its said leaf child nodes, each said path being associated with a score reflecting a level of matching between the search request and the match data of the nodes in the path, and outputting data relating to said database record identified by the link of the leaf child node of the paths with the best scores; wherein the traversing of said tree data structure includes a node determination process, the node determination process including; checking the data content of a node of the tree data structure, and if the node contains data identifying another tree data structure, or group of nodes, then performing the traversal on that other tree data structure, or if the node does not contain data identifying another tree data structure then, for each child node of that node, computing a score based on a match between the search request and the match data associated with the child node.
-
Specification