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: haa8827042c1a714a
Venue: PODS
Year: 1989
Pagerank: 7.274712e-05
Overall Rank: 3,471 | 76.67%
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,234	Multi-Disk B-trees	1991	SIGMOD	6.217296e-05
6,994	Semantic Complexity of Classes of Relational Queries and Query Independent Data Partitioning	1991	PODS	5.6266148e-05
7,055	CMD: A Multidimensional Declustering Method for Parallel Database Systems	1992	VLDB	5.6116467e-05
7,126	On the Optimality of Disk Allocation for Cartesian Product Files (Extended Abstract)	1990	PODS	5.601767e-05
13,358	Hamming Filter: A Dynamic Signature File Organization for Parallel Stores	1993	VLDB	4.9793485e-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
54	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00040499302
137	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00029722253
191	Data Placement In Bubba	1988	SIGMOD	0.00025700375

Semantically Similar Papers

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