Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Using Bloom Filters to Speed Up HITS-like Ranking Algorithms

Sreenivas Gollapudi, Marc Najork, and Rina Panigrahy

Abstract

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.

Details

Publication typeInproceedings
Published in5th Workshop on Algorithms and Models for the Web Graph (WAW)
PublisherSpringer-Verlag
> Publications > Using Bloom Filters to Speed Up HITS-like Ranking Algorithms