Range filters aim to efficiently determine the existence of elements within a specified range. They guarantee query results without false negatives. Due to such reliability, they are widely used in practical scenarios to avoid accessing empty ranges. Numerous studies have consistently demonstrated that range filters can significantly enhance the overall range query performance by preemptively filtering out empty ranges, thereby reducing I/O operations and computational overhead. This chapter introduces six representative range filters, detailing their implementation specifics and analyzing their theoretical performance.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Range Filters

  • Haipeng Dai,
  • Meng Li,
  • Guihai Chen

摘要

Range filters aim to efficiently determine the existence of elements within a specified range. They guarantee query results without false negatives. Due to such reliability, they are widely used in practical scenarios to avoid accessing empty ranges. Numerous studies have consistently demonstrated that range filters can significantly enhance the overall range query performance by preemptively filtering out empty ranges, thereby reducing I/O operations and computational overhead. This chapter introduces six representative range filters, detailing their implementation specifics and analyzing their theoretical performance.