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: hd0cee266066cfd64
Venue: SIGMOD
Year: 2015
Pagerank: 6.8694751e-05
Overall Rank: 3,988 | 73.20%
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
282	Accelerating Machine Learning Inference with Probabilistic Predicates	2018	SIGMOD	0.00022302793
6,149	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	5.8683464e-05
7,152	Learning to Sample: Counting with Complex Queries	2020	VLDB	5.5959861e-05
7,320	Interactive Demonstration of Probabilistic Predicates	2018	SIGMOD	5.5521611e-05
9,389	JENNER: Just-in-time Enrichment in Query Processing	2022	VLDB	5.1843659e-05
9,834	AMNES: Accelerating the computation of data correlation using FPGAs	2023	VLDB	5.1225987e-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.00076265429
92	CrowdDB: Answering Queries with Crowdsourcing	2011	SIGMOD	0.00034670735
105	The MADlib Analytics Library or MAD Skills, the SQL	2012	VLDB	0.00033633007
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030462671
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027827605
248	Overview of SciDB: Large Scale Array Storage, Processing and Analysis	2010	SIGMOD	0.00023179865
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022713652
309	Approximate Query Processing Using Wavelets	2000	VLDB	0.00021376597
335	The Aqua Approximate Query Answering System	1999	SIGMOD	0.000206533
343	Model-Driven Data Acquisition in Sensor Networks	2004	VLDB	0.00020510274
372	Approximate Query Processing: Taming the TeraBytes! A Tutorial	2001	VLDB	0.0001971778
448	Histogram-Based Approximation of Set-Valued Query Answers	1999	VLDB	0.00018121533
564	Congressional Samples for Approximate Answering of Group-By Queries	2000	SIGMOD	0.00016297598
689	Query Optimization in the Presence of Foreign Functions	1993	VLDB	0.00014746059
850	The Design of an Acquisitional Query Processor For Sensor Networks	2003	SIGMOD	0.00013482116
930	Dynamic Sample Selection for Approximate Query Processing	2003	SIGMOD	0.00013009255
1,090	Scalable Approximate Query Processing With The DBO Engine	2007	SIGMOD	0.00012074369
1,663	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.942673e-05
2,035	Practical Predicate Placement	1994	SIGMOD	9.1519324e-05
2,326	Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies	2009	VLDB	8.628257e-05
2,430	Deco: A System for Declarative Crowdsourcing	2012	VLDB	8.4763599e-05
3,500	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.2506844e-05

Semantically Similar Papers

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