System and method for indexing and querying structured text

• US 20030140035A1
• Filed: 01/07/2002
• Published: 07/24/2003
• Est. Priority Date: 01/07/2002
• Status: Active Grant

• Current Assignee: Valtrus Innovations Limited (f/k/a Dolya Holdco 9 Limited) (Key Patent Innovations Limited)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Burrows, Michael
• Granted Patent: US 6,963,869 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An indexer indexes a database of documents, and a search engine searches the database of documents. Nesting level information stored in index entries is used to identify, and match together, start and end meta words comprising fields at assorted nesting levels within a document. Based on a query specifying words to be found within fields, spatial criteria are applied to the identified meta words to determine if the specified words are found within the specified fields. A subset of the documents have nested fields, and each nested field has an associated start meta word and end meta word. Each meta word has an associated nesting level. Each document is indexed by parsing the document to determine locations within the document of words and meta words, as well as the nesting level associated with each meta word. An index is generated that has word entries, meta word entries, and generic meta word entries. The meta word entries indicate locations within the documents of an identified meta word, as well as the nesting level of the meta word. The generic meta word entries identify locations within the document of a class of meta words, including meta words at all nesting levels of the meta words within the document. For each identified location within the generic meta word entry, the generic meta word entry also includes nesting level information associated with the meta word at the identified location.

Claims

1. A computer-implemented method of indexing a database of documents, a subset of the documents containing nested fields, each nested field having an associated start meta word and end meta word, each meta word having an associated nesting level, the method comprising:

indexing each document containing nested fields by;

parsing the document to determine locations within the document of words and

meta words in the document and to determine the nesting level associated with each meta word; and

generating an index including

word entries, each word entry identifying locations within the document of an identified word;

meta word entries, each meta word entry identifying locations within the document of an identified meta word and indicating the determined nesting level associated with the meta word; and

generic meta word entries, each generic meta word entry identifying locations within the document of a class of meta words, including meta words at all nesting levels of the meta words found in the document, the generic meta word entry including, for each identified location within the generic meta word entry, information identifying the nesting level associated with the meta word at the identified location.

2. The computer-implemented method of claim 1, wherein each word entry, meta word entry, and generic meta word entry includes an object identifier and a location list.

3. The computer-implemented method of claim 1, wherein, for each word entry, the object identifier includes one or more words, and the location list includes locations of the one or more words in the document.

4. The computer-implemented method of claim 1, wherein, for each meta word entry, the object identifier includes a meta word and an indication of the nesting level associated with the meta word, and the location list includes locations of the meta word in the document.

5. The computer-implemented method of claim 1, wherein, for each generic meta word entry, the object identifier includes a class of meta words, including meta words at all nesting levels of the meta words found in the document, and the location list includes locations of each occurrence of each meta word in the class of meta words in the document, and further includes an indication of the nesting level associated with each occurrence of each meta word in the class of meta words at each location.

6. The computer-implemented method of claim 5, wherein, for the location list for each generic meta word entry, each location of each occurrence of each meta word in the class of meta words in the document is mathematically combined with the nesting level associated with that occurrence of that meta word at that location to encode both the location and the nesting level into a single value.

7. A computer-implemented method of searching a database of documents, a subset of the documents containing nested fields, each nested field having an associated start meta word and end meta word, each meta word having an associated nesting level, the method comprising:

receiving a query that specifies one or more words to be found within a specified field within a document;

determining a start meta word and end meta word associated with the specified field;

searching an index to identify locations of the specified words and locations of a class of meta words that includes at least one of the start meta word and end meta word associated with the specified field;

applying first spatial criteria to the identified locations of the class of meta words with respect to the identified locations of the specified words to select a meta word from the class of meta words;

determining the nesting level of the selected meta word;

identifying a complementary meta word corresponding to the selected meta word;

searching the index to determine a location for the identified complementary meta word; and

applying second spatial criteria to the identified locations of the specified words and to the determined location for the identified complementary meta word to generate a result that indicates whether the specified words are found within a first field associated with the selected meta word and the identified complementary meta word.

8. The computer-implemented method of claim 7, wherein the first field is the specified field.

