Boolean + Ranking: Querying a Database by K-Constrained Optimization

Summary: Proposes OPT* for k-constrained optimization: Boolean constraint + numeric objective in RDBMS. It merges discrete index-space search with continuous optimization, framing queries as A* search over multi-index states with tight heuristics, achieving up to 3 orders of magnitude speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h958d25caca1129ca
Venue: SIGMOD
Year: 2006
Pagerank: 5.5089205e-05
Overall Rank: 7,497 | 49.60%
DOI: 10.1145/1142473.1142515

Incoming Non-self Citations Over Time

Authors

1. Zhen Zhang (University of Illinois Urbana-Champaign)
2. Seung-won Hwang (Pohang University of Science and Technology)
3. Kevin Chen-Chuan Chang (University of Illinois Urbana-Champaign)
4. Min Wang (IBM)
5. Christian A. Lang (IBM)
6. Yuan-chi Chang (IBM)

BibTeX Citation

@inproceedings{zhang_sigmod06,
        title = {{Boolean + Ranking: Querying a Database by K-Constrained Optimization}},
        author = {Zhang, Zhen and Hwang, Seung-won and Chang, Kevin Chen-Chuan and Wang, Min and Lang, Christian A. and Chang, Yuan-chi},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142515},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142515},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,566	Progressive and Selective Merge: Computing Top-K with Ad-hoc Ranking Functions	2007	SIGMOD	7.2015969e-05
7,339	Sum-Max Monotonic Ranked Joins for Evaluating Top-K Twig Queries on Weighted Data Graphs	2007	VLDB	5.5490881e-05
8,189	Distributed Threshold Querying of General Functions by a Difference of Monotonic Representation	2011	VLDB	5.3810913e-05
9,288	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB	5.2021887e-05
12,659	Exact Indexing for Support Vector Machines	2011	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010679641
111	Optimizing Multi-Feature Queries for Image Databases	2000	VLDB	0.00032675259
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026835705
507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017101297
686	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00014775707
838	Minimal Probing: Supporting Expensive Predicates for Top-k Queries	2002	SIGMOD	0.00013550235
961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001282305
1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD	0.00010275036
1,773	Rank-aware Query Optimization	2004	SIGMOD	9.6719067e-05
14,406	SPIRE: A Progressive Content-Based Spatial Image Retrieval Engine	2000	SIGMOD	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	272	An Overview of Query Optimization in Relational Systems	1998	PODS
2	3,338	On the Complexity of Query Result Diversification	2013	VLDB
3	1,773	Rank-aware Query Optimization	2004	SIGMOD
4	7,855	Constrained Optimalities in Query Personalization	2005	SIGMOD
5	6,520	Query Refinement for Diverse Top-k Selection	2024	SIGMOD
6	2,591	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB
7	12,599	Optimal Top-k Generation of Attribute Combinations based on Ranked Lists	2012	SIGMOD
8	643	Evaluating Top-k Selection Queries	1999	VLDB
9	9,288	A General Framework for Modeling and Processing Optimization Queries	2007	VLDB
10	961	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD