Methods and systems for compressing indices

• US 8,549,000 B2
• Filed: 11/14/2011
• Issued: 10/01/2013
• 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): Ahn, Sangwoo
• Application Number:
  US13/295,286
• Publication Number:
  US 20120059828A1
• Time in Patent Office: 687 Days
• Field of Search: None
• US Class Current: 707/736
• 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 data processing system comprising:

memory storing an inverted index comprising a plurality of entries, wherein

i) a first of the entries includes

a plurality of document identifiers each identifying a document,

ii) a second of the entries

identifies at least one word, concept, or image and includes a pointer to the first of the entries, and

iii) a third of the entries

identifies at least one word, concept, or image that differs from the at least one word, concept, or image identified by the second of the entries and includes

a pointer to the first of the entries,

wherein the first entry is a combined entry related to the second of the entries and the third of the entries; and

one or more data processors programmed to retrieve document identifiers that identify documents responsive to search queries, the retrieving including

receiving a first search query to which the at least one word, concept, or image identified by the second of the entries is responsive,

locating the second of the entries in the inverted index using the first search query,

following the pointer in the second of the entries to the first of the entries,

retrieving at least some of the plurality of document identifiers in the first of the entries for responding to the first search query,

receiving a second search query to which the at least one word, concept, or image identified by the third the entries is responsive,

locating the third of the entries in the inverted index using the second search query,

following the pointer in the third of the entries to the first of the entries, and

retrieving at least some of the plurality of document identifiers in the first of the entries for responding to the second search query.

2. The data processing system of claim 1, wherein the one or more data processors programmed to retrieve document identifiers comprises a search engine.

3. The data processing system of claim 2, further comprising:

a first remote client device programmed to submit the first search query; and

a second remote client device programmed to submit the second search query,

wherein the one or more data processors are programmed transmit the retrieved document identifiers for responding to the first search query to the first remote client device and retrieved document identifiers for responding to the second search query to the second remote client device.

4. The data processing system of claim 1, wherein:

the at least one word, concept, or image identified by the second of the entries is a first concept;

the at least one word, concept, or image identified by the third of the entries is a second concept; and

the first of the entries includes a plurality of values each representing an average strength of expression of the first concept and the second concept in a respective of the documents identified by plurality of document identifiers.

5. The data processing system of claim 1, wherein the retrieving of the document identifiers further comprises:

processing a document retrieved for responding to the second search query to determine a strength of expression of the at least one word, concept, or image responsive to the first search query in the processed document; and

ranking the processed document based at least in part on the determined strength of expression.

6. The data processing system of claim 1, wherein the one or more data processors are further programmed to perform operations including:

determining that a cost of compressing the second of the entries and the third of the entries is acceptable, and

in response to determining that the cost is acceptable, creating the combined entry in the inverted index.

7. A data processing system comprising:

memory storing an inverted index comprising a plurality of entries, wherein

i) a first of the entries includes

a plurality of document identifiers each identifying a document, and

ii) a second of the entries

identifies at least one word or concept and includes

a pointer to the first of the entries,

wherein the first of the entries is a combined entry related to the second of the entries and at least one additional of the entries; and

one or more data processors programmed to retrieve document identifiers that identify documents responsive to a search query, the retrieving including

receiving a search query to which the at least one word or concept identified by the second of the entries is responsive,

locating the second of the entries in the inverted index using the search query,

following the pointer in the second of the entries to the first of the entries and retrieving at least some of the plurality of document identifiers therefrom,

processing two or more of the documents identified by the retrieved document identifiers to determine a strength of expression of the at least one word or concept in each of the processed documents, and

ranking the processed documents based at least in part on the determined strengths of expression.

8. The data processing system of claim 7, wherein the one or more data processors programmed to retrieve document identifiers comprises a search engine.

9. The data processing system of claim 8, further comprising a remote client device programmed to submit the search query, wherein the one or more data processors are programmed transmit the ranking of the processed documents to the remote client device.

10. The data processing system of claim 7, wherein the at least one additional of the entries includes a third of the entries in the inverted index that:

identifies at least one word or concept that differs from the at least one word or concept, or image identified by the second of the entries; and

includes a pointer to the first of the entries.

11. The data processing system of claim 10, wherein the one or more data processors are further programmed to perform operations including:

determining that a cost of compressing the second of the entries and the third of the entries is acceptable, and

in response to determining that the cost is acceptable, creating the combined entry in the inverted index.

12. A data processing system comprising:

memory storing an inverted index comprising a plurality of entries, wherein

i) a first of the entries

identifies a first word or concept and

includes a plurality of document identifiers each identifying a respective document in which the word or concept identified by the first of the entries is expressed, and

ii) a second of the entries

identifies a second word or concept and

includes a plurality of document identifiers each identifying a respective document in which the word or concept identified by the second of the entries is expressed; and

one or more data processors programmed to perform operations including;

determining that a cost of compressing the first of the entries and the second of the entries is acceptable, and

in response to determining that the cost is acceptable, creating a combined entry in the inverted index, wherein the combined entry includes

at least one of the plurality of document identifiers in the first of the entries that is absent from the second of the entries.

13. The data processing system of claim 12, wherein the operations further comprise adding a pointer to the combined entry into the first of the entries.

14. The data processing system of claim 13, wherein the operations further comprise adding a pointer to the combined entry into the second of the entries.

15. The data processing system of claim 12, wherein the one or more data processors are further programmed to retrieve document identifiers that identify documents responsive to a search query, the retrieving including

receiving a search query to which the at least one word or concept identified by the second of the entries is responsive,

locating the first of the entries in the inverted index using the search query,

following the pointer in the first of the entries to the combined entry, and

retrieving the at least one of the plurality of document identifiers therefrom.

16. The data processing system of claim 12, wherein the retrieving further comprises:

processing a document identified by the retrieved document identifier to determine a strength of expression of the first word or concept in the processed document; and

ranking the processed document based at least in part on the determined strength of expression.

17. The data processing system of claim 12, wherein the compressed index further comprises at least one of the plurality of document identifiers in the second of the entries that is absent from the first of the entries.

18. The data processing system of claim 12, wherein:

the first of the entries further comprises values each associated with a respective of the document identifiers and representing a strength of expression of the word or concept identified by the first of the entries in the document identified by the associated document identifier; and

the second of the entries further comprises values each associated with a respective of the document identifiers and representing a strength of expression of the word or concept identified by the second index in the document identified by the associated document identifier.

19. The data processing system of claim 18, wherein the combined entry further comprises values each associated with a respective of a plurality of document identifiers and representing an average strength of expression of the word or concept identified by the first of the entries and the word or concept identified by the second of the entries in the document identified by the associated document identifier.

20. The data processing system of claim 12, wherein determining that the cost of compressing is acceptable comprises determining a benefit of compressing the first of the entries and the second of the entries.