9. The computer-implemented method of claim 7, wherein at least a plurality of the steps of applying first spatial criteria, determining the nesting level, identifying a complementary meta word, searching the index, and applying second spatial criteria are repeated until a final a result is generated.

10. The computer-implemented method of claim 9, wherein the final result is selected from the set consisting of (A) the specified words are found within the specified field, and (B) there is no instance of the specified words within the specified field.

11. The computer-implemented method of claim 7, wherein the step of identifying comprises identifying a complementary meta word corresponding to the selected meta word and to its determined nesting level.

12. The computer-implemented method of claim 7, wherein the class of meta words includes a specific meta word at all nesting levels of the specific meta word found in the database.

13. The computer-implemented method of claim 7, wherein the step of applying first spatial criteria comprises the steps of:

determining a closest location of the identified locations of the class of meta words with respect to an identified location of the specified words, and

selecting the meta word from the class of meta words corresponding to the determined closest location.

14. The computer-implemented method of claim 13, wherein the step of applying second spatial criteria comprises determining whether the identified location of the specified words falls between the determined location for the identified complementary meta word and the determined closest location of the identified locations of the class of meta words to generate a result that indicates whether the specified words are found within the specified field.

15. The computer-implemented method of claim 7, wherein the class of meta words further includes an object identifier and a location list, the object identifier including at least one of the start meta word and end meta word, and the location list including a location, and nesting level information at that location, for each occurrence of the at least one of the start meta word and end meta word.

16. A computer-implemented method of searching a database of documents, a subset of the documents containing nested fields, each nested field having an associated start meta word and end meta word, each meta word having an associated nesting level, the method comprising:

receiving a query that specifies one or more words to be found within a first specified field that is found within a second specified field within a document;

determining a first start meta word and first end meta word associated with the first specified field, and a second start meta word and second end meta word associated with the second specified field;

searching an index to identify;

locations of the specified words,

locations of a first class of meta words that includes at least one of the first start meta word and first end meta word associated with the first specified field, and

locations of a second class of meta words that includes at least one of the second start meta word and second end meta word associated with the second specified field;

applying first spatial criteria, determined at least in part from the received query, to the identified locations of the first and second classes of meta words and the identified locations of the specified words to select a first meta word from the first class of meta words, and a second meta word from the second class of meta words;

determining the nesting levels of the first and second selected meta words;

identifying a first and second complementary meta words, corresponding to the first and second selected meta words;

searching the index to determine a location for the first identified complementary meta word and a location for the second identified complementary meta word; and

applying second spatial criteria, determined from the received query, to the identified locations of the specified words and to the determined locations for the first and second identified complementary meta words to generate a result that indicates whether the specified words are found within a first field, associated with the first selected meta word and the first identified complementary meta word, that is found within a second field, associated with the second selected meta word and the second identified complementary meta word.

17. The computer-implemented method of claim 16, wherein the first field is the first specified field and the second field is the second specified field.

18. The computer-implemented method of claim 16, wherein at least a plurality of the steps of applying first spatial criteria, determining nesting levels, identifying first and second complementary meta words, searching the index, and applying second spatial criteria are repeated until a final a result is generated.

19. The computer-implemented method of claim 18, wherein the final result is selected from the set consisting of (A) the specified words are found within an instance of the first specified field that is found within an instance of the second specified field, and (B) there is no instance of the specified words within an instance of the first specified field that is within an instance of the second specified field.

20. The computer-implemented method of claim 16, wherein the steps of applying first spatial criteria, determining nesting levels, identifying first and second complementary meta words, searching the index and applying second spatial criteria include:

applying the first spatial criteria to the identified locations of the first class of meta words and to the identified locations of the specified words to select a first me a word from the first class of meta words;

determining the nesting level of the first selected meta word;

identifying a first complementary meta word, corresponding to the first selected meta word;

searching the index to determine a location for the first identified complementary meta word;

applying the second spatial criteria to the identified locations of the specified words and to the determined location for the first identified complementary meta word to generate a first result;

applying the first spatial criteria to the identified locations of the second class of meta words and to the identified location corresponding to the first selected meta word to select a second meta word from the second class of meta words;

