Methods and systems for compressing indices

• US 8,060,516 B2
• Filed: 09/20/2010
• Issued: 11/15/2011
• Est. Priority Date: 12/30/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Weissman, Adam J.
• Primary Examiner(s): Vo; Tim T
• Assistant Examiner(s): Ahn; Sangwoo
• Application Number:
  US12/886,000
• Publication Number:
  US 20110066623A1
• Time in Patent Office: 421 Days
• Field of Search: 707/742, 707/696, 707/711, 707/715
• US Class Current: 707/742
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems and methods for compressing indices are described. In one aspect, a plurality of items are selected where each item has an entry in an inverted index and each item entry comprises a listing of articles that the item appears in. At least a first item entry and a second item entry are determined for compression and the second item entry is compressed into the first item entry resulting in a compressed first item entry.

Claims

1. A method implemented by a data processing system of a single computer or a network of computer processors, the method comprising:

selecting from an inverted index first and second entries, each of which includes

an index identifying a concept,

a plurality of document identifiers each identifying a document in which the concept identified by the index is expressed, and

a plurality of concept values each representing a strength of the expression of the concept identified by the index in a respective identified document;

determining, by the data processing system, a plurality of new concept values from the plurality of concept values in the first and second entries; and

combining, by the data processing system, the first and second entries into a combined entry, the combined entry including

a plurality of document identifiers each identifying a document in which at least one of the concepts identified by the indices of the first and second entries is expressed, and

the plurality of new concept values determined from the plurality of concept values in the first and second entries.

2. The method of claim 1, further comprising:

receiving a first search query involving the concept identified by the index in the first entry;

receiving a second search query involving the concept identified by the index in the second entry; and

responding to both the first search query and the second search query using the combined entry.

3. The method of claim 1, wherein the determining the plurality of new concept values comprises averaging, for each document identified by the plurality of document identifiers in the first and second entries, respective concept values.

4. The method of claim 1, wherein the plurality of document identifiers included in the combined entry includes:

a first document identifier that identifies a first document in which the concept identified by the index of the first entry is not expressed; and

a second document identifier that identifies a second document in which the concept identified by the index of the second entry is not expressed.

5. The method of claim 1, further comprising determining, by the data processing system, a cost of combining the first and second entries.

6. The method of claim 5, wherein determining the cost comprises determining a sum of differences between the concept values that represent the strength of the expression of the concept identified by the index of the first entry and the concept values that represent the strength of the expression of the concept identified by the index of the second entry for each document identified by the plurality of document identifiers in the first and second entries.

7. The method of claim 1, wherein the document identifiers comprise pointers to the documents in which the concepts are expressed.

8. The method of claim 1, wherein the concept values represent the strength of the expressions of the concepts in relation to other concepts expressed in the respective identified documents.

9. A system comprising:

a data processing system formed of a single computer or a network of computer processors; and

an inverted index database stored on one or more data storage devices, the inverted index database comprising a first entry and a combined entry, wherein;

the first entry comprises

an entry index identifying a concept and

a pointer to the combined entry; and

the combined entry comprises

a plurality of document identifiers each identifying a document and

a plurality of concept values each associated with a corresponding document identifier,

wherein a strength at which the concept identified by the index of the first entry is expressed in a first document differs from the concept value associated with the document identifier that identifies the first document.

10. The system of claim 9, wherein the concept value associated with the document identifier that identifies the first document is an average of

the strength at which the concept identified by the index of the first entry is expressed in the first document and

a strength at which one or more other concepts are expressed in the first document.

11. The system of claim 9, wherein the data processing system further comprises a search engine.

12. The system of claim 11, wherein:

the system further comprises a client device in data communication with the search engine, the client device programmed to transmit search queries to the search engine; and

the search engine is programmed to respond to the search queries using the inverted index database.

13. The system of claim 11, wherein the search engine is programmed to respond to a first search query involving the concept identified by the index included in the first entry using the combined entry.

14. The system of claim 9, wherein each concept value represents an average strength of the expressions of two or more concepts in relation to other concepts expressed in the document identified by the corresponding document identifier.

15. A system comprising:

a data processing system formed of a single computer or a network of computer processors; and

an inverted index database stored on one or more data storage devices, the inverted index database comprising a first entry and a combined entry, wherein;

the first entry comprises

an index identifying a concept and

a pointer to the combined entry; and

the combined entry comprises

a plurality of document identifiers each identifying a document, wherein the concept identified by the index of the first entry does not appear in at least one of the documents identified by the document identifiers included in the combined entry.

16. The system of claim 15, wherein the combined entry further comprises a plurality of concept values each associated with a respective document identifier.

17. The system of claim 16, wherein the concept values in the combined entry are averages of strengths of the expression of the concept identified by the index in the first entry and strengths of the expression of a second concept.

18. The system of claim 17, wherein the strengths of the expression are in relation to other concepts expressed in the documents identified by the document identifiers.

19. The system of claim 15, wherein the data processing system further comprises a search engine.

20. The system of claim 19, wherein:

the system further comprises a client device in data communication with the search engine, the client device programmed to transmit search queries to the search engine; and

the search engine is programmed to respond to the search queries using the inverted index database.

21. The system of claim 19, wherein the search engine is programmed to respond to a first search query involving the concept identified by the index included in the first entry using the combined entry.