This paper describes a technique for reducing the query-time cost of HITS-like ranking algorithm. The basic idea is to compute for each node in the web graph a summary of its immediate neighborhood (which is a query-independent operation and thus can be done off-line), and to approximate the neighborhood graph of a result set at query-time by combining the summaries of the result set nodes. This approximation of the query-specific neighborhood graph can then be used to perform query-dependent link-based ranking algorithms such as HITS and SALSA. We have evaluated our technique on a large web graph and a substantial set of queries with partially judged results, and found that its effectiveness (retrieval performance) is comparable to the original SALSA algorithm, while its effciency (query-time speed) is substantially higher.

}, author = {Sreenivas Gollapudi and Marc Najork and Rina Panigrahy}, booktitle = {5th Workshop on Algorithms and Models for the Web Graph (WAW)}, month = {December}, publisher = {Springer-Verlag}, title = {Using Bloom Filters to Speed Up HITS-like Ranking Algorithms}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=56911}, year = {2007}, }