Static score bucketing in inverted indexes

ABSTRACT

Maintaining strict static score order of inverted lists is a heuristic used by search engines to improve the quality of query results when the entire inverted lists cannot be processed. This heuristic, however, increases the cost of index generation and requires complex index build algorithms. In this paper, we study a new index organization based on static score bucketing. We show that this new technique significantly improves in index build performance while having minimal impact on the quality of search results.

REFERENCES

• 1: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 2: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing Top k Lists, SIAM Journal on Discrete Mathematics, v.17 n.1, p.134-160, 2003 [doi>10.1137/S0895480102412856]
• 3: M. Fontoura, A. Neumann, S. Rajagopalan, E. Shekita, and J. Zien. High performance index build algorithms for intranet search engines. In VLDB' 2004.
• 4: T. Haveliwala. Efficient encoding for document ranking vectors. In Proc. of 4th Int. Conference on Internet Computing, 2003.
• 5: Nicholas Lester , Justin Zobel , Hugh E. Williams, In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems, Proceedings of the 27th Australasian conference on Computer science, p.15-23, January 01, 2004, Dunedin, New Zealand
• 6: X. Long and T. Suel. Optimized query execution in large search engines with global page ordering. In Proc. of the 29th Int. Conf. on Very Large Databases, 2003.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Performance

Keywords:
indexing, search engines, static scoring