Skip-and-prune: cosine-based top-k query processing for efficient context-sensitive document retrieval

ABSTRACT

Keyword search and ranked retrieval together emerged as popular data access paradigms for various kinds of data, from web pages to XML and relational databases. A user can submit keywords without knowing much (sometimes nothing) about the complex structure underlying a data collection, yet the system can identify, rank, and return a set of relevant matches by exploiting statistics about the distribution and structure of the data. Keyword-based data models are also suitable for capturing user's search context in terms of weights associated to the keywords in the query. Given a search context, the data in the database can also be re-interpreted for semantically correct retrieval. This option, however, is often ignored as the cost of re-assessing the content in the database naively tends to be prohibitive. In this paper, we first argue that top-k query processing can help tackle this challenge by re-assessing only the relevant parts of the database, efficiently. A road-block in this process, however, is that most efficient implementations of top-k query processing assume that the scoring function is monotonic, whereas the cosine-based scoring function needed for re-interpretation of content based on user context is not. In this paper, we develop an efficient top-k query processing algorithm, skip-and-prune (SnP), which is able to process top-k queries under cosine-based non-monotonic scoring functions. We compare the use of proposed algorithm against the alternative implementations of the context-aware retrieval, including naive top-k, accumulator-based inverted files, and full-scan. The experiment results show that while being fast, naive top-k is not an effective solution due to the non-monotonicity of underlying scoring function. The proposed technique, SnP, however, matches the precision of accumulator-based inverted files and full-scan, yet it is orders of magnitude faster than these.

REFERENCES

• 1: S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer:a system for keyword-based search over relational databases. In ICDE, 2002.
• 2: Benjamin Arai , Gautam Das , Dimitrios Gunopulos , Nick Koudas, Anytime measures for top-k algorithms, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 3: Nilesh Bansal , Sudipto Guha , Nick Koudas, Ad-hoc aggregations of ranked lists in the presence of hierarchies, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376626]
• 4: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 5: A. J. Broder, Strategies for efficient incremental nearest neighbor search, Pattern Recognition, v.23 n.1-2, p.171-178, January 1990 [doi>10.1016/0031-3203(90)90057-R]
• 6: Kaushik Chakrabarti , Venkatesh Ganti , Jiawei Han , Dong Xin, Ranking objects based on relationships, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142516]
• 7: Tao Cheng , Xifeng Yan , Kevin Chen-Chuan Chang, EntityRank: searching entities directly and holistically, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 8: Sara Cohen , Jonathan Mamou , Yaron Kanza , Yehoshua Sagiv, XSEarch: a semantic search engine for XML, Proceedings of the 29th international conference on Very large data bases, p.45-56, September 09-12, 2003, Berlin, Germany
• 9: 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]
• 10: 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]
• 11: K. Fukunage , P. M. Narendra, A Branch and Bound Algorithm for Computing k-Nearest Neighbors, IEEE Transactions on Computers, v.24 n.7, p.750-753, July 1975 [doi>10.1109/T-C.1975.224297]
• 12: U. Guntzer, W. Balke, and W. Kiebling. Optimal Aggregation Algorithms for Middleware. In VLDB, 2000.
• 13: Donna Harman , R. Baeza-Yates , Edward Fox , W. Lee, Inverted files, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 14: Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999 [doi>10.1145/320248.320255]
• 15: Ihab F. Ilyas , Walid G. Aref , Ahmed K. Elmagarmid, Supporting top-K join queries in relational databases, Proceedings of the 29th international conference on Very large data bases, p.754-765, September 09-12, 2003, Berlin, Germany
• 16: S. Nepal and M. V. Ramakrishna. Query processing issues in image(multimedia)databases. In ICDE, 1999.
• 17: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 18: P. Resnik. Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language. JAIR, 11:95--130, 1999.
• 19: S. E Robertson and K. S Jones. Relevance weighting of search terms. JASIS, 27(3):129--146, 1976.
• 20: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 21: Gerard Salton , Edward A. Fox , Harry Wu, Extended Boolean information retrieval, Communications of the ACM, v.26 n.11, p.1022-1036, Nov. 1983 [doi>10.1145/182.358466]
• 22: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 23: Jian-Tao Sun , Hua-Jun Zeng , Huan Liu , Yuchang Lu , Zheng Chen, CubeSVD: a novel approach to personalized Web search, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060803]
• 24: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 25: Martin Theobald , Gerhard Weikum , Ralf Schenkel, Top-k query evaluation with probabilistic guarantees, Proceedings of the Thirtieth international conference on Very large data bases, p.648-659, August 31-September 03, 2004, Toronto, Canada
• 26: P. Tsaparas, N. Koudas and T. Palpanas. Ranked join indices. In ICDE, 2003.
• 27: Justin Zobel , Alistair Moffat , Kotagiri Ramamohanarao, Inverted files versus signature files for text indexing, ACM Transactions on Database Systems (TODS), v.23 n.4, p.453-490, Dec. 1998 [doi>10.1145/296854.277632]
• 28: ACM Digital Library. http://portal.acm.org.
• 29: ScienceDirect. http://www.sciencedirect.com.

INDEX TERMS

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

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

General Terms:
Experimentation, Performance

Keywords:
ranking, top-k