Efficient Encodings for Document Ranking Vectors
Taher H. Haveliwala · 2002
The rapid growth of the Web has led to the development of many techniques for enhancing search rankings by us-ing precomputed numeric document attributes such as the estimated popularity or importance of Web pages. For e-cient keyword-search query processing over large document repositories, it is vital that these auxiliary attribute vec-tors, containing numeric per-document properties, be kept in main memory. When only a small number of attribute vectors are used by the system (e.g., a document-length vec-tor for implementing the cosine ranking scheme), a standard 4-byte, single-precision oating point representation for the numeric values suces. However, for richer search rank-ings, which incorporate additional numeric attributes (e.g., a set of page-importance estimates for each page), it becomes more dicult to maintain all of the auxiliary ranking vec-tors in main memory. We propose lossy encoding schemes based on scalar quantization that eciently encode auxil-iary numeric properties, such as PageRank, an estimate of page importance used by the Google search engine. Unlike standard scalar quantization algorithms, which concentrate on minimizing the numerical distortion caused by lossy en-codings, we seek to minimize the distortion of search-result rankings. 1.