计算机工程与应用 ›› 2022, Vol. 58 ›› Issue (23): 104-116.DOI: 10.3778/j.issn.1002-8331.2201-0393

• 大数据与云计算 • 上一篇    下一篇

Top-k集合空间关键字近似查询方法

孟祥福,王丹丹,张霄雁,贾江浩   

  1. 1.辽宁工程技术大学 电子与信息工程学院,辽宁 葫芦岛 125105
    2.辽宁工程技术大学 软件学院,辽宁 葫芦岛 125105
  • 出版日期:2022-12-01 发布日期:2022-12-01

Top-k Collective Spatial Keyword Approximation Query

MENG Xiangfu, WANG Dandan, ZHANG Xiaoyan, JIA Jianghao   

  1. 1.School of Electronic and Information Engineering, Liaoning Technical University, Huludao, Liaoning 125105, China
    2.School of Software, Liaoning Technical University, Huludao, Liaoning 125105, China
  • Online:2022-12-01 Published:2022-12-01

摘要: 近年来,带有位置和文本信息的空间-文本数据的规模迅速增长,以空间-文本数据为背景的空间关键字查询技术得到广泛的研究与应用。现有大多数空间关键字查询方法通常以单个空间对象作为查询结果的基本单元,最近有少数研究工作提出以一组空间对象作为查询结果的基本单元,这组空间对象联合满足用户的查询需求,但却没有考虑组内空间对象之间的关联关系。针对上述问题,提出一种top-[k]集合空间关键字近似查询方法。提出一种基于关联规则的空间对象之间的关联访问度评估方法,设计了一种结合距离和组内空间对象关联访问度的评分函数;提出了一种基于VP-Tree的剪枝策略,用于快速搜索空间对象的局部邻域,进而加快查询匹配速度;利用评分函数计算候选空间对象组合的得分,并以此选取top-[k]组空间对象作为查询结果。实验结果表明,提出的空间对象关联度评估方法具有较高的准确性,提出的剪枝策略具有较高的执行效率,获取的top-[k]组空间对象具有较高的用户满意度。

关键词: 集合空间关键字, 关联访问度, VP-Tree, 局部邻域

Abstract: In recent years, the scale of spatio-textual data with location and text information has been increasing rapidly, and the spatial keyword query technology against spatio-textual data has been widely studied and applied. Most of the existing spatial keyword query methods usually take a single spatial object as the basic unit of the query results. Recently, there are a few recent research work aiming to find a group of spatial object as the basic unit of the query results, this group of spatial objects jointly meet the requirements of the given spatial keyword query. However, such kind of methods does not consider the relationships(such as social correlations, textual similarity) between spatial objects in the group. To deal with this problem, this paper proposes a top-[k] collective spatial keyword approximate query method. First, an association rule-based social relationship evaluation method for spatial objects is proposed. Furthermore, it designs a scoring function which combines the location distances and social relationships of spatial objects within a group. Second, a VP-Tree based pruning strategy is proposed for quickly searching the local neighborhood of spatial objects. Last, the top-[k] spatial object groups are selected as the query result by leveraging the scoring function to calculate the score of candidate spatial object groups. The experimental results show that the proposed spatial object social relationship evaluation method can achieve high accuracy, the proposed pruning strategy has high execution efficiency, and the obtained top-[k]groups of spatial objects can meet user need and preferences well.

Key words: collective spatial keyword query, associative accessibility, VP-Tree, local neighborhood