determining the nesting level of the second selected meta word;

identifying a second complementary meta word, corresponding to the second selected meta word;

searching the index to determine a location for the second identified complementary meta word; and

applying the second spatial criteria to the determined location for the first identified complementary meta word and to the determined location for the second identified complementary meta word to generate a second result.

21. The computer-implemented method of claim 20, wherein at least a plurality of the steps of applying first spatial criteria to the identified locations of the first class of meta words, determining the nesting level of the first selected meta word, identifying the first complementary meta word, searching the index to determine a location for the first identified complementary meta word, and applying second spatial criteria to generate a first result are repeated until the first result is a first final result.

22. The computer-implemented method of claim 21, wherein the first final result is selected from the set consisting of (A) the specified words are found within an instance of the first specified field, and (B) there is no instance of the specified words within an instance of the first specified field.

23. The computer-implemented method of claim 16, wherein the step of identifying comprises identifying a first and second complementary meta words corresponding to the first and second selected meta words, and to the determined nesting levels of the first and second selected meta words.

24. The computer-implemented method of claim 16, wherein the first and second classes of meta words include a specific meta word at all nesting levels of the specific meta word found in the database.

25. The computer-implemented method of claim 16, wherein the step of applying first spatial criteria comprises the steps of:

determining a closest location of the identified locations of the first class of meta words with respect to an identified location of the specified words,

selecting a first meta word from the first class of meta words corresponding to the determined closest location of the first class of meta words,

determining a closest location of the identified locations of the second class of meta words with respect to the first closest location of the identified locations of the first class of meta words, and

selecting a second meta word from the second class of meta words corresponding to the determined closest location of the second class of meta words.

26. The computer-implemented method of claim 25, wherein the step of applying second spatial criteria comprises the steps of:

determining whether the identified location of the specified words falls between the determined location for the first identified complementary meta word and the determined closest location of the first class of meta words,

determining whether the determined location for the first identified complementary meta word falls between the determined location for the second identified complementary meta word and the identified location of the specified words, and

generating a result, based on the determining steps of applying second spatial criteria, that indicates whether that the specified words are found within an instance of the first specified field that is found within an instance of the second specified field.

27. The computer-implemented method of claim 16, wherein the first class of meta words further includes an object identifier and a location list, the object identifier including at least one of the first start meta word and first end meta word, and the location list including a location, and nesting level information at that location, for each occurrence of the at least one of the first start meta word and first end meta word.

28. The computer-implemented method of claim 16, wherein the first class of meta words and the second class of meta words constitute the same class of meta words.

29. A computer-implemented method for searching an index of a database of documents, the index having entries, each entry including an object identifier and a location list, each object identifier including at least one of a word and a meta word, each location list including one or more locations of the at least one of a word and a meta word of each corresponding object identifier, each entry associated with a meta word also including nesting level information for the meta word, the computer-implemented method comprising:

receiving a query that specifies one or more words to be found within a specified field within a document;

determining a start meta word and end meta word associated with the specified field;

identifying a bounding meta word by selecting one of the start meta word and end meta word;

searching the index to identify a first entry that has an object identifier associated with the specified words;

searching the index to identify a second entry that has an object identifier associated with the bounding meta word;

determining a bounding location from a closest occurrence of the bounding meta word with respect to the specified words, by comparing the location list of the second entry and the location list of the first entry;

identifying nesting level information for the bounding meta word at the bounding location;

identifying a complementary meta word to the bounding meta word having corresponding nesting level information as the identified nesting level information for the bounding meta word;

searching the index to locate a third entry that has an object identifier associated with the complementary meta word;

determining a complementary location from the location list of the third entry; and

generating a result that indicates whether the specified words are within a first field, associated with the bounding meta word and the complementary meta word, by determining whether a location in the location list of the first entry falls between the bounding location and the complementary location.

30. The computer-implemented method of claim 29, wherein the complementary location of the complementary meta word is opposite to the bounding location of the bounding meta word, relative to the specified words, in the index of the database of documents.

31. The computer-implemented method of claim 29, wherein the first field is the specified field.

