Expanded inverted index

• US 20070073668A1
• Filed: 11/29/2006
• Published: 03/29/2007
• Est. Priority Date: 05/06/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Stephan, Wolfgang
• Granted Patent: US 7,634,468 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/954 Relational
• 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/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Indexing documents is accomplished by generating an inverted index for a collection of one or more documents. The inverted index includes an inverted list for an index term appearing in one or more of the documents in the collection, and one or more postings. A posting includes a document identifier identifying a document in the collection of documents, a position identifier identifying a position of the index term in the document, and proximity information specifying whether the index term is positioned in a predefined proximal relationship between the index term and another a second index term in the document.

Claims

1. A computer-implemented method of evaluating a search query including two or more index terms, the method comprising:

using proximity information specifying a proximal relationship between two or more search index terms to identify one or more groupings of the search query index terms that are related by a predefined proximal relationship; and

retrieving inverted lists for index terms not included in a grouping, and retrieving an inverted list for one index term for each grouping of index terms.

2. A method as in claim 1, further comprising:

evaluating the search query based on the retrieved inverted lists.

3. A method as in claim 1, wherein the grouping of index terms related by a predefined proximal relationship comprises a pair including a first index term immediately preceding a second index term.

4. A method as in claim 3, wherein the first index term comprises a common term.

5. A method as in claim 3, wherein the second index term comprises a common term.

6. A method as in claim 1, wherein the grouping of index terms related by a predefined proximal relationship is a triple including a first index term immediately preceded by a second index term and immediately followed by a third index term.

7. A method as in claim 1, wherein at least one of the retrieved inverted lists includes one or more postings, the postings comprising:

a document identifier identifying a document in a collection of documents,

a position identifier identifying a position of an index term in the document; and

proximity information specifying a proximal relationship between the index term and another index term in the document.

8. A method as in claim 1, wherein at least one of the retrieved inverted lists includes one or more postings, the postings comprising:

a document identifier identifying a document in the collection of documents,

a flag indicating the index term is positioned next to a common term in the document;

a frequency of the index term occurring in the document;

a common term identifier identifying the common term; and

a position identifier identifying a position of the index term in the document.

9. An article comprising a tangibly embodied machine-readable medium operable to cause one or more machines to perform operations comprising:

using proximity information specifying a proximal relationship between two or more search index terms to identify one or more groupings of the search query index terms that are related by a predefined proximal relationship; and

retrieving inverted lists for index terms not included in a grouping, and an inverted list for one index term for each grouping of index terms.

10. An article as in claim 9, further comprising instructions to evaluate the search query based on the retrieved inverted lists.

11. An article as in claim 9, wherein the grouping of index terms related by a predefined proximal relationship comprises a pair including a first index term immediately preceding a second index term.

12. An article as in claim 11, wherein the first index term comprises a common term.

13. An article as in claim 11, wherein the second index term comprises a common term.

14. An article as in claim 9, wherein the grouping of index terms related by a predefined proximal relationship comprises a triple including a first index term immediately preceded by a second index term and immediately followed by a third index term.

15. An article as in claim 9, wherein at least one of the retrieved inverted lists includes one or more postings, the postings comprising:

a document identifier identifying a document in a collection of documents,

a position identifier identifying a position of an index term in the document; and

proximity information specifying a proximal relationship between the index term and another index term in the document.

16. An article as in claim 9, wherein at least one of the retrieved inverted lists includes one or more postings, the postings comprising:

a document identifier identifying a document in a collection of documents,

a flag indicating an index term is positioned next to a common term in the document;

a frequency of the index term occurring in the document;

a common term identifier identifying the common term; and

a position identifier identifying a position of the index term in the document.

17. An apparatus comprising:

means for evaluating a search query by using proximity information specifying a proximal relationship between two or more search index terms to identify one or more groupings of the search index terms that are related by a predefined proximal relationship; and

means for retrieving inverted lists for index terms not included in a grouping, and retrieving an inverted list for one index term for each grouping of index terms.

18. An apparatus as in claim 17, further comprising:

means for evaluating the search query based on the retrieved inverted lists.

19. An apparatus as in claim 17, wherein at least one of the retrieved inverted lists comprises one or more postings, the postings comprising:

a document identifier identifying a document in a collection of documents,

a position identifier identifying a position of an index term in the document; and

proximity information specifying a proximal relationship between the index term and another index term in the document.

20. An apparatus as in claim 17, wherein at least one of the retrieved inverted lists includes one or more postings, the postings comprising:

a document identifier identifying a document in the collection of documents,

a flag indicating the index term is positioned next to a common term in the document;

a frequency of the index term occurring in the document;

a common term identifier identifying the common term; and

a position identifier identifying a position of the index term in the document.