Davide Mottin
Abstract
We propose a principled optimization-based interactive query relaxation framework for queries that return no answers. Given an initial query that returns an empty answer set, our framework dynamically computes and suggests alternative queries with less conditions than those the user has initially requested, in order to help the user arrive at a query with a non-empty answer, or at a query for which no matter how many additional conditions are ignored, the answer will still be empty. Our proposed approach for suggesting query relaxations is driven by a novel probabilistic framework based on optimizing a wide variety of application-dependent objective functions. We describe optimal and approximate solutions of different optimization problems using the framework. We analyze these solutions, experimentally verify their efficiency and effectiveness, and illustrate their advantage over the existing approaches.
- S. Agrawal, S. Chaudhuri, G. Das, and A. Gionis. Automated ranking of database query results. In CIDR, 2003.Google Scholar
- A. Anagnostopoulos, L. Becchetti, C. Castillo, and A. Gionis. An optimization framework for query recommendation. In WSDM, pages 161-170, 2010. Google Scholar
- B. Arai, G. Das, D. Gunopulos, and N. Koudas. Anytime measures for top-k algorithms on exact and fuzzy data sets. VLDB J., 18(2):407-427, 2009. Google Scholar
- R. A. Baeza-Yates, C. A. Hurtado, and M. Mendoza. Query recommendation using query logs in search engines. In EDBT Workshops, pages 588-596, 2004. Google Scholar
- R. A. Baeza-Yates and B. A. Ribeiro-Neto. Modern Information Retrieval. Addison-Wesley New York, 2011. Google Scholar
- S. Basu Roy, H. Wang, G. Das, U. Nambiar, and M. Mohania. Minimum-effort driven dynamic faceted search in structured databases. In CIKM, pages 13-22, 2008. Google Scholar
- Y. M. M. Bishop, S. E. Fienberg, and P. W. Holland. Discr. Multivariate Analysis: Theory and Practice. MIT Press, 1975.Google Scholar
- A. Chapman and H. V. Jagadish. Why not? In SIGMOD, pages 523-534, 2009. Google Scholar
- S. Chaudhuri. Generalization and a framework for query modification. In ICDE, pages 138-145, 1990. Google Scholar
- S. Chaudhuri, G. Das, V. Hristidis, and G. Weikum. Probabilistic ranking of database query results. In VLDB, pages 888-899, 2004. Google Scholar
- S. Chaudhuri, G. Das, V. Hristidis, and G. Weikum. Probabilistic information retrieval approach for ranking of database query results. ACM Trans. Database Syst., 31(3):1134-1168, 2006. Google Scholar
- S. Gauch and J. Smith. Search improvement via automatic query reformulation. TOIS, 9(3):249-280, 1991. Google Scholar
- S. Gauch and J. B. Smith. An expert system for automatic query reformulation. JASIS, 44(3):124-136, 1993.Google Scholar
- V. Hristidis, Y. Hu, and P. G. Ipeirotis. Ranked queries over sources with boolean query interfaces without ranking support. In ICDE, pages 872-875, 2010.Google Scholar
- D. Jannach. Techniques for fast query relaxation in content-based recommender systems. KI'06: Advances in AI, pages 49-63, 2007. Google Scholar
- D. Jannach and J. Liegl. Conflict-directed relaxation of constraints in content-based recommender systems. Advances in Applied AI, pages 819-829, 2006. Google Scholar
- U. Junker. Quickxplain: Preferred explanations and relaxations for over-constrained problems. In AAAI, volume 4, pages 167-172, 2004. Google Scholar
- A. Kashyap, V. Hristidis, and M. Petropoulos. Facetor: cost-driven exploration of faceted query results. In CIKM, pages 719-728, 2010. Google Scholar
- N. Koudas, C. Li, A. K. H. Tung, and R. Vernica. Relaxing join and selection queries. In VLDB, pages 199-210, 2006. Google Scholar
- C. Li, N. Yan, S. B. Roy, L. Lisham, and G. Das. Facetedpedia: dynamic generation of query-dependent faceted interfaces for wikipedia. In WWW, pages 651-660, 2010. Google Scholar
- D. McSherry. Incremental relaxation of unsuccessful queries. In ECCBR, pages 331-345, 2004.Google Scholar
- C. Mishra and N. Koudas. Interactive query refinement. In EDBT, pages 862-873. ACM, 2009. Google Scholar
- T. M. Mitchell. Machine Learning. McGraw-Hill, 1997. Google Scholar
- Q. T. Tran and C.-Y. Chan. How to conquer why-not questions. In SIGMOD, pages 15-26, 2010. Google Scholar
- J.-R. Wen, J.-Y. Nie, and H. Zhang. Query clustering using user logs. ACM Trans. Inf. Syst., 20(1):59-81, 2002. Google Scholar
Index Terms
- A probabilistic optimization framework for the empty-answer problem
Recommendations
A holistic and principled approach for the empty-answer problem
We propose a principled optimization-based interactive query relaxation framework for queries that return no answers. Given an initial query that returns an empty-answer set, our framework dynamically computes and suggests alternative queries with fewer ...
Combining evidence with a probabilistic framework for answer ranking and answer merging in question answering
Question answering (QA) aims at finding exact answers to a user's question from a large collection of documents. Most QA systems combine information retrieval with extraction techniques to identify a set of likely candidates and then utilize some ...
Materializing views with minimal size to answer queries
PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsIn this paper we study the following problem. Given a database and a set of queries, we want to find, in advance, a set of views that can compute the answers to the queries, such that the size of the viewset (i.e., the amount of space, in bytes, ...
Comments