Adaptive Range Filters for Cold Data: Avoiding Trips to Siberia

  • Karolina Alexiou ,
  • Donald Kossmann ,
  • Paul Larson

Proceedings of the VLDB Endowment, Vol. 6, No. 14Copyright 2013 VLDB Endowment 21508097/13/14... $ 10.00. |

Published by VLDB - Very Large Data Bases

Publication

Bloom filters are a great technique to test whether a key is not in a set of keys. This paper presents a novel data structure called ARF. In a nutshell, ARFs are for range queries what Bloom filters are for point queries. That is, an ARF can determine whether a set of keys does not contain any keys that are part of a specific range. This paper describes the principles and methods for efficient implementation of ARFs and presents the results of comprehensive experiments that assess the precision, space, and latency of ARFs. Furthermore, this paper shows how ARFs can be applied to a commercial database system that partitions data into hot and cold regions to optimize queries that involve only hot data.