Search engine with hierarchically stored indices

• US 20050102270A1
• Filed: 11/10/2003
• Published: 05/12/2005
• Est. Priority Date: 11/10/2003
• Status: Active Grant

• Current Assignee: Jollify Management Limited
• Original Assignee: Overture Services Incorporated (Apollo Global Management, Inc.)
• Inventors: Pettersen, Havard, Egge, Tor, Aasheim, Yngve, Risvik, Knut Magne
• Granted Patent: US 7,240,064 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 from a database;

producing a primary index of the data items;

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

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

storing the at least a first and second sub-index in different search nodes.

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, wherein the mapping is based on a static relevance score of the data items.

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 3, 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.

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

7. 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.

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

retrieving data items from a database;

producing a primary index of the data items;

mapping data items on to at least a first tier and a second tier based on 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 at least a first and second sub-index in different search nodes;

receiving a search query; and

searching the first tier for result data items relating to the search query.

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. 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 and produces a primary index;

a document mapping section which maps data items on to at least a first and a second tier based on 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 search node which stores the first sub-index; and

a second search node which stores the second sub-index.

12. A search node cluster for enabling a search of a database, the cluster comprising:

search nodes logically arranged in a plurality of columns and plurality of rows;

all search nodes in any one of the columns including substantially the same information;

all search nodes in any one of the rows including distinct information;

the search nodes in the rows being logically divided into at least a first and a second tier;

the search nodes in the first tier including an index for a first portion of the database; and

the search nodes in the second tier including an index for a second portion of the database;

wherein

the data in the first and second tier is based on respective rankings of the information in the first and second portion of the database.

13. A search engine comprising:

a crawler which crawls a database to find data items;

an indexer which receives the data items and produces a primary index;

a document mapping section which maps data items on to at least a first and a second tier based on 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 search node which stores the first sub-index;

a second search node which stores the second sub-index; and

a dispatch which receives a query and forwards the query to the first search node.

14. The search engine as recited in claim 13, wherein the first sub-index is stored in a first plurality of search nodes logically arranged in a first plurality of columns;

and the second sub-index is stored in a second plurality of search nodes logically arranged in a second plurality of columns so that the first and second sub-index are further logically arranged in a respective plurality of logical rows.

15. The search engine as recited in claim 13, wherein the dispatch 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.