Space-filling curves (SFCs) are widely used as dimensionality reduction techniques to enhance storage and query efficiency in database systems. Nevertheless, existing SFC-based index structures often operate under the assumption of a static workload, overlooking the necessity for dynamic SFC optimization in response to changing query patterns. This paper proposes adaptive piece-wise SFCs to address variations in query patterns. First, we define a KL-based indicator to measure the extent of variation in dynamic query workloads and develop a dual-rule adjustment trigger mechanism. Second, we implement dynamic adjustment utilizing bit-merging trees (BMTrees), which involves efficient filtering and generation of both data and query sets, as well as the construction and merging of local BMTrees. We evaluated the performance of Dya-BMTree using a synthetic dataset and two real datasets, comparing it with six state-of-the-art baselines. The results show that Dya-BMTree excels under dynamic load conditions, with reductions in query times and I/O costs reaching up to 50.22% and 45.03%, respectively.

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

Adaptive Piece-Wise Space-Filling Curves for Dynamic Query Workloads

  • Junshen Li,
  • Zhengyu Liao,
  • Wei Liang,
  • Zhonglong Zhang,
  • Shiyou Qian,
  • Guangtao Xue,
  • Jian Cao,
  • Xiaoshan Li

摘要

Space-filling curves (SFCs) are widely used as dimensionality reduction techniques to enhance storage and query efficiency in database systems. Nevertheless, existing SFC-based index structures often operate under the assumption of a static workload, overlooking the necessity for dynamic SFC optimization in response to changing query patterns. This paper proposes adaptive piece-wise SFCs to address variations in query patterns. First, we define a KL-based indicator to measure the extent of variation in dynamic query workloads and develop a dual-rule adjustment trigger mechanism. Second, we implement dynamic adjustment utilizing bit-merging trees (BMTrees), which involves efficient filtering and generation of both data and query sets, as well as the construction and merging of local BMTrees. We evaluated the performance of Dya-BMTree using a synthetic dataset and two real datasets, comparing it with six state-of-the-art baselines. The results show that Dya-BMTree excels under dynamic load conditions, with reductions in query times and I/O costs reaching up to 50.22% and 45.03%, respectively.