Evaluating top-k queries over web-accessible databases

ABSTRACT

A query to a web search engine usually consists of a list of keywords, to which the search engine responds with the best or "top" k pages for the query. This top-k query model is prevalent over multimedia collections in general, but also over plain relational data for certain applications. For example, consider a relation with information on available restaurants, including their location, price range for one diner, and overall food rating. A user who queries such a relation might simply specify the user's location and target price range, and expect in return the best 10 restaurants in terms of some combination of proximity to the user, closeness of match to the target price range, and overall food rating. Processing top-k queries efficiently is challenging for a number of reasons. One critical such reason is that, in many web applications, the relation attributes might not be available other than through external web-accessible form interfaces, which we will have to query repeatedly for a potentially large set of candidate objects. In this article, we study how to process top-k queries efficiently in this setting, where the attributes for which users specify target values might be handled by external, autonomous sources with a variety of access interfaces. We present a sequential algorithm for processing such queries, but observe that any sequential top-k query processing strategy is bound to require unnecessarily long query processing times, since web accesses exhibit high and variable latency. Fortunately, web sources can be probed in parallel, and each source can typically process concurrent requests, although sources may impose some restrictions on the type and number of probes that they are willing to accept. We adapt our sequential query processing technique and introduce an efficient algorithm that maximizes source-access parallelism to minimize query response time, while satisfying source-access constraints. We evaluate our techniques experimentally using both synthetic and real web-accessible data and show that parallel algorithms can be significantly more efficient than their sequential counterparts.

REFERENCES

• 1: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 2: Blake, C. and Merz, C. 1998. UCI repository of machine learning databases. ftp://ftp.ics.uci.edu/pub/machine-learning-databases/covtype.
• 3: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, Top-k selection queries over relational databases: Mapping strategies and performance evaluation, ACM Transactions on Database Systems (TODS), v.27 n.2, p.153-187, June 2002 [doi>10.1145/568518.568519]
• 4: Amelie Marian, Evaluating Top-k Queries over Web-Accessible Databases, Proceedings of the 18th International Conference on Data Engineering, p.369, February 26-March 01, 2002
• 5: Michael J. Carey , Donald Kossmann, On saying “Enough already!” in SQL, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.219-230, May 11-15, 1997, Tucson, Arizona, United States
• 6: Michael J. Carey , Donald Kossmann, Reducing the Braking Distance of an SQL Query Engine, Proceedings of the 24rd International Conference on Very Large Data Bases, p.158-169, August 24-27, 1998
• 7: Kevin Chen-Chuan Chang , Seung-won Hwang, Minimal probing: supporting expensive predicates for top-k queries, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564731]
• 8: Surajit Chaudhuri , Luis Gravano, Optimizing queries over multimedia repositories, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.91-102, June 04-06, 1996, Montreal, Quebec, Canada
• 9: Surajit Chaudhuri , Luis Gravano , Amelie Marian, Optimizing Top-k Selection Queries over Multimedia Repositories, IEEE Transactions on Knowledge and Data Engineering, v.16 n.8, p.992-1009, August 2004 [doi>10.1109/TKDE.2004.30]
• 10: A Sampling-Based Estimator for Top-k Query, Proceedings of the 18th International Conference on Data Engineering, p.617, February 26-March 01, 2002
• 11: Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 12: Ronald Fagin, Combining fuzzy information from multiple systems (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.216-226, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237715]
• 13: Ronald Fagin , Amnon Lotem , Moni Naor, Optimal aggregation algorithms for middleware, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375567]
• 14: 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]
• 15: Freedman, D., Pisani, R., and Purves, R. 1997. Statistics. W.W. Norton & Company; 3rd edition.
• 16: Roy Goldman , Jennifer Widom, WSQ/DSQ: a practical approach for combined querying of databases and the Web, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.285-296, May 15-18, 2000, Dallas, Texas, United States
• 17: Gravano, L., Marian, A., and Bruno, N. 2002. Evaluating top-k queries over web-accessible databases. Tech. Rep., Columbia Univ., New York.
• 18: 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
• 19: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 20: Vagelis Hristidis , Nick Koudas , Yannis Papakonstantinou, PREFER: a system for the efficient execution of multi-parametric ranked queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.259-270, May 21-24, 2001, Santa Barbara, California, United States
• 21: A. Kemper , G. Moerkotte , K. Peithner , M. Steinbrunn, Optimizing disjunctive queries with expensive predicates, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.336-347, May 24-27, 1994, Minneapolis, Minnesota, United States
• 22: Mills, D. 1983. Internet delay experiments; RFC 889. In ARPANET Working Group Requests for Comments. Number 889. SRI International, Menlo Park, Calif.
• 23: Apostol Natsev , Yuan-Chi Chang , John R. Smith , Chung-Sheng Li , Jeffrey Scott Vitter, Supporting Incremental Join Queries on Ranked Inputs, Proceedings of the 27th International Conference on Very Large Data Bases, p.281-290, September 11-14, 2001
• 24: Query Processing Issues in Image(Multimedia) Databases, Proceedings of the 15th International Conference on Data Engineering, p.22, March 23-26, 1999
• 25: Michael Ortega , Yong Rui , Kaushik Chakrabarti , Kriengkrai Porkaew , Sharad Mehrotra , Thomas S. Huang, Supporting Ranked Boolean Similarity Queries in MARS, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.905-925, November 1998 [doi>10.1109/69.738357]
• 26: William H. Press , Saul A. Teukolsky , William T. Vetterling , Brian P. Flannery, Numerical recipes in C (2nd ed.): the art of scientific computing, Cambridge University Press, New York, NY, 1992

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
          Subjects: Retrieval models
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Measurement, Performance

Keywords:
Parallel query processing, query optimization, top-k query processing, web databases.