32. The computer-implemented method of claim 29, wherein the step of determining a bounding location comprises determining a bounding location of the bounding meta word by applying first spatial criteria to the location list of the second entry and the location list of the first entry, and further wherein the computer-implemented method includes repeating at least a plurality of the steps of determining a bounding location, identifying nesting level information, identifying a complementary meta word, searching the index, determining a complementary location, and generating a result until a final a result is generated.

33. The computer-implemented method of claim 32, wherein the final result is selected from the set consisting of (A) the specified words are found within the specified field, and (B) there is no instance of the specified words within the specified field.

34. A computer program product for use in conjunction with a computer system, the computer system for indexing a database of documents, a subset of the documents containing nested fields, each nested field having an associated start meta word and end meta word, each meta word having an associated nesting level, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

an indexer for indexing each document containing nested fields by configuring the computer to;

parse the document to determine locations within the document of words and meta words in the document and to determine the nesting level associated with each meta word; and

generate an index including

word entries, each word entry identifying locations within the document of an identified word;

meta word entries, each meta word entry identifying locations within the document of an identified meta word and indicating the determined nesting level associated with the meta word; and

generic meta word entries, each generic meta word entry identifying locations within the document of a class of meta words, including meta words at all nesting levels of the meta words found in the document, the generic meta word entry including, for each identified location within the generic meta word entry, information identifying the nesting level associated with the meta word at the identified location.

35. The computer program product of claim 34, wherein each word entry, meta word entry, and generic meta word entry includes an object identifier and a location list.

36. The computer program product of claim 34, wherein, for each meta word entry, the object identifier includes a meta word and an indication of the nesting level associated with the meta word, and the location list includes locations of the meta word in the document.

37. The computer program product of claim 34, wherein, for each generic meta word entry, the object identifier includes a class of meta words, including meta words at all nesting levels of the meta words found in the document, and the location list includes locations of each occurrence of each meta word in the class of meta words in the document, and further includes an indication of the nesting level associated with each occurrence of each meta word in the class of meta words at each location.

38. The computer program product of claim 37, wherein, for the location list for each generic meta word entry, each location of each occurrence of each meta word in the class of meta words in the document is mathematically combined with the nesting level associated with that occurrence of that meta word at that location to encode both the location and the nesting level into a single value.

39. A computer program product for use in conjunction with a computer system, the computer system for searching a database of documents, a subset of the documents containing nested fields, each nested field having an associated start meta word and end meta word, each meta word having an associated nesting level, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for receiving a query that specifies one or more words to be found within a specified field within a document;

instructions for determining a start meta word and end meta word associated with the specified field;

instructions for searching an index to identify locations of the specified words and locations of a class of meta words that includes at least one of the start meta word and end meta word associated with the specified field;

instructions for applying first spatial criteria to the identified locations of the class of meta words with respect to the identified locations of the specified words to select a meta word from the class of meta words;

instructions for determining the nesting level of the selected meta word;

instructions for identifying a complementary meta word corresponding to the selected meta word;

instructions for searching the index to determine a location for the identified complementary meta word; and

instructions for applying second spatial criteria to the identified locations of the specified words and to the determined location for the identified complementary meta word to generate a result that indicates whether the specified words are found within a first field associated with the selected meta word and the identified complementary meta word.

40. The computer program product of claim 39, wherein the first field is the specified field.

41. The computer program product of claim 39, wherein at least a plurality of the instructions for applying first spatial criteria, determining the nesting level, identifying a complementary meta word, searching the index, and applying second spatial criteria are repeated until a final a result is generated.

42. The computer program product of claim 41, wherein the final result is selected from the set consisting of (A) the specified words are found within the specified field, and (B) there is no instance of the specified words within the specified field.

43. The computer program product of claim 39, wherein the instructions for identifying comprise instructions for identifying a complementary meta word corresponding to the selected meta word and to its determined nesting level.

44. The computer program product of claim 39, wherein the class of meta words includes a specific meta word at all nesting levels of the specific meta word found in the database.

45. The computer program product of claim 39, wherein the instructions for applying first spatial criteria comprise:

