Granted Patent B2

US 8,484,221 · App. 12/787,119 · Granted Jul 9, 2013

Abstract

Claims (55)

1. A method of indexing documents, the method comprising:

extracting, by a computer processor, feature information from each of a plurality of documents to be indexed;

defining a plurality of indexes based on statistical properties of the extracted feature information, wherein the defining includes establishing, for each of the indexes, an upper limit on each of one or more parameters measuring a size of the index;

for each of at least some of the documents:

selecting one of the indexes as a destination index for the document based on the feature information extracted from the document, wherein the selecting includes:

identifying a current index from among the plurality of indexes;

determining, for each of the one or more parameters, whether adding the document to the current index will result in the index exceeding the upper limit on the parameter; and

selecting the current index as the destination index for the document in the event that adding the document to the current index will not result in the index exceeding the upper limit on any of the one or more parameters; and

adding a searchable representation of the document to the destination index;

and storing the plurality of indexes in a computer-readable storage medium.

2. The method of claim 1 wherein the one or more parameters include a parameter from a group consisting of a number of documents in the index, a number of tokens in the index, and a total size of the documents in the index.

3. The method of claim 1 further comprising:

defining a garbage index; and

wherein selecting one of the indexes as the destination index includes:

determining whether the document satisfies a criterion indicating that the document is unlikely to be relevant to a subsequent search query; and

selecting the garbage index as the destination index for the document in the event that the document satisfies the criterion.

4. The method of claim 3 wherein the criterion indicates that the document is unlikely to be relevant in the event that the fraction of tokens in the document that are nonalphanumeric tokens exceeds a threshold.

5. The method of claim 1 wherein selecting one of the indexes as the destination index includes:

determining whether the document satisfies a criterion indicating that the document is unlikely to be relevant to a subsequent search query, wherein the document is not added to any of the indexes in the event that the document satisfies the criterion.

6. The method of claim 1 wherein the document is associated with a metadata item, wherein defining the indexes includes associating different ones of the indexes with different values of the metadata item, and wherein selecting one of the indexes as a destination index for the document is performed based in part on the metadata item.

7. The method of claim 6 wherein the metadata item is selected from a group consisting of a language of the document, a document type, a creation date associated with the document, a modification date associated with the document, a source location associated with the document, a creator associated with the document, and a custodian associated with the document.

8. A non-transitory computer-readable storage medium encoded with program code that, when executed by a computer system, causes the computer system to execute a method of indexing documents, the method comprising:

generating a token-based representation of each of a plurality of documents;

extracting feature information from the token-based representations of the documents;

defining a plurality of indexes, including defining an upper limit for each of a plurality of size parameters measuring a size of each of the indexes; and

for at least one of the documents:

selecting one of the indexes as a destination index for the document based on the feature information, current values of the size parameters for at least one of the indexes, and the upper limits for the size parameters;

adding a searchable representation of the document to the destination index; and

updating the size parameters of the destination index based on the feature information for the document.

9. The non-transitory computer-readable storage medium of claim 8 wherein the size parameters include at least one parameter from a group consisting of a number of documents in the index, a number of tokens in the index, and a total size of the documents in the index.

10. The non-transitory computer-readable storage medium of claim 9 wherein the method further comprises:

defining a garbage index that has no upper limit for the plurality of size parameters;

identifying one or more of the documents as a garbage document based on a garbage criterion indicating that the document is unlikely to be relevant to a subsequent search query; and

adding a searchable representation of the garbage document to the garbage index.

11. The non-transitory computer-readable storage medium of claim 10 wherein the garbage criterion is based on a fraction of tokens in the document that are nonalphanumeric tokens.

12. The non-transitory computer-readable storage medium of claim 8 wherein the upper limits for the size parameters are defined such that when the indexes are populated with the plurality of documents, the indexes are of balanced size relative to each other.

13. The non-transitory computer-readable storage medium of claim 8 wherein the method further comprises:

receiving a search query from a source;

searching the plurality of indexes in response to the search query to identify one or more documents that match the search query; and

transmitting to the source a search report that includes identifying information of the one or more documents that match the search query.

14. The non-transitory computer-readable storage medium of claim 8 wherein the method further comprises:

receiving a search query from a source, the search query specifying a subset of the indexes to be searched;

searching the subset of the indexes in response to the search query to identify one or more documents that match the search query; and

transmitting to the source a search report that includes identifying information of the one or more documents that match the search query.

15. A computer system comprising:

a storage subsystem configured to store a plurality of document indexes; and

a processor coupled to the storage subsystem, the processor being configured to:

extract feature information from each of a plurality of documents;

define an upper limit for each of a plurality of size parameters for the plurality of document indexes, wherein the plurality of size parameters measure a size of each of the plurality of document indexes; and

for at least a first one of the documents:

select one of the document indexes as a destination index for the first document based on the feature information extracted from the first document, a set of current values of the size parameters for at least one of the indexes, and the upper limits for the size parameters for the at least one of the indexes;

store a searchable representation of the first document in the destination index; and

update the size parameters of the destination index based on the feature information for the first document.

16. The computer system of claim 15 wherein the size parameters include at least one parameter from a group consisting of a number of documents in the index, a number of tokens in the index, and a total size of the documents in the index.

17. The computer system of claim 15 wherein the plurality of document indexes includes a garbage index and wherein the processor is further configured to select the garbage index as the destination index for a second one of the documents based on a criterion indicating that the second document is unlikely to be relevant to a subsequent search query.

Assignments (14)