Using Bloom Filters to Speed Up HITS-Like Ranking Algorithms

@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}, comment = {For each page u in the web graph, a summary is computed, containing: * A bloom filter for a sample of in-links of size a (\~{}1000) * A sample of in-links of size b (\~{}5) * A bloom filter for a sample of out-links of size c (\~{}1000) * A sample of out-links of size d (\~{}5) The samples are done using consistent sampling. Bloom filters are variable-length. This speeds up the computation of the base set for HITS given a root set of results.}, doi = {http://dx.doi.org/10.1007/978-3-540-77004-6\_16}, journal = {Algorithms and Models for the Web-Graph}, keywords = {ranking, web-graph}, pages = {195--201}, posted-at = {2008-01-29 15:26:13}, 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 TI - Using Bloom Filters to Speed Up HITS-Like Ranking Algorithms JF - Algorithms and Models for the Web-Graph SP - 195 EP - 201 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. KW - ranking KW - web-graph N1 - For each page u in the web graph, a summary is computed, containing: * A bloom filter for a sample of in-links of size a (~1000) * A sample of in-links of size b (~5) * A bloom filter for a sample of out-links of size c (~1000) * A sample of out-links of size d (~5) The samples are done using consistent sampling. Bloom filters are variable-length. This speeds up the computation of the base set for HITS given a root set of results. 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 -