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: 9561
Venue: VLDB
Year: 2005
Pagerank: 5.5181056e-05
Overall Rank: 7,939 | 45.54%
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,517	Demonstration of the TrajStore System	2009	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
41	Fast Subsequence Matching in Time-Series Databases	1994	SIGMOD	0.00046675394
560	Indexing the Positions of Continuously Moving Objects	2000	SIGMOD	0.00016525569
896	On Indexing Mobile Objects	1999	PODS	0.0001334014
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
1,370	Towards an Analysis of Range Query Performance in Spatial Data Structures	1993	PODS	0.00010997795
2,375	Novel Approaches to the Indexing of Moving Object Trajectories	2000	VLDB	8.6753909e-05
2,853	Indexing Large Trajectory Data Sets With SETI*	2003	CIDR	8.0383547e-05
2,960	XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries	2001	VLDB	7.9182423e-05

Semantically Similar Papers

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