一种新的面向集合的空间关键字查询方法  

New Collective Query Processing Method Based on Spatial Keyword

作　　者：刘文远[1,2] 付颜胜[1,2] 陈子军[1,2] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北省计算机虚拟技术与系统集成重点实验室,河北秦皇岛066004

出　　处：《小型微型计算机系统》2013年第8期1831-1836,共6页Journal of Chinese Computer Systems

摘　　要：面向集合的空间关键字查询处理是数据库领域近年来的热点研究课题.针对已有查询的不足,定义一种新的描述集合质量的Cost函数,提出一种新的面向集合的空间关键字查询方法,并证明基于该Cost函数的查询问题是NP完全问题.对于给定的对象数据集D={o1,o2,…,on},q为包含位置信息和关键字集合的查询点,查询返回的是在对象数据集D中,既满足查询点q的全部关键字,又能成为q的近邻且较紧凑的对象集合.为处理该查询,利用最小圆覆盖包含全部关键字的对象集合,并采用有效的裁剪策略分别实现了该查询的近似查询算法和精确查询算法.最后通过实验验证了所提算法的有效性.Recently, collective query processing based on spatial keyword are becoming research focuses. However, the existing method of this type of query can lead to uncertain results in some cases. On account of the lack of the existing query, a new Cost function which is to describe the quality of the collection of objects is defined, and a new collective query processing method based on spatial keyword is proposed in this paper. We proved that the problem of query processing based on this Cost function is NP-complete problem. Given a set of objects D = { o~ ,o2 ,＇-＂ ,on } ,a query object q with location and keywords, a query returns from D,a set of objects that are among the neighbors of q and close to each other, meanwhile, contains all the keywords of q. To address this query, the method of using smallest circle to enclose the collection of objects which can cover all the keywords of q is proposed, and an ap- proximate algorithm and an exact algorithm are both provided according to an effective pruning strategy. The approximate algorithm also has a very high accuracy. Finally, the experimental results show that the proposed algorithms are efficient and effective.

关 键 词：对象集合 IR树 关键字查询 空间数据库查询 

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