(Almost) Optimal Parallel Block Access for Range Queries

Summary: Tiling/striping scheme for multidimensional range queries on 2^q×2^q block grids with k=2^t disks that achieves at most ceil(m/k)+O(log k) parallel block accesses and extends to higher dimensions. Empirically within 0.5 of ceil(m/k) on average, worst-case +3; bound essentially optimal and extendable to some composite k. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1210
Venue: PODS
Year: 2000
Pagerank: 5.8212982e-05
Overall Rank: 6,619 | 54.59%
DOI: 10.1145/335168.335224

Incoming Non-self Citations Over Time

Authors

1. Mikhail J. Atallah (Purdue University)
2. Sunil Prabhakar (Purdue University)

BibTeX Citation

@inproceedings{atallah_pods00,
        address = {New York, NY, USA},
        series = {{PODS} '00},
        title = {{(Almost) Optimal Parallel Block Access for Range Queries}},
        url = {https://dl.acm.org/doi/10.1145/335168.335224},
        doi = {10.1145/335168.335224},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Atallah, Mikhail J. and Prabhakar, Sunil},
        year = {2000}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,524	Adaptively Parallelizing Distributed Range Queries	2009	VLDB	5.093636e-05
12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS	5.093636e-05

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	7,207	A Scalable and Generic Approach to Range Joins	2022	VLDB
2	3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS
3	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
4	6,160	New Results on Two-dimensional Orthogonal Range Aggregation in External Memory	2011	PODS
5	12,524	Adaptively Parallelizing Distributed Range Queries	2009	VLDB
6	2,341	Parallel R-trees	1992	SIGMOD
7	1,529	On Two-Dimensional Indexability and Optimal Range Search Indexing (Extended Abstract)	1999	PODS
8	9,417	Similarity Query Processing Using Disk Arrays	1998	SIGMOD
9	13,874	Replicated Declustering of Spatial Data	2004	PODS
10	12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS