基于四叉树和R+树复合索引时空数据查询研究  

Spatiotemporal Data Query Based on Quadtree and R+Tree Composite Index

作　　者：赵燚 钱育蓉[2] 杨兴耀[2] 汪丽娟 ZHAO Yi;QIAN Yurong;YANG Xingyao;WANG Lijuan(School of Information Science and Engineering,Xinjiang University,Urumqi Xinjiang 830046,China;School of Software,Xinjiang University,Urumqi Xinjiang 830008,China)

机构地区：[1]新疆大学信息科学与工程学院,新疆乌鲁木齐830046 [2]新疆大学软件学院,新疆乌鲁木齐830008

出　　处：《新疆大学学报（自然科学版）》2020年第1期49-54,74,共7页Journal of Xinjiang University(Natural Science Edition)

基　　金：国家自然科学基金项目“基于内存计算的遥感数据高效并行和任务调度研究”(No.61562086);新疆维吾尔自治区教育厅创新团队项目“协同过滤推荐在电子商务中的应用与研究”(XJEDU2016S035);新疆大学博士科研启动基金项目(BS150257);新疆维吾尔自治区教育厅项目(XJEDU2016S035).

摘　　要：针对空间数据库的现有索引方法可扩展性差和检索效率低的问题,提出了一种分布式复合时空索引方案MixIndexer,可以满足对大量时空传感器数据的查询需求.首先,本文提出了一种基于Couchbase的分布式时空索引体系结构,该体系结构由全局索引和局部索引组成;其次,结合分布式增强R+(MDR+)树算法,提出全局四叉树索引方法以提高时空数据的检索和查询效率,并设计了一种基于MapReduce的大时空传感器数据批量构造指标并行处理方法;最后,基于Couchbase几种常见的键值结构实现了MixIndexer复合索引.经实验,MixIndexer复合索引方法优于典型空间数据库的索引方法和单个树索引R+(Cache Conscious R+Tree,CCR+)方法,相比较查询耗时分别缩短42%和25%.Aiming at the problem of poor scalability and low retrieval efficiency of existing indexing methods in spatial database,a distributed composite spatio-temporal indexing scheme,Mix Indexer,is proposed,which can satisfy the query requirements for a large number of spatio-temporal sensor data.Firstly,a distributed spatial-temporal index architecture based on Couchbase is proposed,which consists of global index and local index.Secondly,combined with distributed enhanced R+(MDR+)tree algorithm,a global quadtree index method is proposed to improve the retrieval and query efficiency of spatio-temporal data,and a parallel processing method of large-scale spatio-temporal sensor data batch construction index based on MapReduce is designed.Finally,MixIndexer hybrid index is implemented based on several common key-value structures of Couchbase.Experiments show that Mix Indexer composite index method is superior to typical spatial database index method and single tree index R+(Cache Conscious R+Tree,CCR+)method.Compared with query time,Mix Indexer composite index method reduces 42%and 25%respectively.

关 键 词：时空数据 Couchbase数据库 复合索引 空间云计算 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]