HYBRID TERM AND DOCUMENT-BASED INDEXING FOR SEARCH QUERY RESOLUTION

• US 20090254523A1
• Filed: 04/04/2008
• Published: 10/08/2009
• Est. Priority Date: 04/04/2008
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chang, Choongsoon, Lang, Kevin, Lim, Swee
• Application Number:
  US12/098,376
• Publication Number:
  US 20090254523A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Methods and apparatuses relate to hosting an inverted index for term-based document searching. According to disclosed aspects, each bank of a plurality of banks receives a plurality of Document IDentifiers (DocIDs) in the inverted index, and within each bank, posting lists for each term are determined large or small. DocIDs for large posting lists are distributed among computers in a bank while responsibility for producing DocIDs identifiers in a small posting list are distributed by term to one or fewer computers in the bank. During operation, each term of a query is distributed to each bank, and then for small terms, only those computers assigned responsibility for a given term need to search for responsive DocIDs. DocIDs can be redistributed among computers in a bank such that results are presented from the computers that would have produced those results in a cluster having a pure DocIDs distribution scheme.

Claims

1. A method of distributing on a computing cluster an inverted index comprising terms respectively associated with posting lists of document identifiers (DocIDs), comprising:

organizing n computers into B banks;

distributing document IDentifiers (DocIDs) appearing in posting lists of an inverted index among the B banks of computers, each posting list corresponding to a search term;

within a bank of the B banks, distributing portions of the DocIDs, which appear in a large posting list and are distributed to that bank, to a plurality of the computers within that bank;

within that bank, assigning responsibility to produce posting list results for a small posting list term to fewer of the computers of that bank; and

providing for the distribution of DocIDs appearing in the small posting list, which are not already distributed thereto, to its assigned computer(s).

2. The method of claim 1, wherein a posting list is determined large by determining that the posting list has more than T DocIDs and a posting list is determined small by determining that the posting list has no more than T DocIDs.

3. The method of claim 1, wherein a posting list is determined large by determining that the posting list has at least T DocIDs.

4. The method of claim 1, further comprising distributing documents according to modulo division of a portion of a hash of a DocID with B.

5. The method of claim 1, wherein a given one of the banks includes k computers, and distribution of terms in that bank is based on modulo division of a hash value for each term divided modulo by k.

6. The method of claim 1, wherein assigning responsibility for the small posting list comprises using a hash value for a term to which the small posting list corresponds to determine the computer to which responsibility is assigned.

7. The method of claim 1, further comprising, providing, for each bank, a small term index mapping assignments of small posting lists to computers of that bank.

8. The method of claim 7, further comprising storing the small term index on one of the computers in the bank.

9. The method of claim 1, further comprising determining, bank-by-bank, whether a posting list portion for a given term is small in that bank.

10. A computer cluster for providing searching of an inverted index comprising posting lists of document identifiers of documents in which each term of a plurality of terms appears, comprising:

n computers organized into B banks, each computer operable for storing data assigned to it, wherein

each computer of a respective bank stores a portion of document identifiers that are assigned to that bank and which are associated with a large posting list, and

all the document identifiers assigned to that bank which are associated with a small posting list corresponding to a term assigned to that computer.

11. The computer cluster of claim 10, further comprising an index mapping small posting list terms to the respective computer to which they were assigned.

12. The computer cluster of claim 10, wherein the portion of document identifiers assigned to that bank were assigned based on a hash value derived from the document identifier.

13. The computer cluster of claim 10, wherein the term was assigned based on a hash value derived from the term.

14. A method of identifying documents potentially relevant to a term-based query, comprising:

receiving a query comprising search terms;

using a computer cluster of n computers organized into B banks, the computer cluster hosting an inverted index comprising posting lists of DocIDs in which each term of a plurality of terms appears, and each computer of a respective bank stores a portion of DocIDs that are assigned to that bank and which are associated with a large posting list, and all the DocIDs assigned to that bank, which are associated with a small posting list corresponding to a term assigned to that computer;

distributing the search terms to each bank; and

in each bank,

for any term corresponding to a small posting list, retrieving its corresponding smaller posting list from the computer to which it was assigned, and

for any term corresponding to a large posting list, retrieving a portion of its corresponding posting list from each computer of the bank.

15. The method of claim 14, further comprising collecting retrieved posting lists results at each computer and at each bank.

16. A method of organizing a computer cluster for supporting term-based searching of an inverted index, comprising:

dividing n computers of the computer cluster into B banks;

distributing selections of document identifiers of an inverted index among the B banks, wherein at least some of the document identifiers are distributed to fewer than all of the B banks; and

distributing the document identifiers assigned to each bank among the computers of that bank, wherein B is selected for balancing an aggregate search throughput of the computer cluster with respective search latencies for individual searches.

17. The method of claim 16, further comprising adjusting B based on measurements of aggregate search throughput and samples of latencies for searches resulting in larger result sets.

18. The method of claim 16, wherein B is increased to decrease individual search latencies.

19. The method of claim 16, wherein B is decreased to increase aggregate search throughput.

20. The method of claim 16, further comprising receiving a search request comprising one or more search terms, distributing the search request among the B banks, determining which computer or computes in each bank was distributed each of the search terms and producing a posting list for each search term from those computers.

21. The method of claim 20, further comprising aggregating respective posting list results for each search term from each bank within a management process.