A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing

Summary: Proposes a formal trajectory-splitting model to minimize spatio-temporal I/Os for MBR-based indices (R-trees) in range queries. Presents a dynamic-programming optimal-split algorithm and a linear-time near-optimal method for dynamic updates, with experiments showing efficiency gains in R-tree deployments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8c159d7b53497f82
Venue: VLDB
Year: 2005
Pagerank: 5.3942942e-05
Overall Rank: 8,107 | 45.50%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Slobodan Rasetic (University of Alberta)
2. Jörg Sander (University of Alberta)
3. James Elding (University of Alberta)
4. Mario A. Nascimento (University of Alberta)

BibTeX Citation

@article{rasetic_vldb05,
        title = {{A Trajectory Splitting Model for Efficient Spatio-Temporal Indexing}},
        author = {Rasetic, Slobodan and Sander, Jörg and Elding, James and Nascimento, Mario A.},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {934--945},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
12,807	Demonstration of the TrajStore System	2009	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
42	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00045773967
574	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016173068
926	On Indexing Mobile Objects	1999	PODS	0.00013047723
985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012685169
1,404	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010767648
2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.4897323e-05
2,911	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	7.8720638e-05
3,022	XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries	2001	VLDB	7.7417557e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
2	2,064	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB
3	9,503	Main-Memory Operation Buffering for Efficient R-Tree Update	2007	VLDB
4	10,048	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
5	9,100	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
6	3,658	Time-Parameterized Queries in Spatio-Temporal Databases	2002	SIGMOD
7	9,406	On Optimal Node Splitting for R-trees	1998	VLDB
8	985	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB
9	1,405	A Model for the Prediction of R-tree Performance	1996	PODS
10	2,421	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB