Replicated Declustering of Spatial Data

Summary: Identifies Omega(log N) unavoidable extra I/Os for single-copy declustering on spatial range queries and proposes using small replication to achieve strictly optimal parallel I/O for all range queries. Provides bounds on copies, introduces provably optimal "periodic allocations" for a-by-b grids and experimentally validates improvements over prior schemes. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1314
Venue: PODS
Year: 2004
Pagerank: -
Overall Rank: 13,874 | 4.82%
DOI: 10.1145/1055558.1055577

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Hakan Ferhatosmanoglu (Ohio State University)
2. Ali Saman Tosun (University of Texas at San Antonio)
3. Aravind Ramachandran (Ohio State University)

BibTeX Citation

@inproceedings{ferhatosmanoglu_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Replicated Declustering of Spatial Data}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055577},
        doi = {10.1145/1055558.1055577},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Ferhatosmanoglu, Hakan and Tosun, Ali Saman and Ramachandran, Aravind},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,915	CMD: A Multidimensional Declustering Method for Parallel Database Systems	1992	VLDB
2	13,098	A Tight Upper Bound on the Benefits of Replication and Consistency Control Protocols	1991	PODS
3	8,086	Load Balancing in a Locally Distributed Database System	1986	SIGMOD
4	8,703	Divergent Physical Design Tuning for Replicated Databases	2012	SIGMOD
5	3,754	An Adaptive Data Placement Scheme for Parallel Database Computer Systems	1990	VLDB
6	13,017	Optimal Response Time Retrieval of Replicated Data	1994	PODS
7	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
8	7,585	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD
9	12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS
10	8,472	Declustering Databases on Heterogeneous Disk Systems	1995	VLDB