Exploiting Correlations for Expensive Predicate Evaluation

Summary: Proposes cost-aware techniques for evaluating selection queries with UDF predicates by exploiting correlations and prior probabilities to meet user-specified precision/recall constraints. The methods handle known, noisy, or unknown probabilities, generalize to complex queries, and deliver up to 80% UDF savings with modest accuracy loss on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4997
Venue: SIGMOD
Year: 2015
Pagerank: 7.0055154e-05
Overall Rank: 3,945 | 72.94%
DOI: 10.1145/2723372.2723715

Incoming Non-self Citations Over Time

Authors

1. Manas Joglekar (Stanford University)
2. Hector Garcia-Molina (Stanford University)
3. Aditya Parameswaran (University of Illinois Urbana-Champaign)
4. Christopher Re (Stanford University)

BibTeX Citation

@inproceedings{joglekar_sigmod15,
        title = {{Exploiting Correlations for Expensive Predicate Evaluation}},
        author = {Joglekar, Manas and Garcia-Molina, Hector and Parameswaran, Aditya and Re, Christopher},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2723715},
        url = {https://dl.acm.org/doi/10.1145/2723372.2723715},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00022238183
6,031	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	6.0007422e-05
7,048	Learning to Sample: Counting with Complex Queries	2020	VLDB	5.7178054e-05
7,176	Interactive Demonstration of Probabilistic Predicates	2018	SIGMOD	5.6816132e-05
9,200	JENNER: Just-in-time Enrichment in Query Processing	2022	VLDB	5.3058708e-05
9,648	AMNES: Accelerating the computation of data correlation using FPGAs	2023	VLDB	5.2430158e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
9	Online Aggregation	1997	SIGMOD	0.00077458002
90	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00034951786
106	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00033539462
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
239	Overview of SciDB: Large Scale Array Storage, Processing and Analysis	2010	SIGMOD	0.00023674329
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
307	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021792475
327	The Aqua Approximate Query Answering System	1999	SIGMOD	0.00021091539
337	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020783399
363	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0002005475
435	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.000185063
553	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016590619
677	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00015065909
828	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013769869
909	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013291205
1,064	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012336248
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
2,005	Practical Predicate Placement	1994	SIGMOD	9.3203144e-05
2,302	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.7808696e-05
2,409	Deco: A System for Declarative Crowdsourcing	2012	VLDB	8.6145078e-05
3,449	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.4074656e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,882	Demonstration of Accelerating Machine Learning Inference Queries with Correlative Proxy Models	2022	VLDB
2	4,481	Dynamically Optimizing Queries over Large Scale Data Platforms	2014	SIGMOD
3	3,162	Efficiently Approximating Selectivity Functions using Low Overhead Regression Models	2020	VLDB
4	6,009	Optimization of Conjunctive Predicates for Main Memory Column Stores	2016	VLDB
5	8,980	Optimization of Multi-Version Expensive Predicates	2007	SIGMOD
6	1,826	Optimizing Disjunctive Queries with Expensive Predicates	1994	SIGMOD
7	9,917	The UDFBench Benchmark for General-purpose UDF Queries	2025	VLDB
8	295	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD
9	2,465	Optimization of Queries with User-defined Predicates	1996	VLDB
10	8,096	Efficient Execution of User-Defined Functions in SQL Queries	2023	VLDB