Database Paper Browser

Back to papers

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
9852
Venue
VLDB
Year
2009
Pagerank
8.0396876e-05
Overall Rank
2,841 | 80.26%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank Citing Paper Year Venue Pagerank
1,365 FITing-Tree: A Data-aware Index Structure 2019 SIGMOD 0.00012379754
1,464 Learning Multi-dimensional Indexes 2020 SIGMOD 0.0001184772
1,887 Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads 2021 VLDB 0.00010201938
2,868 Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations 2019 SIGMOD 7.9856878e-05
3,213 Predicting Cost Amortization for Query Services 2011 SIGMOD 7.3749055e-05
3,868 CORADD: Correlation Aware Database Designer for Materialized Views and Indexes 2010 VLDB 6.6786821e-05
3,923 Pushing Data-Induced Predicates Through Joins in Big-Data Clusters 2020 VLDB 6.6232068e-05
4,022 Exploiting Correlations for Expensive Predicate Evaluation 2015 SIGMOD 6.5185189e-05
6,177 Exploiting Soft and Hard Correlations in Big Data Query Optimization 2016 VLDB 5.1646971e-05
6,461 Pando: Enhanced Data Skipping with Logical Data Partitioning 2023 VLDB 5.0479786e-05
7,278 Sia: Optimizing Queries using Learned Predicates 2021 SIGMOD 4.7720613e-05
7,657 UPI: A Primary Index for Uncertain Databases 2010 VLDB 4.6821809e-05
8,499 Conditional Cuckoo Filters 2021 SIGMOD 4.4929219e-05
9,416 Leveraging Application Data Constraints to Optimize Database-Backed Web Applications 2023 VLDB 4.3399748e-05
9,440 AMNES: Accelerating the computation of data correlation using FPGAs 2023 VLDB 4.3389137e-05
10,335 Scalable Grid-based Computation of Kendall’s tau Correlation 2026 VLDB 4.1905499e-05
10,396 Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve 2025 SIGMOD 4.1905499e-05
10,953 PLAQUE: Automated Predicate Learning at Query Time 2024 SIGMOD 4.1905499e-05
11,688 HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration 2019 VLDB 4.1905499e-05
Previous Page 1 / 1 Next

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
224 CORDS: Automatic Discovery of Correlations and Soft Functional Dependencies 2004 SIGMOD 0.00032743209
316 Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports 2001 VLDB 0.00027981848
380 Towards Estimation Error Guarantees for Distinct Values 2000 PODS 0.00024943236
1,976 BHUNT: Automatic Discovery of Fuzzy Algebraic Constraints in Relational Data 2003 VLDB 9.8784644e-05
4,106 Exploiting Constraint-Like Data Characterizations in Query Optimization 2001 SIGMOD 6.4395338e-05
4,118 A System for Semantic Query Optimization 1987 SIGMOD 6.4313372e-05
4,403 Implementation of Two Semantic Query Optimization Techniques in DB2 Universal Database 1999 VLDB 6.2054188e-05
5,605 Approximate Encoding for Direct Access and Query Processing over Compressed Bitmaps 2006 VLDB 5.413565e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
11,688 HERMIT in Action: Succinct Secondary Indexing Mechanism via Correlation Exploration 2019 VLDB 4.1905499e-05
7,655 CORDS: Automatic Generation of Correlation Statistics in DB2 2004 VLDB 4.6830102e-05
6,673 Discovering Longest-lasting Correlation in Sequence Databases 2013 VLDB 4.962156e-05
6,177 Exploiting Soft and Hard Correlations in Big Data Query Optimization 2016 VLDB 5.1646971e-05
8,869 Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing 2010 VLDB 4.4277859e-05
1,098 Query Optimization In Compressed Database Systems 2001 SIGMOD 0.00014070252
5,767 Indexing Correlated Probabilistic Databases 2009 SIGMOD 5.3341473e-05
3,827 Correlation Sketches for Approximate Join-Correlation Queries 2021 SIGMOD 6.7195959e-05
3,564 Estimating Block Accesses When Attributes Are Correlated 1986 VLDB 6.9655849e-05
2,868 Designing Succinct Secondary Indexing Mechanism by Exploiting Column Correlations 2019 SIGMOD 7.9856878e-05