instructions for determining a closest location of the identified locations of the class of meta words with respect to an identified location of the specified words, and

instructions for selecting the meta word from the class of meta words corresponding to the determined closest location.

46. The computer program product of claim 45, wherein the instructions for applying second spatial criteria comprise instructions for determining whether the identified location of the specified words falls between the determined location for the identified complementary meta word and the determined closest location of the identified locations of the class of meta words to generate a result that indicates whether the specified words are found within the specified field.

47. The computer program product of claim 39, wherein the class of meta words further includes an object identifier and a location list, the object identifier including at least one of the start meta word and end meta word, and the location list including a location, and nesting level information at that location, for each occurrence of the at least one of the start meta word and end meta word.

48. A computer program product for use in conjunction with a computer system, the computer system for searching a database of documents, a subset of the documents containing nested fields, each nested field having an associated start meta word and end meta word, each meta word having an associated nesting level, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for receiving a query that specifies one or more words to be found within a first specified field that is found within a second specified field within a document;

instructions for determining a first start meta word and first end meta word associated with the first specified field, and a second start meta word and second end meta word associated with the second specified field;

instructions for searching an index to identify;

locations of the specified words,

locations of a first class of meta words that includes at least one of the first start meta word and first end meta word associated with the first specified field, and

locations of a second class of meta words that includes at least one of the second start meta word and second end meta word associated with the second specified field;

instructions for applying first spatial criteria, determined at least in part from the received query, to the identified locations of the first and second classes of meta words and the identified locations of the specified words to select a first meta word from the first class of meta words, a second meta word from the second class of meta words;

instructions for determining the nesting levels of the first and second selected meta words;

instructions for identifying a first and second complementary meta words, corresponding to the first and second selected meta words, and searching the index to determine a location for the first identified complementary meta word and a location for the second identified complementary meta word; and

instructions for applying second spatial criteria, determined from the received query, to the identified locations of the specified words and to the determined locations for the first and second identified complementary meta words to generate a result that indicates whether the specified words are found within a first field, associated with the first selected meta word and the first identified complementary meta word, that is found within a second field, associated with the second selected meta word and the second identified complementary meta word.

49. The computer program product of claim 48, wherein the first field is the first specified field and the second field is the second specified field.

50. The computer program product of claim 48, wherein at least a plurality of the instructions for applying first spatial criteria, determining nesting levels, identifying first and second complementary meta words, searching the index, and applying second spatial criteria are repeated until a final a result is generated.

51. The computer program product of claim 50, wherein the final result is selected from the set consisting of (A) the specified words are found within an instance of the first specified field that is found within an instance of the second specified field, and (B) there is no instance of the specified words within an instance of the first specified field that is within an instance of the second specified field.

52. The computer program product of claim 48, wherein the instructions for applying first spatial criteria, determining nesting levels, identifying first and second complementary meta words, searching the index and applying second spatial criteria include:

instructions for applying the first spatial criteria to the identified locations of the first class of meta words and to the identified locations of the specified words to select a first meta word from the first class of meta words;

instructions for determining the nesting level of the first selected meta word;

instructions for identifying a first complementary meta word, corresponding to the first selected meta word;

instructions for searching the index to determine a location for the first identified complementary meta word;

instructions for applying the second spatial criteria to the identified locations of the specified words and to the determined location for the first identified complementary meta word to generate a first result;

instructions for applying the first spatial criteria to the identified locations of the second class of meta words and to the identified location corresponding to the first selected meta word to select a second meta word from the second class of meta words;

instructions for determining the nesting level of the second selected meta word;

instructions for identifying a second complementary meta word, corresponding to the second selected meta word;

instructions for searching the index to determine a location for the second identified complementary meta word; and

instructions for applying the second spatial criteria to the determined location for the first identified complementary meta word and to the determined location for the second identified complementary meta word to generate a second result.

53. The computer program product of claim 52, wherein at least a plurality of the instructions for applying first spatial criteria to the identified locations of the first class of meta words, determining the nesting level of the first selected meta word, identifying the first complementary meta word, searching the index to determine a location for the first identified complementary meta word, and applying second spatial criteria to generate a first result are repeated until the first result is a first final result.

