Term-statistics modification for category-based search

• US 20060248074A1
• Filed: 04/28/2005
• Published: 11/02/2006
• Est. Priority Date: 04/28/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Carmel, David, Darlow, Adam, Soffer, Aya, Petruschka, Yael
• Granted Patent: US 7,401,073 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/33 Querying
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method for searching a document collection includes providing an index of terms indicating the documents in which the terms appear. A first statistical distribution of each of at least some of the terms in the index and a second statistical distribution of each of at least some of the categories are estimated a over the documents in the collection. A query including one or more of the terms and a category restriction referring to at least one of the categories is accepted. A modified term distribution is produced by operating on the first estimated statistical distribution of at least one of the terms in the query using the second estimated statistical distribution of the at least one of the categories, responsively to the category restriction. The query is applied to the index so as to return a response, in which occurrences of the at least one of the terms are scored responsively to the modified term distribution.

Claims

1. A method for searching a document collection that includes a plurality of documents that are respectively associated with one or more categories and contain terms, the method comprising:

providing an index of the terms indicating the documents in which the terms appear;

estimating a first statistical distribution of each of at least some of the terms in the index and a second statistical distribution of each of at least some of the categories over the documents in the collection;

accepting a query comprising one or more of the terms and a category restriction referring to at least one of the categories;

operating on the first estimated statistical distribution of at least one of the terms in the query using the second estimated statistical distribution of the at least one of the categories, responsively to the category restriction, so as to produce a modified term distribution; and

applying the query to the index so as to return a response in which occurrences of the at least one of the terms are scored responsively to the modified term distribution.

2. The method according to claim 1, wherein estimating the first statistical distribution comprises constructing term histograms of the at least some of the terms in the index, wherein estimating the second statistical distribution comprises constructing category histograms of the at least some of the categories, and wherein constructing the term and category histograms comprises mapping the documents in the collection to bins of the histograms.

3. The method according to claim 2, wherein constructing the term and category histograms comprises, when a document is added to or deleted from the collection, incrementally updating the term and category histograms responsively to the added or deleted document.

4. The method according to claim 2, wherein operating on the first estimated statistical distribution comprises determining a category restriction histogram based on the category histogram of the at least one of the categories responsively to the category restriction, and multiplying the category restriction histogram by the term histogram of the at least one of the terms in the query so as to produce a localized term histogram.

5. The method according to claim 4, wherein when the category restriction refers to two or more of the categories linked by a Boolean expression, determining the category restriction histogram comprises combining the category histograms of the two or more of the categories based on the Boolean expression.

6. The method according to claim 1, wherein applying the query comprises determining a local document frequency (DF) based on the modified term distribution, and processing the query using the local DF.

7. The method according to claim 1, wherein the response comprises a list of the documents, and wherein applying the query comprises ordering the list responsively to the modified term distribution.

8. The method according to claim 1 wherein estimating the second statistical distribution comprises querying a text retrieval engine (TRE) responsively to the category restriction, so as to obtain a list of documents in the collection that are associated with the category restriction.

9. The method according to claim 1, wherein the categories comprise sub-collections of the document collection, wherein the category restriction refers to at least one of the sub-collections, and wherein operating on the first estimated statistical distribution comprises producing the modified term distribution so as to describe the first statistical distribution within the sub-collections referred to by the category restriction.

10. Apparatus for searching a document collection, comprising:

a memory, which is arranged to store a plurality of documents that are respectively associated with one or more categories and contain terms;

a search processor, which is arranged to provide an index of the terms indicating the documents in which the terms appear, to estimate a first statistical distribution of each of at least some of the terms in the index and a second statistical distribution of each of at least some of the categories over the documents in the collection, to accept a query comprising one or more of the terms and a category restriction referring to at least one of the categories, to operate on the first estimated statistical distribution of at least one of the terms in the query using the second estimated statistical distribution of the at least one of the categories, responsively to the category restriction, so as to produce a modified term distribution, and to apply the query to the index so as to return a response in which occurrences of the at least one of the terms are scored responsively to the modified term distribution.

