<p>Multidimensional data are commonly indexed using space-filling curves (SFCs), which map data points from a multidimensional space to one-dimensional keys and store them in traditional index structures such as B<InlineEquation ID="IEq1"><EquationSource Format="TEX">\(^+\)</EquationSource><EquationSource Format="MATHML"><math><mmultiscripts><mrow /><mrow /><mo>+</mo></mmultiscripts></math></EquationSource></InlineEquation>-trees. However, most existing approaches adopt fixed mapping strategies, which struggle to adapt to complex data distributions and diverse query workloads, leading to degraded performance in high-dimensional or skewed settings. In this paper, we propose HSFC, a learned hybrid space-filling curve indexing framework that combines multi-level spatial partitioning with subspace-level curve optimization. HSFC first constructs a query-aware Multi-level Spatial Partitioning Tree (MSP-Tree) to recursively divide the global data space into localized subspaces. Within each subspace, a monotonic SFC is independently learned via Bayesian optimization, and a globally ordered one-dimensional key space is formed through prefix encoding mechanism from MSP-Tree. To further reduce false positives, we introduce a proactive query splitting strategy leveraging weight pruning that decomposes window queries into multiple subqueries with tighter projection intervals. Extensive experiments on the evaluated real-world and synthetic datasets show that HSFC outperforms the compared baselines, achieving 1.5<InlineEquation ID="IEq2"><EquationSource Format="TEX">\(\times \)</EquationSource><EquationSource Format="MATHML"><math><mo>×</mo></math></EquationSource></InlineEquation>–8.8<InlineEquation ID="IEq3"><EquationSource Format="TEX">\(\times \)</EquationSource><EquationSource Format="MATHML"><math><mo>×</mo></math></EquationSource></InlineEquation> reductions in query latency and 27%–88% reductions in false positives.</p>

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

An index structure based on learned hybrid space-filling curves

  • Jie Zhou,
  • Zhongbo Wu,
  • Huaiguang Song,
  • Meng Zeng,
  • Zhao Wu,
  • Min Wang

摘要

Multidimensional data are commonly indexed using space-filling curves (SFCs), which map data points from a multidimensional space to one-dimensional keys and store them in traditional index structures such as B\(^+\)+-trees. However, most existing approaches adopt fixed mapping strategies, which struggle to adapt to complex data distributions and diverse query workloads, leading to degraded performance in high-dimensional or skewed settings. In this paper, we propose HSFC, a learned hybrid space-filling curve indexing framework that combines multi-level spatial partitioning with subspace-level curve optimization. HSFC first constructs a query-aware Multi-level Spatial Partitioning Tree (MSP-Tree) to recursively divide the global data space into localized subspaces. Within each subspace, a monotonic SFC is independently learned via Bayesian optimization, and a globally ordered one-dimensional key space is formed through prefix encoding mechanism from MSP-Tree. To further reduce false positives, we introduce a proactive query splitting strategy leveraging weight pruning that decomposes window queries into multiple subqueries with tighter projection intervals. Extensive experiments on the evaluated real-world and synthetic datasets show that HSFC outperforms the compared baselines, achieving 1.5\(\times \)×–8.8\(\times \)× reductions in query latency and 27%–88% reductions in false positives.