Search engine with hierarchically stored indices

• US 7,240,064 B2
• Filed: 11/10/2003
• Issued: 07/03/2007
• Est. Priority Date: 11/10/2003
• Status: Active Grant

• Current Assignee: Jollify Management Limited
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Egge, Tor, Risvik, Knut Magne, Aasheim, Yngve, Pettersen, Ha
• Primary Examiner(s): Ly; Cheyne D.
• Application Number:
  US10/705,641
• Publication Number:
  US 20050102270A1
• Time in Patent Office: 1,331 Days
• Field of Search: 707/2, 707/3, 707/5, 707/10, 707/102, 707/7
• US Class Current: 707/709
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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/99937 Sorting

Abstract

A search engine comprising a crawler which crawls the WWW and stores pages found on the WWW in a database. An indexer indexes the pages in the database to produce a primary index. A document mapping section maps pages in the database into a plurality of tiers based on a ranking of the pages. The ranking may be based on portions of the pages which have a relatively higher value context. A processor produces a plurality of sub-indices from the primary index based on the mapping. The sub-indices are stored in a search node cluster. The cluster is a matrix of search nodes logically arranged in a plurality of rows and columns. Search nodes in the same column include the same sub-index. Search nodes in the same row include distinct sub-indices. A search query received by a user is sent to a dispatcher which, in turn, forwards the query to the first tier of search nodes. A fall through algorithm is disclosed which indicates when the dispatcher should forward the search query to other tiers of search nodes.

Claims

1. A method for indexing data items in a database, the method comprising:

retrieving data items associated with a respective ranking from a database, wherein the ranking is based at least in part on a relevance score for the data item;

mapping the data items on to at least a first tier and a second tier based on the respective rankings of the data items;

producing at least a first and a second sub-index from the primary index based on the mapping;

storing the first sub-index in a first plurality of search nodes logically arranged in a first plurality of columns; and

storing the second sub-index in a second plurality of search nodes logically arranged in a second plurality of columns.

2. The method as recited in claim 1, wherein the database is a collection of pages and documents available through the World Wide Web.

3. The method as recited in claim 1, further comprising:

executing a search query log for a number of queries on the database; and

receiving the results of the search query log;

wherein the first sub-index is based on the results of the query log.

4. The method as recited in claim 1, further comprising:

executing a search query log for a number of queries on the database; and

receiving the results of the search query log;

wherein the first sub-index is based on the results of the query log.

5. The method as recited in claim 1, wherein the mapping is based on a value context of the data items.

6. The method as recited in claim 1, wherein the data items are web pages and mapping is based on a relevance score of the web pages.

7. The method of claim 1, wherein the first and second sub-index are logically arranged in a respective plurality of logical rows.

8. A method for searching a database, the method comprising:

retrieving data items associated with a respective ranking from a database, wherein the ranking is based at least in part on a relevance score for the data item;

mapping data items on to at least a first tier and a second tier based on the respective rankings of the data items;

producing at least a first and a second sub-index from the primary index based on the mapping;

storing the first sub-index in a first plurality of search nodes logically arranged in a first plurality of columns;

storing the second sub-index in a second plurality of search nodes logically arranged in a second plurality of columns;

receiving a search query; and

searching the first tier for result data items relating to the search query and providing one or more of the result data items to a user.

9. The method as recited in claim 8, further comprising:

searching the second tier for the result data items relating to the search query when the first tier does not yield a threshold number of result data items.

10. The method as recited in claim 8, wherein the second tier is searched when the first tier does not yield a threshold number of result data items.

11. The method of claim 8, wherein the first and second sub-index are logically arranged in a respective plurality of logical rows.

12. A system for indexing a database, the system comprising:

a crawler which crawls the database to find data items;

an indexer which receives the data items associated with a respective ranking, wherein the ranking is based at least in part on a relevance score for the data item, produces a primary index;

a document mapping section which maps data items on to at least a first and a second tier based on the respective rankings of the data items;

a processor which produces at least a first and a second sub-index from the primary index based on the mapping;

a first plurality of search nodes logically arranged in a first plurality of columns for storing the first sub-index; and

a second plurality of search nodes logically arranged in a second plurality of columns for storing the second sub-index.

17. The system of claim 12, wherein the first and second sub-index are logically arranged in a respective plurality of logical rows.

13. A search engine comprising:

a crawler which crawls a database to find data items;

an indexer which receives the data items associated with a respective ranking wherein the ranking is based at least in part on a relevance score for the data item, produces a primary index;

a document mapping section which maps data items on to at least a first and a second tier based on the respective rankings of the data items;

a processor which produces at least a first and a second sub-index from the primary index based on the mapping;

a first plurality of search nodes logically arranged in a first plurality of columns for storing the first sub-index;

a second plurality of search nodes logically arranged in a second plurality of columns for storing the second sub-index; and

a dispatcher which receives a query and forwards the query to a search node in the first plurality of search nodes.

14. The search engine as recited in claim 13, wherein the first and second sub-index are logically arranged in a respective plurality of logical rows.

15. The search engine as recited in claim 13, wherein the dispatcher sends the query to the second tier when the first tier did not produce a thresholds number of result data items.

16. The search engine as recited in claim 13, wherein the dispatcher sends the query to the second tier when the first tier does not yield a threshold number of result data items.