Boolean + ranking: Querying a database by k-constrained optimization

Zhen Zhang, Seung Won Hwang, Kevin Chen-Chuan Chang, Min Wang, Christian A. Lang, Yuan Chi Chang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The wide spread of databases for managing structured data, compounded with the expanded reach of the Internet, has brought forward interesting data retrieval and analysis scenarios to RDBMS. In such settings, queries often take the form of k-constrained optimization, with a Boolean constraint and a numeric optimization expression as the goal function, retrieving only the top-k tuples. This paper proposes the concept of supporting such queries, as their nature implies, by a functional optimization machinery over the search space of multiple indices. To realize this concept, we combine the dual perspectives of discrete state search (from the view of indices) and continuous function optimization (from the view of goal functions). We present, as the marriage of the two perspectives, the OPT*framework, which encodes k-constrained optimization as an A*search over the composite space of multiple indices, driven by functional optimization for providing tight heuristics. By processing queries as optimization, OPT*significantly outperforms baseline approaches, with up to 3 orders of magnitude margins.

Original languageEnglish (US)
Title of host publicationSIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data
Pages359-370
Number of pages12
DOIs
StatePublished - Dec 1 2006
Event2006 ACM SIGMOD International Conference on Management of Data - Chicago, IL, United States
Duration: Jun 27 2006Jun 29 2006

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Other

Other2006 ACM SIGMOD International Conference on Management of Data
CountryUnited States
CityChicago, IL
Period6/27/066/29/06

Keywords

  • A
  • Constrained optimization
  • Index
  • Query processing
  • Search
  • Top-k query

ASJC Scopus subject areas

  • Software
  • Information Systems

Fingerprint Dive into the research topics of 'Boolean + ranking: Querying a database by k-constrained optimization'. Together they form a unique fingerprint.

  • Cite this

    Zhang, Z., Hwang, S. W., Chang, K. C-C., Wang, M., Lang, C. A., & Chang, Y. C. (2006). Boolean + ranking: Querying a database by k-constrained optimization. In SIGMOD 2006 - Proceedings of the ACM SIGMOD International Conference on Management of Data (pp. 359-370). (Proceedings of the ACM SIGMOD International Conference on Management of Data). https://doi.org/10.1145/1142473.1142515