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: ha50185cfee5ce0ab
Venue: VLDB
Year: 2009
Pagerank: 8.6292256e-05
Overall Rank: 2,329 | 84.35%
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
779	FITing-Tree: A Data-aware Index Structure	2019	SIGMOD	0.00014030069
868	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013354403
1,191	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011590153
2,238	Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations	2019	SIGMOD	8.7751619e-05
3,073	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6777283e-05
3,500	CORADD: Correlation Aware Database Designer for Materialized Views and Indexes	2010	VLDB	7.2534237e-05
3,988	Exploiting Correlations for Expensive Predicate Evaluation	2015	SIGMOD	6.871854e-05
5,267	Predicting Cost Amortization for Query Services	2011	SIGMOD	6.2016737e-05
5,854	Pando: Enhanced Data Skipping with Logical Data Partitioning	2023	VLDB	5.9708829e-05
5,869	Leveraging Application Data Constraints to Optimize Database-Backed Web Applications	2023	VLDB	5.9648445e-05
6,074	Exploiting Soft and Hard Correlations in Big Data Query Optimization	2016	VLDB	5.8946121e-05
6,147	Sia: Optimizing Queries using Learned Predicates	2021	SIGMOD	5.8710365e-05
7,702	UPI: A Primary Index for Uncertain Databases	2010	VLDB	5.4748399e-05
8,580	Conditional Cuckoo Filters	2021	SIGMOD	5.3100462e-05
9,827	AMNES: Accelerating the computation of data correlation using FPGAs	2023	VLDB	5.1249969e-05
11,067	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	4.9793485e-05
11,113	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	4.9793485e-05
11,511	PLAQUE: Automated Predicate Learning at Query Time	2024	SIGMOD	4.9793485e-05
12,178	HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration	2019	VLDB	4.9793485e-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
160	CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies	2004	SIGMOD	0.00027837289
267	Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports	2001	VLDB	0.00022722971
295	Towards Estimation Error Guarantees for Distinct Values	2000	PODS	0.00021914399
1,662	BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data	2003	VLDB	9.9465656e-05
3,945	A System for Semantic Query Optimization	1987	SIGMOD	6.9084876e-05
3,957	Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database	1999	VLDB	6.8991437e-05
4,250	Exploiting Constraint-Like Data Characterizations in Query Optimization	2001	SIGMOD	6.7027541e-05
5,600	Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps	2006	VLDB	6.0709132e-05

Semantically Similar Papers

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