Systems and methods for indexing content for fast and scalable retrieval

• US 7,849,063 B2
• Filed: 10/15/2004
• Issued: 12/07/2010
• Est. Priority Date: 10/17/2003
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Mg, Thiruvalluvan, Hunt, Patrick David, Stata, Raymond P.
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): Pulliam; Christyann R
• Application Number:
  US10/966,566
• Publication Number:
  US 20050198076A1
• Time in Patent Office: 2,244 Days
• Field of Search: None
• US Class Current: 707/696
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence

Abstract

Systems and methods for query processing and indexing of documents in connection with a content store in a computing system are provided. In various embodiments, an indexing model is provided that is optimized for fast, efficient and scalable retrieval of documents satisfying a query, including the mixed use of forward and inverted indexing representations, including algorithms for achieving a balance between the two representations. When processing queries, fast and efficient generation of reverse chronologically ordered posting lists is enabled for efficient execution of logical operators on query result sets. A term expand index is also provided wherein the overall terms included in the term expand index are decomposed into a plurality of lexicon files, which are combined when convenient for fast, scalable efficiency when performing queries of the content in the content store.

Claims

1. A method for generating an index set for use in connection with the querying of documents in a content store, the method comprising:

updating said index set by storing in the index set a collection of single document indices that index terms from a set of documents, wherein each single document index of the collection of document indices indexes terms from a single document of the set of documents according to a position of the terms in the single document;

monitoring a size of the collection of single document indices;

detecting that the size of the collection has attained a specified size;

in response to detecting that the size of the collection has attained the specified size, generating a new multiple document index by converting a subset of the collection of single document indices to the new multiple document index, wherein;

the new multiple document index indexes terms from the subset, sorted by term;

wherein the subset includes at least two single document indices that index terms from at least two single documents of the set of documents, and wherein the subset includes fewer than all single document indices;

wherein;

converting the subset to the new multiple document index causes the subset to be removed from the collection of single document indices;

each document in said content store is indexed by a single document index that indexes terms of the document if and only if the document is not indexed by a multiple document index that indexes terms of multiple documents;

the method is performed by one or more computing devices.

2. A method according to claim 1, wherein said collection of single document indices is ordered according to at least one ranking function.

3. A method according to claim 2, wherein the at least one ranking function includes a ranking function that ranks the single document indices according to times associated with single documents of the set of documents that are indexed by the single document indices.

4. A method according to claim 3, wherein the ranking function that ranks the single document indices according to times associated with the single documents of the set of documents ranks the single document indices in one of reverse chronological order or forward chronological order.

5. A method according to claim 3, wherein the at least one ranking function includes a ranking function that ranks the single document indices according to dates associated with the single documents of the set of documents.

6. A method according to claim 1, wherein said new multiple document index that indexes terms of the subset, sorted by term, includes at least (a) a first multiple document index that indexes terms from multiple documents, sorted by term, and is partitioned according to at least one ranking function, and (b) at least a second multiple document index that indexes terms from multiple other documents, sorted by term, and is not partitioned according to said at least one ranking function.

7. A method according to claim 6, wherein at least the first multiple document index is partitioned by time and at least the second multiple document index is not partitioned by time.

8. A method according to claim 7, wherein at least the first multiple document index is partitioned by date and at least the second multiple document index is not partitioned by date.

9. A method according to claim 7, wherein at least the first multiple document index is partitioned by time according to a dynamic granularity.

10. A method according to claim 1, further comprising:

storing at least one Bloom filter to be applied when scanning the collection of single document indices for at least one query term.

11. A method according to claim 1, wherein the collection of single document indices includes a series of fingerprints that correspond to terms in the set of documents, wherein each term maps uniquely to a fingerprint.

12. A method according to claim 1, further comprising:

detecting that one or more processors are idle;

wherein;

the step of generating is performed in response to detecting both that the size of the collection has attained the specified size and that one or more processors are idle.

13. A method according to claim 1, further comprising:

merging at least two multiple document indices that index terms of multiple documents, sorted by term, when the number of multiple document indices reaches or exceeds a specified number.

14. A method according to claim 13, wherein the merging includes merging said at least two multiple document indices as a background task that is allowed to proceed in response to detecting that one or more processors are idle.

15. A method according to claim 1, further comprising:

receiving a new document;

generating a single document index that indexes terms of only the new document; and

storing the single document index into the collection of single document indices that index terms of the set of documents.

16. A method according to claim 1, further comprising:

receiving a batch of new documents; and

processing the batch of new documents for storing in the index set as at least one of (A) at least one collection of single document indices that each indexes terms of a single document of the batch of new documents, or (B) at least one multiple document index that indexes terms of multiple documents of the batch of new documents, sorted by term, that occur in the multiple documents of the batch of new documents.

17. A method according to claim 1, wherein the specified size is a percentage relative to an available storage space, wherein the percentage is greater than zero and less than the entire available storage space.

18. A computer readable storage medium storing computer executable instructions for performing the method of claim 1.

19. An apparatus for generating an index set for use in connection with the querying of documents in a content store, the apparatus comprising:

one or more processors coupled to one or more storage devices;

wherein execution of one or more instructions stored on the one or more storage devices causes the one or more processors to perform;

updating said index set by storing in the index set a collection of single document indices that index terms from a set of documents, wherein each single document index of the collection of document indices indexes terms from a single document of the set of documents according to a position of the terms in the single document;

monitoring a size of the collection of single document indices;

