---
_id: '397'
abstract:
- lang: eng
  text: '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. '
alternative_title:
- PPoPP
article_processing_charge: No
author:
- first_name: Maya
  full_name: Arbel Raviv, Maya
  last_name: Arbel Raviv
- first_name: Trevor A
  full_name: Brown, Trevor A
  id: 3569F0A0-F248-11E8-B48F-1D18A9856A87
  last_name: Brown
citation:
  ama: 'Arbel Raviv M, Brown TA. Harnessing epoch-based reclamation for efficient
    range queries. In: Vol 53. ACM; 2018:14-27. doi:<a href="https://doi.org/10.1145/3178487.3178489">10.1145/3178487.3178489</a>'
  apa: 'Arbel Raviv, M., &#38; 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. <a href="https://doi.org/10.1145/3178487.3178489">https://doi.org/10.1145/3178487.3178489</a>'
  chicago: Arbel Raviv, Maya, and Trevor A Brown. “Harnessing Epoch-Based Reclamation
    for Efficient Range Queries,” 53:14–27. ACM, 2018. <a href="https://doi.org/10.1145/3178487.3178489">https://doi.org/10.1145/3178487.3178489</a>.
  ieee: '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.'
  ista: '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.'
  mla: Arbel Raviv, Maya, and Trevor A. Brown. <i>Harnessing Epoch-Based Reclamation
    for Efficient Range Queries</i>. Vol. 53, no. 1, ACM, 2018, pp. 14–27, doi:<a
    href="https://doi.org/10.1145/3178487.3178489">10.1145/3178487.3178489</a>.
  short: M. Arbel Raviv, T.A. Brown, in:, ACM, 2018, pp. 14–27.
conference:
  end_date: 2018-02-28
  location: Vienna, Austria
  name: 'PPoPP: Principles and Practice of Parallel Programming'
  start_date: 2018-02-24
date_created: 2018-12-11T11:46:14Z
date_published: 2018-02-10T00:00:00Z
date_updated: 2023-09-11T14:10:25Z
day: '10'
department:
- _id: DaAl
doi: 10.1145/3178487.3178489
external_id:
  isi:
  - '000446161100002'
intvolume: '        53'
isi: 1
issue: '1'
language:
- iso: eng
month: '02'
oa_version: None
page: 14 - 27
publication_identifier:
  isbn:
  - 978-1-4503-4982-6
publication_status: published
publisher: ACM
publist_id: '7430'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Harnessing epoch-based reclamation for efficient range queries
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 53
year: '2018'
...