Methods and Systems for Compressing Indices

• US 20110066623A1
• Filed: 09/20/2010
• Published: 03/17/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.
• Granted Patent: US 8,060,516 B2
• Time in Patent Office: Days
• 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-29. -29. (canceled)

30. 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 that each represents a strength of the expression of the concept identified by the index in a respective of the identified documents;

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 are expressed, and

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

31. The method of claim 30, 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.

32. The method of claim 30, 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.

33. The method of claim 30, 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.

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

35. The method of claim 34, wherein determining the cost comprises determining a sum of differences between the concept values that represents the strength of the expression of the concept identified by the index of the first entry and the concept values that represents 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.

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

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

38. 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 of the document identifiers,

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

39. The system of claim 38, 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.

40. The system of claim 38, wherein the data processing system further comprises a search engine.

41. The system of claim 40, 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.

42. The system of claim 40, 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.

44. 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.

43. The system of claim 44, wherein the concept values each represent an average strength of the expressions of two or more concepts in relation to other concepts expressed in the document identified by the associated document identifier.

45. The system of claim 44, wherein the combined entry further comprises a plurality of concept values, each of which is associated with a respective document identifier.

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

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

48. The system of claim 44, wherein the data processing system further comprises a search engine.

49. The system of claim 48, 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.

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