System, method and technique for searching structured databases

• US 7,403,941 B2
• Filed: 04/25/2005
• Issued: 07/22/2008
• Est. Priority Date: 04/23/2004
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Novauris Technologies Ltd. (Apple Inc.)
• Inventors: Cook, Gary D, Bedworth, Mark D.
• Primary Examiner(s): Alam; Shahid A
• Assistant Examiner(s): NGUYEN, PHONG H
• Application Number:
  US11/115,070
• Publication Number:
  US 20060004721A1
• Time in Patent Office: 1,184 Days
• Field of Search: 707/1, 707/3, 707/102, 707/104.1, 717/144, 704/256, 382/228
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

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.

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.

2. A method according to claim 1, wherein the match data of said child node of the first tree data structure corresponds to said data value of said record of a first set of said database records and the match data of said child node of said further tree data structure corresponds to said data value of said record of another set of said database records.

3. A method according to claim 1, wherein the at least one child node of the first tree data structure corresponds to at least one different data value of a first common field, the first common field being a field amongst the fields of at least some of the database records having a least number of different data values and the match data of said child node of the first tree data structure corresponds to a data value of the first common field.

4. A method according to claim 1, wherein the at least one child node of said further tree data structure corresponds to at least one different data value of a further common field, said further common field being selected from amongst the fields of at least some of the database records based on a number of different data values the field contains and the match data of a said child node of said further tree data structure corresponds to data value of said further common field.

5. A method according to claim 1, wherein data related to at least some of the tree data structures created is stored on a storage medium external to the processing device performing the method and the data relating to said tree data structure is transferred to the processing device when the tree data structure is to be traversed.

6. A method according to claim 1, wherein the traversing of said tree data structure includes:

placing the root node of the tree onto a queue data structure;

popping the node from the queue data structure;

performing the node determination process on the popped node, wherein data relating to the node and the score computed for the node is placed on the queue data structure, and

the scores of nodes in the queue being used to determine the selection of said further tree data structure for the traversal.

7. A method according to claim 1, wherein the computation of the score uses a Dynamic Programming technique to score a degree of matching between the search request and a hypothesis based on the match data of said path.

8. A method according to claim 7 wherein data describing said score computed for a portion of said hypothesis is stored and retrieved to avoid re-computation of the score.

9. A method according to claim 3, wherein said database record includes one or more fields, the one or more fields including data values that represent an address and contact details associated with the address.

10. A method according to claim 9, wherein the record further includes a field including a data value representing a name associated with the address and/or contact details.

11. A method according to claim 9, wherein the record includes a field including a data value representing a state and/or a ZIP/postal code.

12. A method according to claim 11, wherein the first common field includes the field representing the state or the ZIP/postal code.

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.

14. The computing apparatus of claim 13, further including an input converter for converting an input signal based on an audible signal to produce data that describes the search request.

15. The computing apparatus of claim 13, further including an output converter for converting the output data relating to the said database record into an audible signal.

16. The computing apparatus of claims 13, further including an interface for receiving an input signal over a network and/or transmitting an output over a network.

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.