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

doi:10.3778/j.issn.1002-8331.2201-0393

摘要/Abstract

摘要： 近年来，带有位置和文本信息的空间-文本数据的规模迅速增长，以空间-文本数据为背景的空间关键字查询技术得到广泛的研究与应用。现有大多数空间关键字查询方法通常以单个空间对象作为查询结果的基本单元，最近有少数研究工作提出以一组空间对象作为查询结果的基本单元，这组空间对象联合满足用户的查询需求，但却没有考虑组内空间对象之间的关联关系。针对上述问题，提出一种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

孟祥福, 王丹丹, 张霄雁, 贾江浩. Top-k集合空间关键字近似查询方法[J]. 计算机工程与应用, 2022, 58(23): 104-116.

MENG Xiangfu, WANG Dandan, ZHANG Xiaoyan, JIA Jianghao. Top-k Collective Spatial Keyword Approximation Query[J]. Computer Engineering and Applications, 2022, 58(23): 104-116.

参考文献

[1] HE P J，XU H，ZHAO X，et al.Scalable collective spatial keyword query[C]//IEEE International Conference on Data Engineering，2015：182-189.
[2] CAO X，CONG G，JENSEN C S，et al.Collective spatial keyword querying[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data，2011：373-384.
[3] CAO X，CONG G，GUO T，et al.Efficient processing of spatial group keyword queries[J].ACM Transactions on Database Systems（TODS），2015，40（2）：1-48.
[4] YU D，WU Y，LIU C，et al.Collective POI querying based on multiple keywords and user preference[C]//Database Systems for Advanced Applications，2019：609-625.
[5] PARK S，PARK S.Reverse collective spatial keyword query processing on road networks with g-tree index structure[J].Information Systems，2019，84：49-62.
[6] LIU H，XU J，ZHENG K，et al.Semantic-aware query processing for activity trajectories[C]//Web Search and Data Mining，2017：283-292.
[7] QIAN Z，XU J，ZHENG K，et al.Semantic-aware top-k spatial keyword queries[J].World Wide Web，2018，21（3）：573-594.
[8] 李盼，张霄雁，孟祥福，等.空间关键字个性化语义近似查询方法[J].智能系统学报，2020，15（6）：1163-1174.
LI P，ZHANG X Y，MENG X F，et al.Spatial keyword personalized and semantic approximate query approach[J].CAAI Transactions on Intelligent Systems，2020，15（6）：1163-1174.
[9] 孙佳宝.基于用户意图理解的空间关键字查询研究[D].苏州：苏州大学，2020.
SUN J B.Research on spatial keyword query based on user intention understanding[D].Suzhou：Soochow University，2020.
[10] 孟祥福，毕崇春，张霄雁，等.Web数据库top-k多样性关键字查询推荐方法[J].计算机研究与发展，2017，54（7）：1577-1591.
MENG X F，BI C C，ZHANG X Y，et al.Web database top-k diverse keyword query suggestion approach[J].Journal of Computer Research and Development，2017，54（7）：1577-1591.
[11] GUO L，SHAO J，AUNG H H，et al.Efficient continuous top-k spatial keyword queries on road networks[J].GeoInformatica，2015，19（1）：29-60.
[12] LUO S，LUO Y，ZHOU S，et al.Distributed spatial keyword querying on road networks[C]//Extending Data Base Technology，2014：235-246.
[13] CHO H J，KWON S J，CHUNG T S.ALPS：an efficient algorithm for top-k spatial preference search in road networks[J].Knowledge and Information Systems，2015，42（3）：599-631.
[14] YUAN Y，LIAN X，CHEN L，et al.RSkNN：KNN search on road networks by incorporating social influence[J].IEEE Transactions on Knowledge and Data Engineering，2016，28（6）：1575-1588.
[15] WANG S，BAO Z F，SHANE C J，et al.Reverse K nearest neighbor search over trajectories[J].IEEE Transactions on Knowledge and Data Engineering，2018，30（4）：757-771.
[16] LI F F，CHENG D H，TENG S H，et al.On trip planning queries in spatial databases[C]//Symposium on Spatial and Temporal Databases，2005：273-290.
[17] LAPPAS T，LIU K，TERZI E.Finding a team of experts in social networks[C]//Knowledge Discovery and Data Mining，2009：467-476.
[18] ROCHA-JUNIOR J B，GKORGKAS O，JONASSEN S，et al.Efficient processing of top-k spatial keyword queries[C]//Symposium on Spatial and Temporal Databases，2011：205-222.
[19] CONG G，JENSEN C S，WU D.Efficient retrieval of the top-k most relevant spatial web objects[J].Proceedings of the VLDB Endowment，2009，2（1）：337-348.
[20] FELIPE I D，HRISTIDIS V，RISHE N.Keyword search on spatial databases[C]//International Conference on Data Engineering，2008：656-665.
[21] CHEN L，LIN X，HU H，et al.Answering why-not questions on spatial keyword top-k queries[C]//International Conference on Data Engineering，2015：279-290.
[22] LI F，YAO B，TANG M，et al.Spatial approximate string search[J].IEEE Transactions on Knowledge and Data Engineering，2013，25（6）：1394-1409.
[23] LI G，FENG J，XU J.Desks：direction-aware spatial keyword search[C]//International Conference on Data Engineering，2012：474-485.
[24] YAO B，LI F，HOU K，et al.Approximate string search in spatial databases[C]//International Conference on Data Engineering，2010：545-556.
[25] ZHANG D，CHAN C Y，TAN K L.Processing spatial keyword query as a top-k aggregation query[C]//Research & Development in Information Retrieval，2014：355-364.
[26] 刘润涛，梁建创.基于新型索引结构的反最近邻查询[J].计算机研究与发展，2020，57（6）：1335-1346.
LIU R T，LIANG J C.Reverse nearest neighbor query based on new index structure[J].Journal of Computer Research and Development，2020，57（6）：1335-1346.
[27] ZHENG K，SU H，ZHENG B，et al.Interactive top-k spatial keyword queries[C]//International Conference on Data Engineering，2015：423-434.
[28] ZHANG D，OOI B C，TUNG A.Locating mapped resources in web 2.0[C]//2010 IEEE 26th International Conference on Data Engineering（ICDE），2010：521-532.
[29] ZHANG D，CHEE Y M，MONDAL A，et al.Keyword search in spatial databases：towards searching by document[C]//International Conference on Data Engineering，2009：688-699.
[30] SU D N，ZHOU X，YANG Z B，et al.Top-K collective spatial keyword queries[J].IEEE Access，2019，7：180779-180792.
[31] GAO Y J，ZHAO J W，ZHENG B H，et al，Efficient collective spatial keyword query processing on road networks[J].IEEE Transactions on Intelligent Transportation Systems，2016，17（2）：480-496.
[32] SU S，ZHAO S，CHENG X，et al.Group-based collective keyword querying in road networks[J].Information Processing Letters，2017：83-90.
[33] WU D，YIU M，JENSEN C S，et al，Efficient continuously moving top-k spatial keyword query processing[C]//International Conference on Data Engineering，2011：541-552.
[34] LONG C，WONG R C，WANG K，et al.Collective spatial keyword queries：a distance owner-driven approach[C]//ACM Special Interest Group on Management of Data，2013：689-700.
[35] JIN X G，SHINS J，JOE J，et al.Collective keyword query on a spatial knowledge base[J].IEEE Transactions on Knowledge and Data Engineering，2019，31（11）：2051-2062.
[36] PETER N Y.Data structures and algorithms for nearest neighbor search in general metric spaces[C]//Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms，1993：311-321.