54. The computer program product of claim 53, wherein the first final result is selected from the set consisting of (A) the specified words are found within an instance of the first specified field, and (B) there is no instance of the specified words within an instance of the first specified field.

55. The computer program product of claim 48, wherein the instructions for identifying comprise instructions for identifying a first and second complementary meta words corresponding to the first and second selected meta words, and to the determined nesting levels of the first and second selected meta words.

56. The computer program product of claim 48, wherein the first and second classes of meta words include a specific meta word at all nesting levels of the specific meta word found in the database.

57. The computer program product of claim 48, wherein the instructions for applying first spatial criteria comprise:

instructions for determining a closest location of the identified locations of the first class of meta words with respect to an identified location of the specified words,

instructions for selecting a first meta word from the first class of meta words corresponding to the determined closest location of the first class of meta words,

instructions for determining a closest location of the identified locations of the second class of meta words with respect to the first closest location of the identified locations of the first class of meta words, and

instructions for selecting a second meta word from the second class of meta words corresponding to the determined closest location of the second class of meta words.

58. The computer program product of claim 51, wherein the instructions for applying second spatial criteria comprise:

instructions for determining whether the identified location of the specified words falls between the determined location for the first identified complementary meta word and the determined closest location of the first class of meta words,

instructions for determining whether the determined location for the first identified complementary meta word falls between the determined location for the second identified complementary meta word and the identified location of the specified words, and

instructions for generating a result that indicates whether that the specified words are found within an instance of the first specified field that is found within an instance of the second specified field if both determinations are true.

59. The computer program product of claim 48, wherein the first class of meta words further includes an object identifier and a location list, the object identifier including at least one of the first start meta word and first end meta word, and the location list including a location, and nesting level information at that location, for each occurrence of the at least one of the first start meta word and first end meta word.

60. The computer program product of claim 48, wherein the first class of meta words and the second class of meta words constitute the same class of meta words.

61. A computer program product for use in conjunction with a computer system, the computer system for searching an index of a database of documents, the index having entries, each entry including an object identifier and a location list, each object identifier including at least one of a word and a meta word, each location list including one or more locations of the at least one of a word and a meta word of each corresponding object identifier, each entry associated with a meta word also including nesting level information for the meta word, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

instructions for receiving a query that specifies one or more words to be found within a specified field within a document;

instructions for determining a start meta word and end meta word associated with the specified field;

instructions for identifying a bounding meta word by selecting one of the start meta word and end meta word;

instructions for searching the index to identify a first entry that has an object identifier associated with the specified words;

instructions for searching the index to identify a second entry that has an object identifier associated with the bounding meta word;

instructions for determining a bounding location from a closest occurrence of the bounding meta word with respect to the specified words, by comparing the location list of the second entry and the location list of the first entry;

instructions for identifying nesting level information for the bounding meta word at the bounding location;

instructions for identifying a complementary meta word to the bounding meta word having corresponding nesting level information as the identified nesting level information for the bounding meta word;

instructions for searching the index to locate a third entry that has an object identifier associated with the complementary meta word;

instructions for determining a complementary location from the location list of the third entry; and

instructions for generating a result that indicates whether the specified words are within a first field, associated with the bounding meta word and the complementary meta word, by determining whether a location in the location list of the first entry falls between the bounding location and the complementary location.

62. The computer program product of claim 61, wherein the complementary location of the complementary meta word is opposite to the bounding location of the bounding meta word, relative to the specified words, in the index of the database of documents.

63. The computer program product of claim 61, wherein the first field is the specified field.

64. The computer program product of claim 61, wherein the instructions for determining a bounding location comprise instructions for determining a bounding location of the bounding meta word by applying first spatial criteria to the location list of the second entry and the location list of the first entry, and further wherein the computer program product includes instructions for repeating at least a plurality of the instructions for determining a bounding location, identifying nesting level information, identifying a complementary meta word, searching the index, determining a complementary location, and generating a result until a final a result is generated.

65. The computer program product of claim 64, wherein the final result is selected from the set consisting of (A) the specified words are found within the specified field, and (B) there is no instance of the specified words within the specified field.