Parallel main-memory indexing for moving-object query and update workloads

Darius Sidlauskas, Simonas Saltenis, Christian Søndergaard Jensen

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

40 Citations (Scopus)

Abstract

We are witnessing a proliferation of Internet-worked, geo-positioned mobile
devices such as smartphones and personal navigation devices.
Likewise, location-related services that target the users of such devices are
proliferating. Consequently, server-side infrastructures are needed that are
capable of supporting the location-related query and update workloads generated by very large populations of such moving objects.

This paper presents a main-memory indexing technique that aims to support such workloads. The technique, called PGrid, uses a grid structure that is capable of exploiting the parallelism offered by modern processors. Unlike earlier proposals that maintain separate structures for updates and queries, PGrid allows both long-running queries and rapid updates to operate on a single data structure and thus offers up-to-date query results. Because PGrid does not rely on creating snapshots, it avoids the stop-the-world problem that occurs when workload processing is interrupted to perform such snapshotting.
Its concurrency control mechanism relies instead on hardware-assisted atomic
updates as well as object-level copying, and it treats updates as non-divisible
operations rather than as combinations of deletions and insertions; thus, the
query semantics guarantee that no objects are missed in query results.

Empirical studies demonstrate that PGrid scales near-linearly with the number of hardware threads on four modern multi-core processors. Since both updates and queries are processed on the same current data-store state, PGrid outperforms snapshot-based techniques in terms of both query freshness and CPU cycle-wise efficiency.
Original languageEnglish
Title of host publicationProceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012
Number of pages10
PublisherAssociation for Computing Machinery
Publication date2012
Pages37-48
ISBN (Print)978-1-4503-1247-9
DOIs
Publication statusPublished - 2012
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2012 - Scottsdale, Arizona, United States
Duration: 20 May 201224 May 2012

Conference

ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2012
CountryUnited States
CityScottsdale, Arizona
Period20/05/201224/05/2012

Fingerprint

Data storage equipment
Concurrency control
Copying
Smartphones
Computer hardware
Program processors
Data structures
Navigation
Servers
Semantics
Internet
Hardware
Processing

Cite this

Sidlauskas, D., Saltenis, S., & Jensen, C. S. (2012). Parallel main-memory indexing for moving-object query and update workloads. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012 (pp. 37-48). Association for Computing Machinery. https://doi.org/10.1145/2213836.2213842
Sidlauskas, Darius ; Saltenis, Simonas ; Jensen, Christian Søndergaard. / Parallel main-memory indexing for moving-object query and update workloads. Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012. Association for Computing Machinery, 2012. pp. 37-48
@inproceedings{5bb9fcbb72634921bec1525cc32bf702,
title = "Parallel main-memory indexing for moving-object query and update workloads",
abstract = "We are witnessing a proliferation of Internet-worked, geo-positioned mobiledevices such as smartphones and personal navigation devices.Likewise, location-related services that target the users of such devices areproliferating. Consequently, server-side infrastructures are needed that arecapable of supporting the location-related query and update workloads generated by very large populations of such moving objects.This paper presents a main-memory indexing technique that aims to support such workloads. The technique, called PGrid, uses a grid structure that is capable of exploiting the parallelism offered by modern processors. Unlike earlier proposals that maintain separate structures for updates and queries, PGrid allows both long-running queries and rapid updates to operate on a single data structure and thus offers up-to-date query results. Because PGrid does not rely on creating snapshots, it avoids the stop-the-world problem that occurs when workload processing is interrupted to perform such snapshotting.Its concurrency control mechanism relies instead on hardware-assisted atomicupdates as well as object-level copying, and it treats updates as non-divisibleoperations rather than as combinations of deletions and insertions; thus, thequery semantics guarantee that no objects are missed in query results.Empirical studies demonstrate that PGrid scales near-linearly with the number of hardware threads on four modern multi-core processors. Since both updates and queries are processed on the same current data-store state, PGrid outperforms snapshot-based techniques in terms of both query freshness and CPU cycle-wise efficiency.",
author = "Darius Sidlauskas and Simonas Saltenis and Jensen, {Christian S{\o}ndergaard}",
year = "2012",
doi = "10.1145/2213836.2213842",
language = "English",
isbn = "978-1-4503-1247-9",
pages = "37--48",
booktitle = "Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012",
publisher = "Association for Computing Machinery",
address = "United States",

}

