skip to main content
10.1145/1526709.1526846acmconferencesArticle/Chapter ViewAbstractPublication PagesthewebconfConference Proceedingsconference-collections
research-article

Answering approximate queries over autonomous web databases

Published: 20 April 2009 Publication History

Abstract

To deal with the problem of empty or too little answers returned from a Web database in response to a user query, this paper proposes a novel approach to provide relevant and ranked query results. Based on the user original query, we speculate how much the user cares about each specified attribute and assign a corresponding weight to it. This original query is then rewritten as an approximate query by relaxing the query criteria range. The relaxation order of all specified attributes and the relaxed degree on each specified attribute are varied with the attribute weights. For the approximate query results, we generate users' contextual preferences from database workload and use them to create a priori orders of tuples in an off-line preprocessing step. Only a few representative orders are saved, each corresponding to a set of contexts. Then, these orders and associated contexts are used at query time to expeditiously provide ranked answers. Results of a preliminary user study demonstrate that our query relaxation and results ranking methods can capture the user's preferences effectively. The efficiency and effectiveness of our approach is also demonstrated by experimental result.

References

[1]
Agrawal, R. and Rantzau, R. Context-sensitive ranking. In Proceedings of the SIGMOD Conference, 383--394, 2006.
[2]
Agrawal, R., Imielinski, T., and Swami, A. N. Mining association rules between sets of items in large databases. In Proceedings of the SIGMOD Conference, 207--216. 1993.
[3]
Agrawal, S., Chaudhuri, S., Das, G., and Gionis, A. Automated ranking of database query results. ACM Trans. Database Syst., 28(2): 140--174, 2003.
[4]
Bosc, P., Hadjali, A., and Pivert, O. Empty versus overabundant answers to flexible relational queries. Fuzzy Sets and Systems, 159, 1450--1467, 2007.
[5]
Chen, Z. Y. and Li, T. Addressing diverse user preferences in SQL-Query-Result navigation. In Proceedings of the SIGMOD Conference, 641--652, 2007.
[6]
Chakrabarti, K., Ganti, V., Han, J., and Xin, D. Ranking objects based on relationships. In Proceedings of the SIGMOD Conference, 371--382, 2006.
[7]
Chrobak, M., Keynon, C., and Young, N. The reverse greedy algorithm for the metric k-median problem. Information Processing Letters 97, 68--72, 2005.
[8]
Chaudhuri, S., Das, G., and Hristidis, V. Probabilistic information retrieval approach for ranking of database query results. ACM Trans. Database Syst., 31(3):1134--1168, 2006.
[9]
Chakrabarti, K., Chaudhuri, S., and Hwang, S. Automatic categorization of query results. In Proceedings of the SIGMOD Conference, 755--766, 2004.
[10]
Chomicki, J. Preference formulas in relational queries. ACM Trans. Database Syst., 28(4): 427--466, 2003.
[11]
Cohen, W. W., Schapire, R. E. Learning to order things. Journal of Artificial Intelligence Research, 10, 243--270, 1999.
[12]
Das, G., Hristidis, V., Kapoor, N., and Sudarshan, S. Ordering the attributes of query results. In Proceedings of the SIGMOD Conference, 395--406, 2006.
[13]
Fagin, R., Lotem, A., and Naor, M. Optimal aggregation algorithms for middleware. In Proceedings of the PODS Conference, 102--113, 2001.
[14]
Kiebling, W. Foundations of preferences in database systems. In Proceedings of the VLDB Conference, 311--322, 2002.
[15]
Ma, Z. M. and Yan, L. Generalization of strategies for fuzzy query translation in classical relational databases. Information and Software Technology, 49(2):172--180, 2007.
[16]
Nambiar, U. and Kambhampati, S. Answering imprecise queries over web databases. In Proceedings of the ICDE Conference, 45--54, 2006.
[17]
Ortega, B. M., Chakrabarti, K., and Mehrotra, S. An approach to integrating query refinement in SQL. In Proceedings of the EDBT Conference, 15--33, 2002.
[18]
Ortega, B. M. Integrating similarity based retrieval and query refinement in databases. Ph.D Dissertation, UIUC, 2003.
[19]
Muslea, I. Machine learning for online query relaxation. In Proceedings of the KDD Conference, 246--255, 2004.
[20]
Rui, Y., Huang, T. S., and Merhotra, S. Content-based image retrieval with relevance feedback in MARS. In Proceedings of the ICIP Conference, 815--818, 1997.
[21]
Stefanidis, K. and Pitoura, E. Adding context to preferences. In Proceedings of the ICDE Conference, 846--855, 2007.
[22]
Su, W., Wang, J., Huang, Q., and Lochovsky, F. Query result ranking over e-commerce web databases. In Proceedings of the CIKM Conference, 575--584, 2006.
[23]
Wu, L., Faloutsos, C., Sycara, K., and Payne, T. FALCON: feedback adaptive loop for content-based retrieval. In Proceedings of the VLDB Conference, 297--306, 2000.

Cited By

View all
  • (2024)Boolean interpretation, matching, and ranking of natural language queries in product selection systemsDiscover Computing10.1007/s10791-024-09432-x27:1Online publication date: 3-Apr-2024
  • (2022)Retrieving and Ranking Relevant Products from Boolean Natural Language Queries2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)10.1109/WI-IAT55865.2022.00051(303-308)Online publication date: Nov-2022
  • (2022)Answering Non-Answer Questions on Reverse Top-k Geo-Social Keyword QueriesJournal of Computer Science and Technology10.1007/s11390-022-2414-037:6(1320-1336)Online publication date: 30-Nov-2022
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
WWW '09: Proceedings of the 18th international conference on World wide web
April 2009
1280 pages
ISBN:9781605584874
DOI:10.1145/1526709

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 April 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. query relaxation
  2. query results ranking
  3. top-k.
  4. web database

Qualifiers

  • Research-article

Conference

WWW '09
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)1
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Boolean interpretation, matching, and ranking of natural language queries in product selection systemsDiscover Computing10.1007/s10791-024-09432-x27:1Online publication date: 3-Apr-2024
  • (2022)Retrieving and Ranking Relevant Products from Boolean Natural Language Queries2022 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT)10.1109/WI-IAT55865.2022.00051(303-308)Online publication date: Nov-2022
  • (2022)Answering Non-Answer Questions on Reverse Top-k Geo-Social Keyword QueriesJournal of Computer Science and Technology10.1007/s11390-022-2414-037:6(1320-1336)Online publication date: 30-Nov-2022
  • (2021)Automated Query Relaxation Mechanism for QoS-Aware Service ProvisioningArabian Journal for Science and Engineering10.1007/s13369-021-05978-w47:2(1717-1732)Online publication date: 18-Aug-2021
  • (2021)A third-party replication service for dynamic hidden databasesService Oriented Computing and Applications10.1007/s11761-020-00313-xOnline publication date: 8-Jan-2021
  • (2018)Item Retrieval as Utility EstimationThe 41st International ACM SIGIR Conference on Research & Development in Information Retrieval10.1145/3209978.3210053(795-804)Online publication date: 27-Jun-2018
  • (2017)Learning Effective Query Management Strategies from Big Data2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA)10.1109/ICMLA.2017.00-88(643-648)Online publication date: Dec-2017
  • (2017)Adaptive query relaxation and top-k result ranking over autonomous web databasesKnowledge and Information Systems10.1007/s10115-016-0982-451:2(395-433)Online publication date: 1-May-2017
  • (2016)Approximation and relaxation of semantic web path queriesWeb Semantics: Science, Services and Agents on the World Wide Web10.1016/j.websem.2016.08.00140:C(1-21)Online publication date: 1-Oct-2016
  • (2015)Adaptation of language model of information retrieval for empty answers problem in databases2015 12th International Symposium on Programming and Systems (ISPS)10.1109/ISPS.2015.7244977(1-7)Online publication date: Apr-2015
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media