Efficient and effective link analysis with precomputed salsa maps

ABSTRACT

SALSA is a link-based ranking algorithm that takes the result set of a query as input, extends the set to include additional neighboring documents in the web graph, and performs a random walk on the induced subgraph. The stationary probability distribution of this random walk, used as a relevance score, is significantly more effective for ranking purposes than popular query-independent link-based ranking algorithms such as PageRank. Unfortunately, this requires significant effort at query-time, to access the link graph and compute the stationary probability distribution. In this paper, we explore whether it is possible to perform most of the computation off-line, prior to the arrival of any queries. The off-line phase of our approach computes a "score map" for each node in the web graph by performing a SALSA-like algorithm on the neighborhood of that node and retaining the scores of the most promising nodes in the neighborhood graph. The on-line phase takes the results to a query, retrieves the score map of each result, and returns for each result a score that is the sum of the matching scores from each score map. We evaluated this algorithm on a collection of about 28,000 queries with partially labeled results, and found that it is significantly more effective than PageRank, although not quite as effective as SALSA. We also studied the trade-off between ranking effectiveness and space requirements.

REFERENCES

• 1: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations, Journal of Computer and System Sciences, v.60 n.3, p.630-659, June 2000 [doi>10.1006/jcss.1999.1690]
• 2: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceedings of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 3: S. Gollapudi, M. Najork and R. Panigrahy. Using Bloom filters to speed up HITS-like ranking algorithms. In Proc. of the 5th Workshop on Algorithms and Models for the Web Graph,pages 195--201, 2007.
• 4: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 5: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 6: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.387-401, June 2000
• 7: R. Lempel , S. Moran, SALSA: the stochastic approach for link-structure analysis, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.131-160, April 2001 [doi>10.1145/382979.383041]
• 8: G. Linden. Marissa Mayer at Web 2.0. Online at: http://glinden.blogspot.com/2006/11/marissa-mayer-at-web-20.html
• 9: Massimo Marchiori, The quest for correct information on the Web: hyper search engines, Computer Networks and ISDN Systems, v.29 n.8-13, p.1225-1235, Sep. 1997
• 10: F. McSherry and M. Najork. Computing information retrieval performance measures efficiently in the presence of tied scores. In 30th European Conference on Information Retrieval, pages 414--421, 2008.
• 11: Marc A. Najork , Hugo Zaragoza , Michael J. Taylor, Hits on the web: how does it compare?, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277823]
• 12: Marc A. Najork, Comparing the effectiveness of hits and salsa, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, November 06-10, 2007, Lisbon, Portugal [doi>10.1145/1321440.1321465]
• 13: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: bringing order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 14: H. Zaragoza, N. Craswell, M. Taylor, S. Saria, and S. Robertson. Microsoft Cambridge at TREC-13: Web and HARD tracks. In Proc. of the 13th Text Retrieval Conference, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Selection process

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
link-based ranking, retrieval performance, salsa, web search