Top-k aggregation using intersections of ranked inputs

ABSTRACT

There has been considerable past work on efficiently computing top k objects by aggregating information from multiple ranked lists of these objects. An important instance of this problem is query processing in search engines: One has to combine information from several different posting lists (rankings) of web pages (objects) to obtain the top k web pages to answer user queries. Two particularly well-studied approaches to achieve efficiency in top-k aggregation include early-termination algorithms (e.g., TA and NRA) and preaggregation of some of the input lists. However, there has been little work on a rigorous treatment of combining these approaches.

We generalize the TA and NRA algorithms to the case when preaggregated intersection lists are available in addition to the original lists. We show that our versions of TA and NRA continue to remain "instance optimal," a very strong optimality notion that is a highlight of the original TA and NRA algorithms. Using an index of millions of web pages and real-world search engine queries, we empirically characterize the performance gains offered by our new algorithms. We show that the practical benefits of intersection lists can be fully realized only with an early-termination algorithm.

REFERENCES

• 1: Vo Ngoc Anh , Owen de Kretser , Alistair Moffat, Vector-space ranking with effective early termination, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.35-42, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383957]
• 2: Anh Ngoc Vo , Alistair Moffat, Compressed inverted files with reduced decoding overheads, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.290-297, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291011]
• 3: Vo Ngoc Anh , Alistair Moffat, Pruned query evaluation using pre-computed impacts, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148235]
• 4: B. Bhattacharjee, S. Chawathe, V. Gopalakrishnan, P. Keleher, and B. Silaghi. Efficient peer-to-peer searches using result-caching. In Proc. 2nd IWP2PS, 2003.
• 5: Chris Buckley , Alan F. Lewit, Optimization of inverted vector searches, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.97-110, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.253515]
• 6: Gautam Das , Dimitrios Gunopulos , Nick Koudas , Dimitris Tsirogiannis, Answering top-k queries using views, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: Ronald Fagin, Combining fuzzy information from multiple systems, Journal of Computer and System Sciences, v.58 n.1, p.83-99, Feb. 1999 [doi>10.1006/jcss.1998.1600]
• 8: Ronald Fagin, Combining fuzzy information: an overview, ACM SIGMOD Record, v.31 n.2, June 2002 [doi>10.1145/565117.565143]
• 9: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Journal of Computer and System Sciences, v.66 n.4, p.614-656, 1 June 2003 [doi>10.1016/S0022-0000(03)00026-6]
• 10: Ulrich Güntzer , Wolf-Tilo Balke , Werner Kießling, Optimizing Multi-Feature Queries for Image Databases, Proceedings of the 26th International Conference on Very Large Data Bases, p.419-428, September 10-14, 2000
• 11: D. Harman and G. Candela. Retrieving records from a gigabyte of text on a mini-computer using statistical ranking. JASIS, 41(8):581--589, 1990.
• 12: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 13: Xiaohui Long , Torsten Suel, Optimized query execution in large search engines with global page ordering, Proceedings of the 29th international conference on Very large data bases, p.129-140, September 09-12, 2003, Berlin, Germany
• 14: Xiaohui Long , Torsten Suel, Three-level caching for efficient query processing in large Web search engines, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060785]
• 15: Christopher D. Manning , Prabhakar Raghavan , Hinrich Schtze, Introduction to Information Retrieval, Cambridge University Press, New York, NY, 2008
• 16: Query Processing Issues in Image(Multimedia) Databases, Proceedings of the 15th International Conference on Data Engineering, p.22, March 23-26, 1999
• 17: Alexandros Ntoulas , Junghoo Cho, Pruning policies for two-tiered inverted index with correctness guarantee, 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.1277776]
• 18: Michael Persin , Justin Zobel , Ron Sacks-Davis, Filtered document retrieval with frequency-sorted indexes, Journal of the American Society for Information Science, v.47 n.10, p.749-764, Oct. 1996 [doi>10.1002/(SICI)1097-4571(199610)47:10<749::AID-ASI3>3.3.CO;2-U]
• 19: R. Schenkel, A. Broschart, S. Hwang, M. Theobald, and G. Weikum. Efficient text proximity search. In Proc. 14th SPIRE, pages 287--299, 2007.
• 20: A. Schrijver. Combinatorial Optimization. Springer, 2003.
• 21: David Carmel , Doron Cohen , Ronald Fagin , Eitan Farchi , Michael Herscovici , Yoelle S. Maarek , Aya Soffer, Static index pruning for information retrieval systems, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.43-50, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383958]
• 22: Howard Turtle , James Flood, Query evaluation: strategies and optimizations, Information Processing and Management: an International Journal, v.31 n.6, p.831-850, Nov. 1995 [doi>10.1016/0306-4573(95)00020-H]
• 23: Hugh E. Williams , Justin Zobel , Dirk Bahle, Fast phrase querying with combined indexes, ACM Transactions on Information Systems (TOIS), v.22 n.4, p.573-594, October 2004 [doi>10.1145/1028099.1028102]
• 24: I. H. Witten, A. Moffat, and T. C. Bell. Managing Gigabytes. Morgan Kaufmann, 1999.
• 25: Wai Yee Peter Wong , Dik Lun Lee, Implementations of partial document ranking using inverted files, Information Processing and Management: an International Journal, v.29 n.5, p.647-669, Sept.-Oct. 1993 [doi>10.1016/0306-4573(93)90085-R]
• 26: Jiangong Zhang , Torsten Suel, Efficient Query Evaluation on Large Textual Collections in a Peer-to-Peer Environment, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing, p.225-233, August 31-September 02, 2005 [doi>10.1109/P2P.2005.7]
• 27: J. Zhang and T. Suel. Optimized inverted list assignment in distributed search engine architectures. In Proc. 21st IPDPS, pages 1--10, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Experimentation, Theory

Keywords:
NRA, TA, early-termination, intersections