基于分布式内存数据库的移动对象全时态索引

计算机科学 ›› 2016, Vol. 43 ›› Issue (7): 203-207.doi: 10.11896/j.issn.1002-137X.2016.07.037

基于分布式内存数据库的移动对象全时态索引

周翔宇,程春玲,杨雁莹

南京邮电大学计算机学院南京210003,南京邮电大学计算机学院南京210003,南京森林警察学院信息技术系南京210023

出版日期:2018-12-01 发布日期:2018-12-01
基金资助:
本文受中央高校基本科研业务费专项资金项目(LGZD201502),国家自然科学基金(61373139,61403208)资助

Full-temporal Index of Moving Objects Based on Distributed Main Memory Database

ZHOU Xiang-yu, CHENG Chun-ling and YANG Yan-ying

Online:2018-12-01 Published:2018-12-01

摘要/Abstract

摘要： 针对现有移动索引仅对内存/磁盘两层结构进行优化,忽略了索引节点在内存中的缓存敏感性,提出一种基于分布式内存数据库的全时态索引结构DFTB^x树。该索引结构针对存储器Cache、内存和磁盘3层结构进行优化,根据Cache行、指令数量和TLB失配数等多个条件设计内存索引节点的大小。同时,根据磁盘数据页的大小设计历史数据迁移链节点的大小,使得Cache和内存能够一次读取索引节点和迁移链节点数据,避免多次读取数据带来的延迟。此外,构建历史数据迁移链,实现历史数据持久化,从而支持移动对象全时态索引。实验结果表明:与B^x树、B^dual树、TPR*树和STRIPES算法相比,DFTB^x树具有较高的查询和更新效率。

关键词: 分布式内存数据库,移动对象,全时态索引,三层结构

Abstract: Due to the traditional index of moving objects ignores the cache-conscious of index nodes,only the two-layer memory/disk hierarchy is optimized.Thus,this paper proposed a novel full-temporal index structure named DFTB^x-tree based on the distributed main memory database.The optimization of new index structure includes the Cache,the main memory and the hard disk.The size of index nodes is set according to many conditions such as Cache line,the number of instructions and the number of TLB mismatches.Meanwhile,the size of historical data migration nodes is designed a ccording to the size of the disk data pages.Therefore,the cache and the main memory can read the data of interior node or leaf node at a time,to avoid the delay caused by multiple data reads.Moreover,the full-temporal index of mo-ving objects is supported by historical data which is linked through a migration chain.Compared with other algorithms,the experiment shows that DFTB^x-tree has higher efficiency in query and update operations.

Key words: Distributed main memory database,Moving objects,Full-temporal index,Three-level structure

周翔宇,程春玲,杨雁莹. 基于分布式内存数据库的移动对象全时态索引[J]. 计算机科学, 2016, 43(7): 203-207. https://doi.org/10.11896/j.issn.1002-137X.2016.07.037

ZHOU Xiang-yu, CHENG Chun-ling and YANG Yan-ying. Full-temporal Index of Moving Objects Based on Distributed Main Memory Database[J]. Computer Science, 2016, 43(7): 203-207. https://doi.org/10.11896/j.issn.1002-137X.2016.07.037

参考文献

[1] Qiu P,Zhang J,Zeng J.Study on the mobile LBS development model[C]∥2012 IEEE International Conference on Computer Science & Service System (CSSS).2012:1070-1074
[2] Rao B,Minakakis L.Evolution of mobile location-based services[J].Communications of the ACM,2003,46(12):61-65
[3] Sun L M,Song B Y,Yu Y X,et al.Cache-conscious index me-chanism for main-memory databases[J].Wuhan University Journal of Natural Sciences,2006,2(1):309-312
[4] Hankins R A.Effect of node size on the performance of cache-conscious B+-tree[J].ACM SIGMETRICS Performance Evalua-tion Review,2003,31(1):283-294
[5] Saltenis S,Jensen C S,Leutenegger S T,et al.Indexing the positions of continuously moving objects[C]∥Proceedings of ACM SIGMOD International Conference on Management Data.2000:331-342
[6] Tao Y,Papadias D,Sun J.The TPR*-Tree:An optimized spatio-temporal access method for predictive queries[C]∥Procee-dings of the 29^th International Journal on Very Large Data Bases(VLDB).2003:790-801
[7] Jensen C S,Lin D,Ooi B C.Query and update efficient B+-tree based indexing of moving objects[C]∥Proceedings of the Thirtieth International Journal on Very Large Data Bases(VLDB).2004:768-779
[8] Man L Y,Tao Y,Mamoulis N.The B dual-tree:indexing moving objects by space filling curves in the dual space[J].The VLDB Journal,2008,17(3):379-400
[9] Chen S,Ooi B C,Tan K L,et al.ST²B-tree:A self-tunable spatio-temporal B+-tree index for moving objects[C]∥Procee-dings of the ACM SIGMOD International Conference on Mana-gement of Data.2008:29-42
[10] Patel J M,Chen Y,Chakka V P.STRIPES:An efficient index for predicted trajectories[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data.2004:635-646
[11] Zhao L,Chen L,Jing N,et al.An efficient moving object index that supports concurrent access[J].Journal of National University of Defense Technology,2010,32(3):53-59(in Chinese) 赵亮,陈荦,景宁,等.一种支持高效并发访问的移动对象索引[J].国防科技大学学报,2010,32(3):53-59
[12] Rao J,Ross K A.Making B+-Trees Cache conscious in mainmemory[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data.2000:475-486
[13] Chen S,Todd G P B.Improving index performance through prefetching[J].ACM SIGMOD Record,2001,30(2):235-246
[14] Rao J,Ross K A.Cache conscious indexing for decision-support in main memory[C]∥Proceedings of the International Journal on Very Large Data Bases(VLDB).1999:78-89
[15] Chen S,Jensen C S,Lin D.A benchmark for evaluating moving objects indexes[C]∥Proceedings of the International Journal on Very Large Data Bases(PVLDB).2008:23-28

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed