Moving Object Learned Index and Query Algorithm Based on Data Distribution
Author:
Affiliation:

Clc Number:

TP311

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The abundance of sources, ease of acquisition, and frequent movement of moving objects have led to exponential growth in data volume. The growing need for efficient management of moving object data has made indexing and querying such data a pressing issue. Traditional moving object indexes, based on spatial partitioning, can effectively handle changes in the spatial position and temporal dynamics of objects. However, due to the dynamic nature of moving objects, which require frequent index updates, maintaining these indexes becomes costly with large datasets. Learned indexes, as an emerging indexing technique, have the potential to improve query efficiency and reduce storage costs by leveraging machine learning methods. Nevertheless, learned indexes are not well-suited for data with multidimensional characteristics. To address this limitation, the proposed learned index uses the non-uniform grid code algorithm (NUGC_LI). It employs a recursive hierarchical model structure similar to the B+-tree, divided into root, internal, and leaf nodes. The learned index uses a multi-phase linear model to adapt to the flexibly divided data distribution, setting arrays with gaps and node key value ranges in the leaf nodes to improve node update and query efficiency. At the same time, B+-tree, RMI, ALEX, NUGC_LI, 3D R-tree, and TB-tree indexes are constructed for real taxi trajectories, system simulation train trajectories, and randomly generated trajectory datasets for comparison. The number of trajectory points in the real, simulated, and random datasets is approximately 917000, 51544, and 5222752, respectively. Through comparative experiments and scalability tests, NUGC_LI reduces the index construction time by approximately 91.45%, 89.63%, 90.38%, 87.46%, and 13.71% compared to TB-tree, 3D R-tree, B+-tree, RMI, and ALEX, respectively. For update operations, the update time is reduced by at least 93.76%. Range queries, nearest neighbor queries, and similar trajectory queries based on NUGC_LI show significant advantages under large-scale data conditions, with query times reduced by at least 8.74%, 30%, and 16.07% compared to ALEX; 29.38%, 77.44%, and 25.24% compared to RMI; 52.72%, 92.44%, and 70.5% compared to B+-tree; 53.09%, 91.2%, and 67.58% compared to 3D R-tree; and 52.67%, 90.43%, and 67.47% compared to TB-tree. The NUGC_LI index not only demonstrates high scalability under multi-task loads but also achieves significant performance improvements in construction, updates, and query operations.

    Reference
    Related
    Cited by
Get Citation

王撷阳,巢成,金鑫,许建秋,高云君.基于数据分布的移动对象学习索引及查询算法.软件学报,2026,37(5):2202-2234

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 28,2024
  • Revised:April 02,2025
  • Adopted:
  • Online: October 29,2025
  • Published: May 06,2026
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063