Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies

Summary: Proposes Correlation Maps (CMs), a compressed access structure that exploits soft functional dependencies between a clustered attribute and unclustered predicates to localize lookups and cut random I/O. Bucketing domains makes CMs orders of magnitude smaller, enabling many CMs; an analytic cost model and automatic pair suggestions drive scalable, low-maintenance query acceleration, demonstrated on SDSS and TPC-H. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10042
Venue: VLDB
Year: 2009
Pagerank: 8.7808696e-05
Overall Rank: 2,302 | 84.21%
DOI: 10.14778/1687627.1687765

Incoming Non-self Citations Over Time

Authors

1. Hideaki Kimura (Brown University)
2. George Huo (Google)
3. Alexander Rasin (Brown University)
4. Samuel Madden (Massachusetts Institute of Technology)
5. Stanley B. Zdonik (Brown University)

BibTeX Citation

@article{kimura_vldb09,
        title = {{Correlation Maps: A Compressed Access Method for Exploiting Soft Functional Dependencies}},
        author = {Kimura, Hideaki and Huo, George and Rasin, Alexander and Madden, Samuel and Zdonik, Stanley B.},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687765},
        url = {https://doi.org/10.14778/1687627.1687765},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
790	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.0001401445
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.9410226e-05
3,137	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.7204167e-05
3,449	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.4074656e-05
3,945	Exploiting Correlations for Expensive Predicate Evaluation	2015	SIGMOD	7.0055154e-05
5,176	Predicting Cost Amortization for Query Services	2011	SIGMOD	6.3326746e-05
6,031	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	6.0007422e-05
6,042	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9970052e-05
6,044	Exploiting Soft and Hard Correlations in Big Data Query Optimization	2016	VLDB	5.995949e-05
7,553	UPI: A Primary Index for Uncertain Databases	2010	VLDB	5.6004812e-05
8,413	Conditional Cuckoo Filters	2021	SIGMOD	5.4306049e-05
9,561	Leveraging Application Data Constraints to Optimize Database-Backed Web Applications	2023	VLDB	5.2528121e-05
9,648	AMNES: Accelerating the computation of data correlation using FPGAs	2023	VLDB	5.2430158e-05
10,621	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	5.093636e-05
10,672	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	5.093636e-05
11,166	PLAQUE: Automated Predicate Learning at Query Time	2024	SIGMOD	5.093636e-05
11,878	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
159	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00028129426
255	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00023174541
288	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00022296371
1,648	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	0.00010120668
3,901	A System for Semantic Query Optimization	1987	SIGMOD	7.0317421e-05
3,928	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	7.0115196e-05
4,199	Exploiting Constraint-Like Data Characterizations in Query Optimization	2001	SIGMOD	6.8388774e-05
5,472	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.2058219e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,012	CORDS: Automatic Generation of Correlation Statistics in DB2	2004	VLDB
2	6,780	Discovering Longest-lasting Correlation in Sequence Databases	2013	VLDB
3	6,044	Exploiting Soft and Hard Correlations in Big Data Query Optimization	2016	VLDB
4	8,965	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB
5	921	Query Optimization In Compressed Database Systems	2001	SIGMOD
6	5,383	Compressed Representations of Conjunctive Query Results	2018	PODS
7	5,450	Indexing Correlated Probabilistic Databases	2009	SIGMOD
8	3,228	Correlation Sketches for Approximate Join-Correlation Queries	2021	SIGMOD
9	3,996	Estimating Block Accesses When Attributes Are Correlated	1986	VLDB
10	2,213	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD