Expanded inverted index

• US 7,149,748 B1
• Filed: 05/06/2003
• Issued: 12/12/2006
• Est. Priority Date: 05/06/2003
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Stephan, Wolfgang
• Primary Examiner(s): HWANG, JOON H
• Application Number:
  US10/431,075
• Time in Patent Office: 1,316 Days
• Field of Search: 707/102, 707/1
• US Class Current: 707/742
• 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 for indexing documents, the method comprising:

generating an inverted index for a collection of one or more documents, the inverted index comprising;

an inverted list for a single index term appearing in one or more of the documents in the collection, the inverted list including one or more postings, where a posting comprises;

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 a proximal relationship between the index term and another index term in the document.

2. The computer-implemented method of claim 1, wherein the proximity information comprises:

a flag indicating whether the index term is positioned in a predefined proximal relationship to a second index term in the document.

3. The computer-implemented method of claim 2, wherein the proximity information further comprises:

an index term identifier identifying the second index term.

4. The computer-implemented method of claim 2, wherein the second index term comprises a common term.

5. The computer-implemented method of claim 2, wherein the predefined proximal relationship specifies the second index term immediately precedes the index term.

6. The computer-implemented method of claim 2, wherein the predefined proximal relationship specifies the second index term immediately follows the index term.

7. The computer-implemented method of claim 2, wherein the predefined proximal relationship specifies the second index term is positioned within a predefined proximity to the index term.

8. The computer-implemented method of claim 1, wherein the posting further includes a frequency of the index term occurring in the document.

9. The computer-implemented method of claim 1, wherein the proximity information further specifies whether the index term is positioned in a predefined proximal relationship to a second index term and a third index term in the document.

10. The computer-implemented method of claim 1, wherein the collection of one or more documents includes one or more binary files, data tables, source code files, text documents or combinations thereof.

11. The computer-implemented method of claim 1, wherein the collection of one or more documents includes unstructured documents or structured documents or both.

12. A computer-implemented method for indexing documents, the method comprising:

creating an inverted index for a collection of one or more documents, the inverted index comprising;

an inverted list for a single index term included in the collection, the inverted list including one or more postings, where a posting comprises;

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.

13. The computer-implemented method of claim 12, wherein the flag indicates the index term is positioned immediately following a common term in the document.

14. The computer-implemented method of claim 12, wherein the flag indicates the index term is positioned immediately before a common term in the document.

15. An article comprising a machine-readable storage medium storing instructions operable to cause one or more machines to perform operations comprising:

generating an inverted index for a collection of one or more documents, the inverted index comprising;

an inverted list for a single index term appearing in one or more of the documents in the collection, the inverted list including one or more postings, where a posting comprises;

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 specify whether the index term is positioned to have a predefined proximal relationship with a second index term in the document.

16. The article of claim 15, wherein the proximity information comprises:

a flag indicating whether the index term is positioned in a predefined proximal relationship to a second index term in the document.

17. The article of claim 16, wherein the proximity information further comprises:

an index term identifier identifying the second index term.

18. The article of claim 15, wherein the second index term comprises a common term.

19. The article of claim 15, wherein the predefined proximal relationship specifies the second index term immediately precedes the index term.

20. The article of claim 15, wherein the predefined proximal relationship specifies the second index term immediately follows the index term.

21. The article of claim 15, wherein the posting further includes a frequency of the index term occurring in the document.

22. The article of claim 15, wherein the predefined proximal relationship specifies the second index term is positioned within a predefined proximity to the index term.

23. The article of claim 15, wherein the proximity information further specifies whether the index term is positioned in a predefined proximal relationship to the second index term and a third index term in the document.

24. The article of claim 15, wherein the collection of one or more documents includes one or more binary files, data tables, source code files, text documents or combinations thereof.

25. The article of claim 15, wherein the collection of one or more documents includes unstructured documents or structured documents or both.

26. An article comprising a machine-readable storage medium storing instructions operable to cause one or more machines to perform operations comprising:

creating an inverted index for a collection of one or more documents, the inverted index comprising;

an inverted list for a single index term included in the collection, the inverted list including one or more postings, where a posting comprises;

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.

27. The article of claim 26, wherein the flag indicates the index term is positioned immediately following a common term in the document.

28. The article of claim 26, wherein the flag indicates the index term is positioned immediately before a common term in the document.