Distributing a Search Tree Among a Growing Number of Processors

Summary: Proposes a scalable distributed search tree preserving ordered queries (range, nearest neighbor), overcoming limits of prior distributed linear-hashing variants. Empirical results show strong storage utilization and fast query performance at scale, highlighting the need for a formal theory of scalable distributed data structures. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2794
Venue: SIGMOD
Year: 1994
Pagerank: 6.9224298e-05
Overall Rank: 4,075 | 72.05%
DOI: 10.1145/191839.191891

Incoming Non-self Citations Over Time

Authors

1. Brigitte Kröll (ETH Zurich)
2. Peter Widmayer (ETH Zurich)

BibTeX Citation

@inproceedings{kroll_sigmod94,
        title = {{Distributing a Search Tree Among a Growing Number of Processors}},
        author = {Kröll, Brigitte and Widmayer, Peter},
        series = {{SIGMOD} '94},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/191839.191891},
        url = {https://dl.acm.org/doi/10.1145/191839.191891},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,552	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.4284603e-05
3,454	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.4001286e-05
5,417	Guaranteeing Correctness and Availability in P2P Range Indices	2005	SIGMOD	6.2255551e-05
12,967	Finding Data in the Neighborhood	1997	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,605	Lazy Updates for Distributed Search Structure	1993	SIGMOD	8.3494816e-05
3,465	LH* — Linear Hashing for Distributed Files	1993	SIGMOD	7.3910846e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,827	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB
2	1,772	A Heuristic Approach to Distributed Query Processing	1982	VLDB
3	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
4	1,637	On the Design and Scalability of Distributed Shared-Data Databases	2015	SIGMOD
5	1,342	Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks	2019	SIGMOD
6	7,342	Efficient Search in Very Large Databases	1988	VLDB
7	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
8	2,605	Lazy Updates for Distributed Search Structure	1993	SIGMOD
9	3,115	Extendible Hashing for Concurrent Operations and Distributed Data	1983	PODS
10	3,685	Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures	2016	PODS