Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems

Summary: Online, asymptotically optimal algorithms maintain storage balance for range-partitioned data under adversarial inserts/deletes across disks/nodes. With distributed routing, it enables range queries in P2P settings while preserving balance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: heba86eadb960d509
Venue: VLDB
Year: 2004
Pagerank: 0.00010554122
Overall Rank: 1,471 | 90.12%
DOI: 10.1016/B978-012088469-8.50041-3

Incoming Non-self Citations Over Time

Authors

1. Prasanna Ganesan (Stanford University)
2. Mayank Bawa (Stanford University)
3. Hector Garcia-Molina (Stanford University)

BibTeX Citation

@article{ganesan_vldb04,
        title = {{Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems}},
        author = {Ganesan, Prasanna and Bawa, Mayank and Garcia-Molina, Hector},
        journal = {PVLDB},
        series = {{VLDB} '04},
        pages = {444--455},
        doi = {10.1016/B978-012088469-8.50041-3},
        url = {https://doi.org/10.1016/B978-012088469-8.50041-3},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
891	E-Store: Fine-Grained Elastic Partitioning for Distributed Transaction Processing Systems	2015	VLDB	0.00013241227
2,330	BATON: A Balanced Tree Structure for Peer-to-Peer Networks	2005	VLDB	8.6260609e-05
2,412	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	8.5070443e-05
3,261	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4807048e-05
5,466	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.1192481e-05
5,558	Guaranteeing Correctness and Availability in P2P Range Indices	2005	SIGMOD	6.0829894e-05
5,594	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	6.0706959e-05
6,967	Incremental Elasticity For Array Databases	2014	SIGMOD	5.6301184e-05
7,712	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	5.4705892e-05
8,239	Online Reorganization in Read Optimized MMDBS	2011	SIGMOD	5.3696221e-05
9,892	Indexing data-oriented overlay networks	2005	VLDB	5.1145017e-05
12,820	Adaptively Parallelizing Distributed Range Queries	2009	VLDB	4.9769913e-05
12,972	SQLB: A Query Allocation Framework for Autonomous Consumers and Providers	2007	VLDB	4.9769913e-05
12,973	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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.00040482761
192	Data Placement In Bubba	1988	SIGMOD	0.00025689465
243	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.00023349603
1,002	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB	0.00012593352
2,289	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.6890827e-05
2,594	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.2421304e-05
2,651	A Performance Analysis of Alternative Multi-Attribute Declustering Strategies	1992	SIGMOD	8.1699714e-05
3,511	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.2414794e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	473	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
2	3,241	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD
3	4,940	Increasing Availability in Partitioned Database Systems (extended abstract)	1984	PODS
4	3,641	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD
5	1,583	On the Design and Scalability of Distributed Shared-Data Databases	2015	SIGMOD
6	12,820	Adaptively Parallelizing Distributed Range Queries	2009	VLDB
7	6,251	Towards High Performance Peer-to-Peer Content and Resource Sharing Systems	2003	CIDR
8	7,712	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD
9	6,559	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD
10	2,289	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR