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: 9155
Venue: VLDB
Year: 2004
Pagerank: 0.00012456657
Overall Rank: 1,347 | 90.64%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 14 of 14 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,092	E-Store: Fine-Grained Elastic Partitioning for Distributed Transaction Processing Systems	2015	VLDB	0.00014135961
2,240	BATON: A Balanced Tree Structure for Peer-to-Peer Networks	2005	VLDB	9.2201128e-05
2,261	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	9.1629995e-05
3,165	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4539655e-05
3,962	Guaranteeing Correctness and Availability in P2P Range Indices	2005	SIGMOD	6.5876809e-05
5,188	Using Partial Evaluation in Distributed Query Evaluation	2006	VLDB	5.6385696e-05
5,317	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5719038e-05
7,134	Incremental Elasticity For Array Databases	2014	SIGMOD	4.822331e-05
7,715	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	4.6699261e-05
7,809	Online Reorganization in Read Optimized MMDBS	2011	SIGMOD	4.6448758e-05
9,545	Indexing data-oriented overlay networks	2005	VLDB	4.3263737e-05
12,330	Adaptively Parallelizing Distributed Range Queries	2009	VLDB	4.1945683e-05
12,483	SQLB: A Query Allocation Framework for Autonomous Consumers and Providers	2007	VLDB	4.1945683e-05
12,484	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.1945683e-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
20	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00086459551
197	Data Placement In Bubba	1988	SIGMOD	0.00035201758
285	Automating Physical Database Design in a Parallel Database	2002	SIGMOD	0.0002899128
773	Multi-Dimensional Database Allocation for Parallel Data Warehouses	2000	VLDB	0.00016870159
1,680	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	0.00010931115
2,353	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.9752351e-05
2,462	A Performance Analysis of Alternative Multi-Attribute Declustering Strategies	1992	SIGMOD	8.7589902e-05
3,401	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.1400085e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
679	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.00018215154
3,821	Locality-aware Partitioning in Parallel Database Systems	2015	SIGMOD	6.7281515e-05
3,587	Increasing Availability in Partitioned Database Systems (extended abstract)	1984	PODS	6.9428835e-05
3,434	Efficient Bulk Insertion into a Distributed Ordered Table	2008	SIGMOD	7.0994919e-05
1,957	On the Design and Scalability of Distributed Shared-Data Databases	2015	SIGMOD	9.9598319e-05
12,330	Adaptively Parallelizing Distributed Range Queries	2009	VLDB	4.1945683e-05
5,380	Towards High Performance Peer-to-Peer Content and Resource Sharing Systems	2003	CIDR	5.5402489e-05
7,715	Query Centric Partitioning and Allocation for Partially Replicated Database Systems	2017	SIGMOD	4.6699261e-05
6,694	Optimal Splitters for Temporal and Multi-version Databases	2013	SIGMOD	4.9586454e-05
1,680	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	0.00010931115