Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads

Summary: PGrid—an in-memory grid index for moving objects—exploits multi-core parallelism to handle high-rate workloads. Updates and queries share a single data structure, avoiding snapshots; hardware-assisted atomic updates with object-level copying implement non-divisible updates, delivering fresh results and near-linear scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4572
Venue: SIGMOD
Year: 2012
Pagerank: 5.865078e-05
Overall Rank: 6,488 | 55.49%
DOI: 10.1145/2213836.2213842

Incoming Non-self Citations Over Time

Authors

1. Darius Šidlauskas (Aalborg University)
2. Simonas Šaltenis (Aalborg University)
3. Christian S. Jensen (Aarhus University)

BibTeX Citation

@inproceedings{sidlauskas_sigmod12,
        title = {{Parallel Main-Memory Indexing for Moving-Object Query and Update Workloads}},
        author = {Šidlauskas, Darius and Šaltenis, Simonas and Jensen, Christian S.},
        series = {{SIGMOD} '12},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2213836.2213842},
        url = {https://dl.acm.org/doi/10.1145/2213836.2213842},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,987	Progressive Top-K Nearest Neighbors Search in Large Road Networks	2020	SIGMOD	6.0183678e-05
7,070	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.7116663e-05
9,739	Waffle: In-memory Grid Index for Moving Objects with Reinforcement Learning-based Configuration Tuning System	2022	VLDB	5.227679e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
68	The End of an Architectural Era (It’s Time for a Complete Rewrite)	2007	VLDB	0.00038446206
957	The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries	2003	VLDB	0.00012962576
1,710	Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems	2001	VLDB	9.9537123e-05
1,978	Optimizing Multidimensional Index Trees for Main Memory Access	2001	SIGMOD	9.3627341e-05
2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB	9.2983514e-05
2,227	Concurrency and Recovery in Generalized Search Trees	1997	SIGMOD	8.9111106e-05
2,254	STRIPES: An Efficient Index for Predicted Trajectories	2004	SIGMOD	8.8603695e-05
3,057	High-Concurrency Locking in R-Trees	1995	VLDB	7.807389e-05
4,569	Supporting Frequent Updates in R-Trees: A Bottom-Up Approach	2003	VLDB	6.6255507e-05
5,740	A Benchmark for Evaluating Moving Object Indexes	2008	VLDB	6.1035012e-05
5,809	Logical and Physical Versioning in Main Memory Databases	1997	VLDB	6.0801663e-05
7,681	Efficient Concurrency Control in Multidimensional Access Methods	1999	SIGMOD	5.5683442e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,492	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD
2	3,741	Spatial Online Sampling and Aggregation	2016	VLDB
3	12,334	MOIST: A Scalable and Parallel Moving Object Indexer with School Tracking	2012	VLDB
4	6,619	(Almost) Optimal Parallel Block Access for Range Queries	2000	PODS
5	12,324	A Moving-Object Index for Efficient Query Processing with Peer-Wise Location Privacy	2012	VLDB
6	9,322	An Adaptive Updating Protocol for Reducing Moving Object Database Workload	2010	VLDB
7	4,740	An Experimental Analysis of Iterated Spatial Joins in Main Memory	2013	VLDB
8	6,012	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD
9	6,669	Spatial Joins in Main Memory: Implementation Matters!	2015	VLDB
10	2,020	Query and Update Efficient B+-Tree Based Indexing of Moving Objects	2004	VLDB