Harnessing epoch-based reclamation for efficient range queries Conference Paper


Author(s): Arbel Raviv, Maya; Brown, Trevor
Title: Harnessing epoch-based reclamation for efficient range queries
Title Series: PPoPP
Affiliation IST Austria
Abstract: Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous problems that limit their usefulness. For example, they impose high overhead or rely heavily on garbage collection. In this work, we show how to augment data structures with highly efficient range queries, without relying on garbage collection. We identify a property of epoch-based memory reclamation algorithms that makes them ideal for implementing range queries, and produce three algorithms, which use locks, transactional memory and lock-free techniques, respectively. Our algorithms are applicable to more data structures than previous work, and are shown to be highly efficient on a large scale Intel system.
Conference Title: PPoPP: Principles and Practice of Parallel Programming
Volume: 53
Issue 1
Conference Dates: February 24-28, 2018
Conference Location: Vienna, Austria
Publisher: ACM  
Date Published: 2018-02-10
Start Page: 14
End Page: 27
DOI: 10.1145/3178487.3178489
Open access: no
IST Austria Authors
  1. Trevor Brown
    2 Brown
Related IST Austria Work