Declustering Using Error Correcting Codes

Summary: Partition 2^n binary tuples into m disk groups by forming Error Correcting Codes so each group has large intra-group Hamming distance, maximizing parallelism for partial-match queries. Proves a necessary optimality condition and shows ECC declustering outperforms prior heuristics and is close to the theoretical bound. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 870
Venue: PODS
Year: 1989
Pagerank: 7.4414918e-05
Overall Rank: 3,403 | 76.66%
DOI: 10.1145/73721.73747

Incoming Non-self Citations Over Time

Authors

1. Christos Faloutsos (University of Maryland)
2. Dimitrios Metaxas (University of Maryland; University of Toronto)

BibTeX Citation

@inproceedings{faloutsos_pods89,
        address = {New York, NY, USA},
        series = {{PODS} '89},
        title = {{Declustering Using Error Correcting Codes}},
        url = {https://dl.acm.org/doi/10.1145/73721.73747},
        doi = {10.1145/73721.73747},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Faloutsos, Christos and Metaxas, Dimitrios},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,120	Multi-Disk B-trees	1991	SIGMOD	6.3577476e-05
6,847	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.7554494e-05
6,915	CMD: A Multidimensional Declustering Method for Parallel Database Systems	1992	VLDB	5.7404469e-05
6,986	On the Optimality of Disk Allocation for Cartesian Product Files (Extended Abstract)	1990	PODS	5.7303405e-05
13,068	Hamming Filter: A Dynamic Signature File Organization for Parallel Stores	1993	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
52	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00041107291
133	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00030370315
188	Data Placement In Bubba	1988	SIGMOD	0.00026126036

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,613	A Performance Analysis of Alternative Multi-Attribute Declustering Strategies	1992	SIGMOD
2	13,135	Clustered Multiattribute Hash Files	1989	PODS
3	13,068	Hamming Filter: A Dynamic Signature File Organization for Parallel Stores	1993	VLDB
4	6,915	CMD: A Multidimensional Declustering Method for Parallel Database Systems	1992	VLDB
5	4,533	The Idea of De-clustering and Its Applications	1986	VLDB
6	13,874	Replicated Declustering of Spatial Data	2004	PODS
7	2,742	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD
8	8,472	Declustering Databases on Heterogeneous Disk Systems	1995	VLDB
9	6,986	On the Optimality of Disk Allocation for Cartesian Product Files (Extended Abstract)	1990	PODS
10	12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS