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)
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,594 | RP*: A Family of Order-Preserving Scalable Distributed Data Structures | 1994 | VLDB | 8.2421304e-05 |
| 3,511 | Towards Self-Tuning Data Placement in Parallel Database Systems | 2000 | SIGMOD | 7.2414794e-05 |
| 5,558 | Guaranteeing Correctness and Availability in P2P Range Indices | 2005 | SIGMOD | 6.0829894e-05 |
| 13,263 | Finding Data in the Neighborhood | 1997 | VLDB | 4.9769913e-05 |
Previous
Page 1 / 1
Next
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,658 | Lazy Updates for Distributed Search Structure | 1993 | SIGMOD | 8.1597547e-05 |
| 3,534 | LH* — Linear Hashing for Distributed Files | 1993 | SIGMOD | 7.2220529e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 7,974 | Efficient B-tree Based Indexing for Cloud Data Processing | 2010 | VLDB |
| 2 | 1,583 | On the Design and Scalability of Distributed Shared-Data Databases | 2015 | SIGMOD |
| 3 | 6,587 | Efficient Search of Multidimensional B-Trees | 1995 | VLDB |
| 4 | 1,802 | A Heuristic Approach to Distributed Query Processing | 1982 | VLDB |
| 5 | 1,366 | Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks | 2019 | SIGMOD |
| 6 | 7,359 | Efficient Search in Very Large Databases | 1988 | VLDB |
| 7 | 9,792 | Memory-Efficient Search Trees for Database Management Systems | 2021 | SIGMOD |
| 8 | 2,658 | Lazy Updates for Distributed Search Structure | 1993 | SIGMOD |
| 9 | 3,178 | Extendible Hashing for Concurrent Operations and Distributed Data | 1983 | PODS |
| 10 | 3,757 | Parallel Algorithms for Constructing Range and Nearest-Neighbor Searching Data Structures | 2016 | PODS |