Lossy index compression

• US 20040158580A1
• Filed: 01/09/2004
• Published: 08/12/2004
• Est. Priority Date: 12/19/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Farchi, Eitan, Soffer, Aya, Carmel, David, Fagin, Ronald, Cohen, Doron, Herscovici, Michael, Maarek, Yoelle
• Granted Patent: US 7,356,527 B2
• Time in Patent Office: Days
• US Class Current: 707/104.1
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

An apparatus is provided for performing a method (FIG. 2) for pruning an index of a corpus of text documents, wherein the method includes steps for ranking (50) the postings in the index and pruning (48) from the index the postings below a given level in the ranking. The pruning methods of the invention are lossy, since some document postings are removed from the full index; however, the user cannot differentiate the lossy index from the full index.

Claims

1. Apparatus for indexing a corpus of text documents, characterized by an index processor which is arranged to create an inverted index of terms appearing in the documents, the index comprising postings of the terms in the documents, the processor being further arranged to create rankings of the postings in the index, and prune from the index the postings below a given level in the ranking.

2. Apparatus according to claim 1, wherein the processor is arranged to determine a separate ranking for each of at least some of the terms separately, and to prune the separate ranking for each of at least some of the terms.

3. Apparatus according to claim 2, further characterized by a user interface for receiving at least one parameter, wherein the processor is arranged to set the given level based on the parameter and the separate index ranking.

4. Apparatus according to claim 3, wherein the at least one parameter comprises a number k of documents to retrieve from the index, and a number r of the terms permitted in a query, and wherein the processor is arranged to set the level based on the score of one of the documents ranked k from the top in the ranking.

5. Apparatus according to claim 4, wherein the processor is arranged to set the given level by dividing the score of the one of the documents by r.

6. Apparatus according to claim 3, wherein the at least one parameter comprises a number δ

, of the portion of the documents to retrieve from the ranking, and a number r, of the terms permitted in a query, and wherein the processor is arranged to set given the level based on the score of the first document out of the documents in the ranking, δ

, and r.

7. Apparatus according to claim 6, wherein the processor is arranged to multiply the score of the first document by δ

and divide by r.

8. Apparatus according to claim 1, wherein the processor is arranged to select the postings to prune based on information on a statistical distribution of queries in a search space with respect to the document postings.

9. Apparatus according to claim 8, further characterized by a user interface for receiving at least one parameter, wherein the processor is arranged to set the given level based on the parameter and the index ranking.

10. Apparatus according to claim 9, wherein the at least one parameter comprises a number M of the scores to remain in the pruned inverted index.

11. Apparatus according to claim 10, wherein the processor is arranged to determine a probability of at least some of the terms and to multiply the posting scores for each of the at least some of the terms by the probability of the term, and to rank all the postings by the multiplied posting scores, and wherein the given level comprises the score of document M from the top of the ranking.

12. Apparatus according to claim 1, wherein the index processor is characterized by a computer having large memory capacity, and comprising apparatus for transferring the index after pruning to a device with limited memory capacity.

13. Apparatus according to claim 12, wherein the device with limited memory capacity comprises a handheld computing device.

14. Apparatus for performing a method for indexing a corpus of text documents, wherein the method is characterized by steps for:

creating an inverted index of terms appearing in the documents, the index comprising postings of the terms in the documents;

ranking the postings in the index; and

pruning from the index the postings below a given level in the ranking.