Techniques for searching for best matches in tables of information

• US 6,678,675 B1
• Filed: 03/30/2000
• Issued: 01/13/2004
• Est. Priority Date: 03/30/2000
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Portal Software, Inc. (Oracle Corporation)
• Inventors: Rothrock, Michael R.
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): THAI, HANH B
• Application Number:
  US09/539,669
• Time in Patent Office: 1,384 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6
• US Class Current: 707/780
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

Techniques for searching for best matches in tables of information are provided. A first tree is traversed according to a first value for a first field and as information is encountered at each node, the information is written to a second tree. The second tree is traversed according to a second value for a second field to determine the best match for the first and second values. By utilizing the first and second trees, efficient searching for best matches can be achieved while allowing for dynamic modification of the data.

Claims

1. A computer implemented method of searching for best matches in a table storing information in multiple rows, wherein each row includes multiple fields, comprising:

traversing a first tree that stores information from the rows of the table according to a first value for a first field;

saving the information that is encountered when traversing the first tree in a second tree according to data in a second field; and

traversing the second tree according to a second value for the second field to determine the best match for the first and second values.

2. The method of claim 1, further comprising building the first tree by retrieving a row, retrieving data from the first field, traversing the first tree according to the data, and adding information from the row at an appropriate node of the first tree.

3. The method of claim 1, further comprising receiving the first and second values.

4. The method of claim 1, wherein longer matches of the second field take precedence over longer matches of the first field.

5. The method of claim 1, wherein traversing the second tree includes:

traversing the second tree according to the second value for the second field;

saving the information that is encountered when traversing the second tree in a third tree according to data in a third field; and

traversing the third tree according to a third value for the third field to determine the best match for the first, second and third values.

6. A computer program product that searches for best matches in a table storing information in multiple rows, wherein each row includes multiple fields, comprising:

computer code that traverses a first tree that stores information from the rows of the table according to a first value for a first field;

computer code that saves the information that is encountered when traversing the first tree in a second tree according to data in a second field;

computer code that traverses the second tree according to a second value for the second field to determine the best match for the first and second values; and

a computer readable medium that stores the computer codes.

7. The computer program product of claim 6, wherein the computer readable medium is a CD-ROM, floppy disk, tape, flash memory, system memory, hard drive, or data signal embodied in a carrier wave.

14. The computer program product of claim 6, further computer code that builds the first tree by retrieving a row, retrieves data from the first field, traverses the first tree according to the data, and adds information from the row at an appropriate node of the first tree.

15. The computer program product of claim 6, further comprising computer code that receives the first and second values.

16. The computer program product of claim 6, wherein longer matches of the second field take precedence over longer matches of the first field.

17. The computer program product of claim 6, wherein the computer code that traverses the second tree includes:

computer code that traverses the second tree according to the second value for the second field;

computer code that saves the information that is encountered when traversing the second tree in a third tree according to data in a third field; and

computer code that traverses the third tree according to a third value for the third field to determine the best match for the first, second and third values.

8. A computer implemented method of searching for best matches in a table storing information in multiple rows, wherein each row includes multiple fields, comprising:

receiving first and second values, where the first value indicates a desired value for a first field in the table and the second value indicates a desired value for a second field in the table;

traversing a first tree by the first value, wherein the first tree stores at each node information from the rows in the table according to data in the first field;

as each node is traversed, saving the information that is encountered to a second tree according to data in the second field; and

traversing the second tree according to the second value to determine the best match for the first and second values.

9. The method of claim 8, further comprising building the first tree by retrieving a row, retrieving data from the first field, traversing the first tree according to the data, and adding information from the row at an appropriate node of the first tree.

10. The method of claim 8, wherein longer matches of the second field take precedence over longer matches of the first field.

11. The method of claim 8, wherein traversing the second tree includes:

traversing the second tree according to the second value for the second field;

saving the information that is encountered when traversing the second tree in a third tree according to data in a third field; and

traversing the third tree according to a third value for the third field to determine the best match for the first, second and third values.

12. A computer program product for mapping a graphical user interface of an application, comprising:

computer code that receives first and second values, where the first value indicates a desired value for a first field in the table and the second value indicates a desired value for a second field in the table;

computer code that traverses a first tree by the first value, wherein the first tree stores at each node information from the rows in the table according to data in the first field;

computer code that, as each node is traversed, saves the information that is encountered to a second tree according to data in the second field;

computer code that traverses the second tree according to the second value to determine the best match for the first and second values; and

a computer readable medium that stores the computer codes.

13. The computer program product of claim 12, wherein the computer readable medium is a CD-ROM, floppy disk, tape, flash memory, system memory, hard drive, or data signal embodied in a carrier wave.

18. The computer program product of claim 12, further comprising computer code that builds the first tree by retrieving a row, retrieves data from the first field, traverses the first tree according to the data, and adds information from the row at an appropriate node of the first tree.

19. The computer program product of claim 12, wherein longer the second field take precedence over longer matches of the first field.

20. The computer program product of claim 12, wherein the computer code that traverses the second tree includes:

computer code that traverses the second tree according to the second value for the second field;

computer code that saves the information that is encountered when traversing the second tree in a third tree according to data in a third field; and

computer code that traverses the third tree according to a third value for the third field to determine the best match for the first, second and third values.