This paper compares the effectiveness of two well-known query-dependent link-based ranking algorithms,“Hyperlink-Induced Topic Search” (HITS) and the “Stochastic Approach for Link-Structure Analysis” (SALSA). The two algorithms are evaluated on a very large web graph induced by 463 million crawled web pages and a set of 28,043 queries and 485,656 results labeled by human judges. We employed three different performance measures – mean average precision (MAP), mean reciprocal rank (MRR), and normalized discounted cumulative gain (NDCG). We found that as an isolated feature, SALSA substantially outperforms HITS. This is quite surprising, given that the two algorithms operate over the same neighborhood graph induced by the query result set. We also studied the combination of SALSA and HITS with BM25F, a state-of-the-art text-based scoring function that incorporates anchor text. We found that the combination of SALSA and BM25F outperforms the combination of HITS and BM25F. Finally, we broke down our query set by query specificity, and found that SALSA (and to a lesser extent HITS) is most effective for general queries.
|Published in||16th ACM Conference on Information and Knowledge Management (CIKM)|
|Publisher||Association for Computing Machinery, Inc.|
Copyright © 2007 by the Association for Computing Machinery, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or email@example.com. The definitive version of this paper can be found at ACM’s Digital Library --http://www.acm.org/dl/.