Decomposition tree: a spatio-temporal indexing method for movement big data
Decomposition tree: a spatio-temporal indexing method for movement big data
复制标题
DOI：
10.1007/s10586-015-0475-3
复制
发表时间：
2015-12
期刊：
影响因子：
--
通讯作者：
Zhenwen He;Chonglong Wu;Gang Liu;Zufang Zheng;Yiping Tian
中科院分区：
文献类型：
--
作者：
Zhenwen He;Chonglong Wu;Gang Liu;Zufang Zheng;Yiping Tian
运动是一个复杂的过程，在空间和时间中不断演变。由运动对象产生的运动数据是大数据的一种，一直是科学、技术、经济和社会研究的焦点。运动数据库也是地理信息科学研究的前沿。为储存在移动数据库中的移动数据制定有效的存取方法至关重要。R树、四叉树、八叉树等树型索引结构由于其内部节点的空间开销较大，不适合对多维运动数据进行索引。此外，难以将它们用于对多维运动数据的并行访问，因为它们是分层结构，这在高维空间中具有严重的重叠问题。在本文中，我们提出了一种新的访问方法，分解树（D树），索引多维运动数据。D-tree是一种没有内部节点的虚拟树，通过基于整数移位运算的编码方法，可以高效地回答各种查询。实验结果表明，D-tree的空间开销和查询性能都优于其最著名的竞争对手上级。
Movement is a complex process that evolves through both space and time. Movement data generated by moving objects is a kind of big data, which has been a focus of research in science, technology, economics, and social studies. Movement database is also at the forefront of geographic information science research. Developing efficient access methods for movement data stored in movement databases is of critical importance. Tree-like indexing structures such as the R-tree, Quadtree, Octree are not suitable for indexing multi-dimensional movement data because they all have high space cost of their inner nodes. In addition, it is difficult to use them for parallel access to multi-dimensional movement data because they thereof, are in hierarchical structures, which have severe overlapping problems in high dimensional space. In this paper, we propose a novel access method, the Decomposition Tree (D-tree), for indexing multi-dimensional movement data. The D-tree is a virtual tree without inner nodes, instead, through an encoding method based on integer bit-shifting operation, and can efficiently answer a wide range of queries. Experimental results show that the space cost and query performance of D-tree are superior to its best known competitors.