Sidlauskas, Darius6; Saltenis, Simonas1; Jensen, Christian Søndergaard3
1 Daisy - Center for Data-intensive Systems, The Faculty of Engineering and Science (ENG), Aalborg University, VBN2 Database and Programming Technologies, The Faculty of Engineering and Science (ENG), Aalborg University, VBN3 Department of Computer Science, The Faculty of Engineering and Science (ENG), Aalborg University, VBN4 The Faculty of Engineering and Science (TECH), Aalborg University, VBN5 CITS, The Faculty of Engineering and Science (ENG), Aalborg University, VBN6 Department of Computer Science, Aarhus University
The efficient processing of workloads that interleave moving-object updates and queries is challenging. In addition to the conflicting needs for update-efficient versus query-efficient data structures, the increasing parallel capabilities of multi-core processors yield challenges. To prevent concurrency anomalies and to ensure correct system behavior, conflicting update and query operations must be serialized. In this setting, it is a key concern to avoid that operations are blocked, which leaves processing cores idle. To enable efficient processing, we first examine concurrency degrees from traditional transaction processing in the context of our target domain and propose new semantics that enable a high degree of parallelism and ensure up-to-date query results. We define the new semantics for range and k-nearest neighbor queries. Then we present a main-memory indexing technique called PGrid that implements the proposed semantics as well as two other variants supporting different semantics. This enables us to quantify the effects different degrees of consistency have on performance. We also present an alternative time-partitioning approach. Empirical studies with the above and three existing proposals conducted on modern processors show that our proposals scale near-linearly with the number of hardware threads and thus are able to benefit from increasing on-chip parallelism.
V L D B Journal, 2014, Vol 23, Issue 5, p. 817-841