Sidlauskas, D, Saltenis, S & Jensen, CS 2012, Parallel main-memory indexing for moving-object query and update workloads. in Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012. Association for Computing Machinery, pp. 37-48, ACM SIGMOD International Conference on Management of Data, SIGMOD 2012, Scottsdale, Arizona, United States, 20/05/2012. https://doi.org/10.1145/2213836.2213842

Parallel main-memory indexing for moving-object query and update workloads. / Sidlauskas, Darius; Saltenis, Simonas; Jensen, Christian Søndergaard.

Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012. Association for Computing Machinery, 2012. p. 37-48.

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - Parallel main-memory indexing for moving-object query and update workloads

AU - Sidlauskas, Darius

AU - Saltenis, Simonas

AU - Jensen, Christian Søndergaard

PY - 2012

Y1 - 2012

N2 - We are witnessing a proliferation of Internet-worked, geo-positioned mobiledevices such as smartphones and personal navigation devices.Likewise, location-related services that target the users of such devices areproliferating. Consequently, server-side infrastructures are needed that arecapable of supporting the location-related query and update workloads generated by very large populations of such moving objects.This paper presents a main-memory indexing technique that aims to support such workloads. The technique, called PGrid, uses a grid structure that is capable of exploiting the parallelism offered by modern processors. Unlike earlier proposals that maintain separate structures for updates and queries, PGrid allows both long-running queries and rapid updates to operate on a single data structure and thus offers up-to-date query results. Because PGrid does not rely on creating snapshots, it avoids the stop-the-world problem that occurs when workload processing is interrupted to perform such snapshotting.Its concurrency control mechanism relies instead on hardware-assisted atomicupdates as well as object-level copying, and it treats updates as non-divisibleoperations rather than as combinations of deletions and insertions; thus, thequery semantics guarantee that no objects are missed in query results.Empirical studies demonstrate that PGrid scales near-linearly with the number of hardware threads on four modern multi-core processors. Since both updates and queries are processed on the same current data-store state, PGrid outperforms snapshot-based techniques in terms of both query freshness and CPU cycle-wise efficiency.

AB - We are witnessing a proliferation of Internet-worked, geo-positioned mobiledevices such as smartphones and personal navigation devices.Likewise, location-related services that target the users of such devices areproliferating. Consequently, server-side infrastructures are needed that arecapable of supporting the location-related query and update workloads generated by very large populations of such moving objects.This paper presents a main-memory indexing technique that aims to support such workloads. The technique, called PGrid, uses a grid structure that is capable of exploiting the parallelism offered by modern processors. Unlike earlier proposals that maintain separate structures for updates and queries, PGrid allows both long-running queries and rapid updates to operate on a single data structure and thus offers up-to-date query results. Because PGrid does not rely on creating snapshots, it avoids the stop-the-world problem that occurs when workload processing is interrupted to perform such snapshotting.Its concurrency control mechanism relies instead on hardware-assisted atomicupdates as well as object-level copying, and it treats updates as non-divisibleoperations rather than as combinations of deletions and insertions; thus, thequery semantics guarantee that no objects are missed in query results.Empirical studies demonstrate that PGrid scales near-linearly with the number of hardware threads on four modern multi-core processors. Since both updates and queries are processed on the same current data-store state, PGrid outperforms snapshot-based techniques in terms of both query freshness and CPU cycle-wise efficiency.

UR - http://www.scopus.com/inward/record.url?scp=84862646917&partnerID=8YFLogxK

U2 - 10.1145/2213836.2213842

DO - 10.1145/2213836.2213842

M3 - Article in proceeding

SN - 978-1-4503-1247-9

SP - 37

EP - 48

BT - Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012

PB - Association for Computing Machinery

ER -

Sidlauskas D, Saltenis S, Jensen CS. Parallel main-memory indexing for moving-object query and update workloads. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2012. Association for Computing Machinery. 2012. p. 37-48 https://doi.org/10.1145/2213836.2213842