11. The apparatus according to claim 10, wherein the processor is arranged to construct term histograms of the at least some of the terms in the index, to construct category histograms of the at least some of the categories, and to map the documents in the collection to bins of the histograms, so as to estimate the first and second statistical distributions.

12. The apparatus according to claim 11, wherein the processor is arranged, when a document is added to or deleted from the collection, to incrementally update the term and category histograms responsively to the added or deleted document.

13. The apparatus according to claim 11, wherein the processor is arranged to determine a category restriction histogram based on the category histogram of the at least one of the categories responsively to the category restriction, and to multiply the category restriction histogram by the term histogram of the at least one of the terms in the query so as to produce a localized term histogram.

14. The apparatus according to claim 13, wherein when the category restriction refers to two or more of the categories linked by a Boolean expression, the processor is arranged to combine the category histograms of the two or more of the categories based on the Boolean expression, so as to determine the category restriction histogram.

15. The apparatus according to claim 10, wherein the processor is arranged to determine a local document frequency (DF) based on the modified term distribution, and to process the query using the local DF.

16. The apparatus according to claim 10, wherein the response comprises a list of the documents, and wherein the processor is arranged to order the list responsively to the modified term distribution.

17. The apparatus according to claim 10, wherein the processor is arranged to query a text retrieval engine (TRE) responsively to the category restriction and to obtain a list of documents in the collection that are associated with the category restriction, so as to estimate the second statistical distribution.

18. The apparatus according to claim 10, wherein the categories comprise sub-collections of the document collection, wherein the category restriction refers to at least one of the sub-collections, and wherein the processor is arranged to produce the modified term distribution so as to describe the first statistical distribution within the sub-collections referred to by the category restriction.

19. A computer software product for searching a document collection that includes a plurality of documents that are respectively associated with one or more categories and contain terms, the product comprising a computer-readable medium, in which program instructions are stored, which instructions, when read by the computer, cause the computer to store an index of the terms indicating the documents in which the terms appear, to estimate a first statistical distribution of each of at least some of the terms in the index and a second statistical distribution of each of at least some of the categories over the documents in the collection, to accept a query comprising one or more of the terms and a category restriction referring to at least one of the categories, to operate on the first estimated statistical distribution of at least one of the terms in the query using the second estimated statistical distribution of the at least one of the categories, responsively to the category restriction, so as to produce a modified term distribution, and to apply the query to the index so as to return a response in which occurrences of the at least one of the terms are scored responsively to the modified term distribution.

20. The product according to claim 19, wherein the instructions cause the computer to construct term histograms of the at least some of the terms in the index, to construct category histograms of the at least some of the categories, and to map the documents in the collection to bins of the histograms, so as to estimate the first and second statistical distributions.

21. The product according to claim 20, wherein the instructions cause the computer, when a document is added to or deleted from the collection, to incrementally update the term and category histograms responsively to the added or deleted document.

22. The product according to claim 20, wherein the instructions cause the computer to determine a category restriction histogram based on the category histogram of the at least one of the categories responsively to the category restriction, and to multiply the category restriction histogram by the term histogram of the at least one of the terms in the query so as to produce a localized term histogram.

23. The product according to claim 22, wherein when the category restriction refers to two or more of the categories linked by a Boolean expression, the instructions cause the computer to combine the category histograms of the two or more of the categories based on the Boolean expression, so as to determine the category restriction histogram.

24. The product according to claim 19, wherein the instructions cause the computer to determine a local document frequency (DF) based on the modified term distribution, and to process the query using the local DF.

25. The product according to claim 19, wherein the response comprises a list of the documents, and wherein the instructions cause the computer to order the list responsively to the modified term distribution.

26. The product according to claim 19, wherein the instructions cause the computer to query a text retrieval engine (TRE) responsively to the category restriction and to obtain a list of documents in the collection that are associated with the category restriction, so as to estimate the second statistical distribution.

27. The product according to claim 19, wherein the categories comprise sub-collections of the document collection, wherein the category restriction refers to at least one of the sub-collections, and wherein the instructions cause the computer to produce the modified term distribution so as to describe the first statistical distribution within the sub-collections referred to by the category restriction.