detecting that the size of the collection has attained a specified size;

in response to detecting that the size of the collection has attained the specified size, generating a new multiple document index by converting a subset of the collection of single document indices to the new multiple document index, wherein;

the new multiple document index indexes terms from the subset, sorted by term;

wherein the subset includes at least two single document indices that index terms from at least two single documents of the set of documents, and wherein the subset includes fewer than all single document indices;

wherein;

converting the subset to the new multiple document index causes the subset to be removed from the collection of single document indices;

each document in said content store is indexed by a single document index that indexes terms of the document if and only if the document is not indexed by a multiple document index that indexes terms of multiple documents.

20. A method for querying documents in a content store, the method comprising:

accessing an index set including;

a first plurality of single document indices that index terms of a first set of documents according to a position of the terms in the first set of documents, wherein each single document index of the first plurality of single document indices indexes terms of a single document of the first set of documents, and

a second plurality of multiple document indices that index terms of a second set of documents, sorted by term , wherein each multiple document index of the second plurality of multiple document indices indexes terms of multiple documents of the second set of documents;

wherein each multiple document index of the second plurality of multiple document indices is generated by converting a subset of a collection of single document indices when a size of the collection of single document indices reaches a specified size;

receiving at least one query term for processing against said index set;

scanning the first plurality of single document indices for said at least one query term and retrieving a first set of document identifiers for documents that satisfy the at least one query term; and

querying against the second plurality of multiple document indices with said at least one query term and retrieving a second set of document identifiers for documents that satisfy the at least one query term;

wherein each document in said content store is indexed by a single document index in the first plurality of single document indices if and only if the document is not indexed by a multiple document index in the second plurality of multiple document indices;

wherein the method is performed by one or more computing devices.

21. A method according to claim 20, further comprising:

terminating said scanning without said querying if said first set of document identifiers completely satisfies the at least one query term.

22. A method according to claim 20, further comprising:

terminating said querying when said first set of document identifiers and said second set of document identifiers completely satisfy the at least one query term.

23. A method according to claim 20, wherein said first set of document identifiers are sorted according to a ranking function as a result of said first plurality of single document indices representing documents sorted according to the same ranking function.

24. A method according to claim 23, wherein said first set of document identifiers are sorted according to reverse chronological order as a result of said first plurality of single document indices representing documents according to reverse chronological order.

25. A method according to claim 20, wherein said first set of document identifiers include at least one of (A) document identifiers that are sorted according to a ranking function as a result of the first plurality of single document indices representing documents sorted according to the same ranking function or (B) document identifiers that are not sorted according to the ranking function as a result of the first plurality of single document indices not representing documents sorted according to the ranking function.

26. A method according to claim 25, wherein said first set of document identifiers include document identifiers that are sorted according to time.

27. A method according to claim 26, wherein said first set of document identifiers include document identifiers that are sorted in reverse chronological order.

28. A method according to claim 23, wherein for each query term, said first and second sets of document identifiers are combined to form a posting list sorted according to the ranking function.

29. A method according to claim 28, wherein for each query term, said first and second sets of document identifiers are combined to form a posting list sorted according to reverse chronological order.

30. A method according to claim 20, wherein scanning includes scanning a series of fingerprints of the first plurality of single document indices, wherein the series of fingerprints corresponds to terms in the first set of documents, wherein each term maps uniquely to a fingerprint.

31. A method according to claim 20, wherein said scanning the first plurality of single document indices for said at least one query term includes first applying a Bloom filter to determine whether a query term condition is not satisfied by said first plurality of single document indices.

32. A method according to claim 20, further comprising:

monitoring a size of the first plurality of single document indices;

in response to detecting that the size of the first plurality of single document indices has attained the specified size, generating a new multiple document index in the second plurality of multiple document indices by converting a subset of the first plurality of single document indices to the new multiple document index, wherein the new multiple document index indexes terms from the subset, sorted by term;

wherein the subset includes at least two single document indices that index terms from at least two single documents of the first set of documents, and wherein the subset includes fewer than all of the first plurality of single document indices.

33. A method according to claim 32, wherein the specified size is a percentage relative to an available storage space, wherein the percentage is greater than zero and less than the entire available storage space.

34. A computer readable storage medium storing computer executable instructions for performing the method of claim 20.

35. An apparatus for querying documents in a content store, the apparatus comprising:

one or more processors coupled to one or more storage devices;

wherein execution of one or more instructions stored on the one or more storage devices causes the one or more processors to perform;

accessing an index set including;

a first plurality of single document indices that index terms of a first set of documents according to a position of the terms in the first set of documents, wherein each single document index of the first plurality of single document indices indexes text of a single document of the first set of documents, and

a second plurality of multiple document indices that index terms of a second set of documents, sorted by term, wherein each multiple document index of the second plurality of multiple document indices indexes terms of multiple documents of the second set of documents;

wherein each multiple document index of the second plurality of multiple document indices is generated by converting a subset of a collection of single document indices when a size of the collection of single document indices reaches a specified size;

receiving at least one query term for processing against said index set;

scanning the first plurality of single document indices for said at least one query term and retrieving a first set of document identifiers for documents that satisfy the at least one query term; and

querying against the second plurality of multiple document indices with said at least one query term and retrieving a second set of document identifiers for documents that satisfy the at least one query term;

wherein each document in said content store is indexed by a single document index in the first plurality of single document indices if and only if the document is not indexed by a multiple document index in the second plurality of multiple document indices.