Supporting Frequent Updates in R-Trees: A Bottom-Up Approach

Summary: Bottom-up R-tree updates for high-frequency, localized streams; avoids expensive top-down reorganization. Introduces a compact in-memory summary enabling direct node access and flexible global-to-local reorganization, delivering higher throughput and better queries. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9009
Venue: VLDB
Year: 2003
Pagerank: 5.9958252e-05
Overall Rank: 4,692 | 67.36%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,165	SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases	2004	SIGMOD	0.00013557822
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
1,917	A Generic Framework for Monitoring Continuous Spatial Queries over Moving Objects	2005	SIGMOD	0.0001009778
2,534	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.5890923e-05
6,202	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	5.1593242e-05
6,537	Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads	2012	SIGMOD	5.0235647e-05
6,742	AGILE: Adaptive Indexing for Context-Aware Information Filters	2005	SIGMOD	4.9432585e-05
6,819	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9158166e-05
9,258	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB	4.3690661e-05
12,411	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	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
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
56	Direct Spatial Search on Pictorial Databases Using Packed R-trees	1985	SIGMOD	0.00065631356
354	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00026137988
631	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00018935493
1,002	On Indexing Mobile Objects	1999	PODS	0.00014702555
2,499	The MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries	2001	VLDB	8.646204e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
8,767	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS	4.456315e-05
8,474	Adaptive Index Structures	2002	VLDB	4.5029015e-05
6,819	Workload-Aware Indexing of Continuously Moving Objects	2009	VLDB	4.9158166e-05
9,116	R-Tree Based Indexing of Now-Relative Bitemporal Data	1998	VLDB	4.3928853e-05
3,255	A Revised R*-tree in Comparison with Related Index Structures	2009	SIGMOD	7.3160522e-05
10,556	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	4.1945683e-05
7,054	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	4.8496866e-05
1,774	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	0.00010604097
9,258	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB	4.3690661e-05
12,411	Towards Efficient Main-Memory Use For Optimum Tree Index Update	2008	VLDB	4.1945683e-05