DKR-Tree:一种支持动态关键字的空间对象索引树  

DKR-Tree:A Dynamic-Keyword-R Tree

作　　者：戴健[1,2] 许佳捷[2] 刘奎恩[2] 武斌[2] 丁治明[2] 

机构地区：[1]中国科学院大学,北京100049 [2]中国科学院软件研究所基础软件国家工程研究中心,北京100190

出　　处：《计算机研究与发展》2013年第S1期163-170,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金重大研究计划重点基金项目(91124001);国家自然科学基金青年科学基金项目(61202064);中国科学院感知中国"先导专项课题"(XDA06020601)

摘　　要：结合空间对象关键字和位置信息的查询作为一项移动互联网的核心技术近年来引起了学术界和工业界的广泛关注.但是,之前的研究工作往往假设关键字是静态的、不变的;然而,由于和空间对象相关的关键字往往是具有其时效性的,因此静态性的假设可能会导致结合空间对象关键字和位置信息的查询结果并不实际可用.针对这种情况,从动态关键字的定义切入;提出了一种结合了动态关键字和空间对象索引的动态关键字空间索引树(dynamic-keyword-R tree);模型化了一个可优化的查询———基于顺序动态关键字的最短路径查询(dynamic and sequential keyword constraints shortest path query,SPQ-DSK);基于DKR-Tree设计了两种策略:关键字优先策略(keyword first)和距离优先策略(distance first)处理SPQ-DSK并给出了相应的算法;最后通过大量的实验对比并分析了基于DKRTree的关键字优先策略和距离优先策略的性能.实验结果表明DKR-Tree能很好地对动态关键字查询提供支持,不论是有效性和高效性都填补了原有含有静态关键字假设的索引树的空白,为下一步研究提供了基础.Queries that combine both spatial locations and keywords have become a core technique in the mobile computing field and have attracted the attention from both academia and industry. However,previous researches usually assume that the keywords related with a spatial location are static,which may lead to the queries including both spatial locations and keywords not actually feasible.To deal with such problem,in this work,a clear definition of dynamic keyword to model the inherent characteristics of some keywords is given;then introduce a dynamic keyword spatial index tree(Dynamic-Keyword-R Tree)and accordingly present an optimizablequery-the Shortest Path Query with Dynamic and Sequential Keyword Constraints(SPQ-DSK);finally,design two strategies to handle such kind of query:Keyword First(KF)strategy and Distance First(DF)strategy and give the corresponding algorithms to implement them respectively.Massive experiments on DKR-Tree and its two strategies are also performed.The results testify that our DKR-Tree outperforms IR2-Tree in both effectiveness and efficiency,which indicate that our work can be a basisforfurther research of dynamic keyword query.

关 键 词：动态关键字 空间对象 索引树 DKR-Tree SPQ-DSK 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]