Harnessing epoch-based reclamation for efficient range queries

M. Arbel Raviv, T.A. Brown, in:, ACM, 2018, pp. 14–27.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Author
;
Department
Series Title
PPoPP
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.
Publishing Year
Date Published
2018-02-10
Volume
53
Issue
1
Page
14 - 27
Conference
PPoPP: Principles and Practice of Parallel Programming
Conference Location
Vienna, Austria
Conference Date
2018-02-24 – 2018-02-28
IST-REx-ID

Cite this

Arbel Raviv M, Brown TA. Harnessing epoch-based reclamation for efficient range queries. In: Vol 53. ACM; 2018:14-27. doi:10.1145/3178487.3178489
Arbel Raviv, M., & Brown, T. A. (2018). Harnessing epoch-based reclamation for efficient range queries (Vol. 53, pp. 14–27). Presented at the PPoPP: Principles and Practice of Parallel Programming, Vienna, Austria: ACM. https://doi.org/10.1145/3178487.3178489
Arbel Raviv, Maya, and Trevor A Brown. “Harnessing Epoch-Based Reclamation for Efficient Range Queries,” 53:14–27. ACM, 2018. https://doi.org/10.1145/3178487.3178489.
M. Arbel Raviv and T. A. Brown, “Harnessing epoch-based reclamation for efficient range queries,” presented at the PPoPP: Principles and Practice of Parallel Programming, Vienna, Austria, 2018, vol. 53, no. 1, pp. 14–27.
Arbel Raviv M, Brown TA. 2018. Harnessing epoch-based reclamation for efficient range queries. PPoPP: Principles and Practice of Parallel Programming, PPoPP, vol. 53. 14–27.
Arbel Raviv, Maya, and Trevor A. Brown. Harnessing Epoch-Based Reclamation for Efficient Range Queries. Vol. 53, no. 1, ACM, 2018, pp. 14–27, doi:10.1145/3178487.3178489.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar
ISBN Search