利用覆盖区域设计与实现移动对象索引

doi:10.3778/j.issn.1673-9418.2010.01.007

计算机科学与探索 ›› 2010, Vol. 4 ›› Issue (1): 64-72.DOI: 10.3778/j.issn.1673-9418.2010.01.007

利用覆盖区域设计与实现移动对象索引

王波涛¹⁺，陈贺¹，马俊¹，喜连川优²，王国仁¹

1. 东北大学信息科学与工程学院，沈阳 110004
2. 东京大学生产技术研究所，东京 153-8505

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-01-15 发布日期:2010-01-15
通讯作者: 王波涛

Design and Implementation of Mobile Object Index Based on Covered Area

WANG Botao¹⁺， CHEN He¹， MA Jun¹， KITSUREGAWA Masaru²， WANG Guoren¹

1. College of Information Science and Engineering， Northeastern University， Shenyang 110004， China
2. Institute of Industrial Science， University of Toyko， Toyko 153-8505， Japan

Received:1900-01-01 Revised:1900-01-01 Online:2010-01-15 Published:2010-01-15
Contact: WANG Botao

摘要/Abstract

摘要： 对移动对象索引频繁更新问题进行了研究，提出了一种基于区域覆盖的空间索引结构虚拟网格四分树（virtual grid quadtree，VGQ）；通过索引移动对象所在的区域而非移动对象本身来减少由于移动对象位置的改变而引起的索引结构的改变，并给出了近似连续范围查询算法及增量和自底向上优化策略。实验结果表明，VGQ在查询效率和空间使用上是一种有效的索引方法。

关键词: 移动对象, 空间索引, 连续范围查询

Abstract: For the frequent updating problem of moving object index， virtual grid quadtree （VGQ） is proposed based on the covered areas of mobile objects， where the areas covered by mobile objects are indexed instead of the locations of mobile objects so as to reduce the number of update operations of index structure. Based on VGQ， one approximate continuous range query algorithm with incremental and bottom-up optimization is proposed. Evaluation results show that VGQ index is efficient with regard to the response time and index space.

Key words: mobile object, spatial index, continuous range query

中图分类号:

TP301

王波涛1+ ，陈贺1 ，马俊1 ，喜连川优2 ，王国仁1 . 利用覆盖区域设计与实现移动对象索引[J]. 计算机科学与探索, 2010, 4(1): 64-72.

WANG Botao¹⁺， CHEN He¹， MA Jun¹， KITSUREGAWA Masaru²， WANG Guoren¹. Design and Implementation of Mobile Object Index Based on Covered Area[J]. Journal of Frontiers of Computer Science and Technology, 2010, 4(1): 64-72.

[1]	高雅，江国华，秦小麟，王钟毓. 基于LSTM的移动对象位置预测算法[J]. 计算机科学与探索, 2019, 13(1): 23-34.
[2]	申金鑫，吴烨，陈荦，景宁. 面向空间在线分析的并行近似聚集查询[J]. 计算机科学与探索, 2018, 12(10): 1559-1570.
[3]	车庆首，李传文，张轶，邓庆绪. GAPI：GPU加速的移动对象并行索引方法[J]. 计算机科学与探索, 2017, 11(11): 1713-1722.
[4]	胡昱璞，牛保宁. 动态确定K值聚类算法的R-树空间索引构建[J]. 计算机科学与探索, 2016, 10(2): 173-181.
[5]	单观敏，董一鸿，何贤芒. 基于MapReduce的连续概率Skyline查询[J]. 计算机科学与探索, 2016, 10(2): 182-193.
[6]	李佳佳，王波涛，王国仁，黄山. 不确定移动对象的查询处理技术研究综述[J]. 计算机科学与探索, 2013, 7(12): 1057-1072.
[7]	曹金凤，董一鸿，王勇，钱江波，钟才明. 不确定移动对象概率Skyline集的查询更新[J]. 计算机科学与探索, 2012, 6(5): 443-455.
[8]	吴烨, 熊伟, 蔡蕾, 景宁. 面向多核处理器的空间数据库索引性能分析[J]. 计算机科学与探索, 2011, 5(8): 707-718.
[9]	李佳佳1 , 王波涛1+ , 陈东1 , 喜连川优2 , 王国仁1 . 分组移动对象的区域偏离监视算法*[J]. 计算机科学与探索, 2010, 4(9): 803-811.
[10]	赵亮1+ , 陈荦1 , 景宁1 , 廖巍2 , 钟志农1 . 道路网中的移动对象连续范围查询*[J]. 计算机科学与探索, 2010, 4(7): 617-628.
[11]	丁晓锋+,卢炎生,赵娜. 基于TPU-tree的Skyline分支定界查询算法[J]. 计算机科学与探索, 2009, 3(2): 162-172.
[12]	刘胤田1,2 ,刘应明1 ,徐开阔3 ,曾涛4 ,唐常杰3+ . 多维空间索引结构SHG-Tree[J]. 计算机科学与探索, 2009, 3(1): 68-90.

利用覆盖区域设计与实现移动对象索引

Design and Implementation of Mobile Object Index Based on Covered Area

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics