Using Bloom Filters to Speed Up HITS-Like Ranking Algorithms Export

@incollection{citeulike:2303980, 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 efficiency (query-time speed) is substantially higher.}, author = {Gollapudi, Sreenivas and Najork, Marc and Panigrahy, Rina}, citeulike-article-id = {2303980}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-77004-6_16}, doi = {10.1007/978-3-540-77004-6_16}, journal = {Algorithms and Models for the Web-Graph}, keywords = {bloom, computation, fast, filters, hits}, pages = {195--201}, posted-at = {2008-12-03 10:53:46}, priority = {0}, title = {Using Bloom Filters to Speed Up HITS-Like Ranking Algorithms}, url = {http://dx.doi.org/10.1007/978-3-540-77004-6_16}, year = {2007} }

TY - CHAP ID - citeulike:2303980 L3 - citeulike-article-id:2303980 N2 - 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 efficiency (query-time speed) is substantially higher. JF - Algorithms and Models for the Web-Graph EP - 201 TI - Using Bloom Filters to Speed Up HITS-Like Ranking Algorithms SP - 195 KW - bloom KW - computation KW - fast KW - filters KW - hits AU - Gollapudi, Sreenivas AU - Najork, Marc AU - Panigrahy, Rina PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-77004-6_16 ER -