EUVIMEDEUVIMED entdecken
Crossref

BMTree: Designing, Learning, and Updating Piecewise Space-Filling Curves for Multi-Dimensional Data Indexing

Jiangneng Li, Yuang Liu, Zheng Wang, Gao Cong, Cheng Long, Walid G. Aref, Han Mao Kiah, Bin Cui

IEEE Transactions on Knowledge and Data Engineering · 2026-09 · 38 (9) · 5692-5706

DOI: 10.1109/tkde.2026.3704959 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Knowledge and Data Engineering, 2026-09. Verfasst von Jiangneng Li und 7 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 56 Literaturangaben. Gefördert von: Ministry of Education - Singapore, Tier 1.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Space-filling curves (SFC, for short) have been widely applied to index multi-dimensional data, which first maps the data to one dimension, and then a one-dimensional indexing method, e.g., the B-tree indexes the mapped data. Existing SFCs adopt a single mapping scheme for the whole data space. However, a single mapping scheme often does not perform well on all the data space. In this paper, we propose a new type of SFC called piecewise SFCs that adopts different mapping schemes for different data subspaces. Specifically, we propose a data structure termed the Bit Merging tree (BMTree) that can generate data subspaces and their SFCs simultaneously, and achieve desirable properties of the SFC for the whole data space. Furthermore, we develop a reinforcement learning-based solution to build the BMTree, aiming to achieve excellent query performance. To update the BMTree efficiently when the distributions of data and/or queries change, we develop a new mechanism that achieves fast detection of distribution shifts in data and queries, and enables partial retraining of the BMTree. The retraining mechanism achieves performance enhancement efficiently since it avoids retraining the BMTree from scratch. Extensive experiments show the effectiveness and efficiency of the BMTree with the proposed learning-based methods.

Förderung

  • Ministry of Education - Singapore
  • Tier 1

Zitieren

APA

Li, J., Liu, Y., Wang, Z., Cong, G., Long, C., Aref, W. G., Kiah, H. M., & Cui, B. (2026). BMTree: Designing, Learning, and Updating Piecewise Space-Filling Curves for Multi-Dimensional Data Indexing. IEEE Transactions on Knowledge and Data Engineering, 38(9), 5692-5706. https://doi.org/10.1109/tkde.2026.3704959

Vancouver

Li J, Liu Y, Wang Z, Cong G, Long C, Aref WG, et al. BMTree: Designing, Learning, and Updating Piecewise Space-Filling Curves for Multi-Dimensional Data Indexing. IEEE Transactions on Knowledge and Data Engineering. 2026;38(9):5692-5706. doi:10.1109/tkde.2026.3704959

BibTeX
@article{Li2026,
  author = {Li, Jiangneng and Liu, Yuang and Wang, Zheng and Cong, Gao and Long, Cheng and Aref, Walid G. and Kiah, Han Mao and Cui, Bin},
  title = {BMTree: Designing, Learning, and Updating Piecewise Space-Filling Curves for Multi-Dimensional Data Indexing},
  journal = {IEEE Transactions on Knowledge and Data Engineering},
  year = {2026},
  volume = {38},
  number = {9},
  pages = {5692--5706},
  doi = {10.1109/tkde.2026.3704959}
}
Kostenlos starten →