Overview of Spatial Keyword Queries

doi:10.3778/j.issn.1002-8331.2105-0091

Abstract

Abstract:

In recent years, the scale of spatial-textual data with location and textual information has grown rapidly. Social data in social networks and transaction data in mobile Internet are both important sources of spatial-text data, which are characterized by massive, heterogeneous and multi-dimensional data. Spatial keyword query technology based on spatial-text data has been widely studied and applied at present. Given a query location （represented by latitude and longitude） and a group of query keywords, the spatial object closest to the query location and highly relevant to the query keyword is returned. The relevant query technologies of spatial-text data are reviewed, including query processing mode, index structure, semantic approximation query, query based on road network, query based on route planning, query based on social network, query based on influence constraint, etc.

Key words: space keyword, index, semantic approximation, road network, route planning, social network, impact constraint

摘要：

近年来，带有位置和文本信息的空间-文本数据的规模迅速增长。社交网络中的社交数据和移动互联网中的交易数据等都是空间-文本数据的重要来源，这些数据具有海量、异构、多维等特点。以空间-文本数据为背景的空间关键字查询技术目前得到广泛的研究与应用，给定一个查询位置（用经度和纬度表示）和一组查询关键字，返回距离查询位置最近且与查询关键字相关性较高的空间对象。对空间-文本数据的相关查询技术进行综述，主要包括查询处理模式、索引结构、语义近似查询、基于路网的查询、路线规划查询、基于社交网络查询、基于影响约束下的查询等。

关键词: 空间关键字, 索引, 语义近似, 路网, 路线规划, 社交网络, 影响约束

MENG Xiangfu, WANG Dandan, ZHANG Feng. Overview of Spatial Keyword Queries[J]. Computer Engineering and Applications, 2021, 57(20): 13-24.

孟祥福，王丹丹，张峰. 空间关键字查询综述[J]. 计算机工程与应用, 2021, 57(20): 13-24.

References

[1] GUTTMAN A.R-trees：a dynamic index structure for spatial searching[C]//Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data，Boston，Massachusetts.New York：Association for Computing Machinery，1984：47-57.
[2] CONG G，JENSEN C S，WU D.Efficient retrieval of the top-k most relevant spatial web objects[J].Proc of the VLDB Endowment，2009，2（1）：337-348.
[3] LI Z S，LEE K C K，ZHENG B H，et al.IR-Tree：an efficient index for geographic document search[J].IEEE Transactions on Knowledge & Data Engineering，2011，23（4）：585-599.
[4] LEE S H，YU J S，YUK I H，et al.An efficient high-dimensional index structure[J].Journal of KISS（B）：Software and Applications，1999，26（6）.
[5] BECKMANN N，KRIEGEL H P，SCHNEIDER R，et al.The R*-Tree：an efficient and robust access method for points and rectangles[J].ACM SIGMOD Record，1990，19（2）：322-331.
[6] FELIPE I D，HRISTIDIS V，RISHE N.Keyword search on spatial databases[C]//IEEE International Conference on Data Engineering，2008：656-665.
[7] ZHANG D，CHEE Y M，MONDAL A，et al.Keyword search in spatial databases：towards searching by document[C]//IEEE International Conference on Data Engineering，2009：688-699.
[8] 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.
[9] ZHOU Y，XIE X，WANG C，et al.Hybrid index structures for location-based web search[C]//International Conference on Information & Knowledge Management，2005：155-162.
[10] YIANILOS P N.Data structures and algorithms for nearest neighbor search in general metric spaces[C]//Proceedings of SODA’93，1993：311-321.
[11] ZHANG C Y，ZHANG Y，ZHANG W J，et al.Inverted linear quadtree：efficient top-k spatial keyword search[J].Journal of Robotics & Machine Learning，2016，28（7）：1706-1721.
[12] ASUDEH A，ZHANG G，HASSAN N，et al.Crowdsourcing pareto-optimal object finding by pairwise comparisons[C]//Proceedings of the 24th ACM International Conference on Information and Knowledge Management，Melbourne，Oct 19-23，2015：753-762.
[13] KWON H Y，WANG H，WHANG K Y.G-index model：ageneric model of index schemes for top-k spatial keyword queries[J].World Wide Web-Internet & Web Information Systems，2015，18（4）：969-995.
[14] LIU X，CHEN L，WAN C.LINQ：a framework for location-aware indexing and query processing[J].IEEE Transactions on Knowledge & Data Engineering，2015，27（5）：1288-1300.
[15] ROCHA-JUNIOR J B，GKORGKAS O，JONASSEN S，et al.Efficient processing of top-k spatial keyword queries[C]//Advances in Spatial and Temporal Databases，Minneapolis，August 24-26，2011.Berlin，Heidelberg：Springer，2011：205-222.
[16] WU D M，YIU M L，CONG G，et al.Joint top-k spatial keyword query processing[J].IEEE Transactions on Knowledge and Data Engineering，2012，24（10）：1889-1903.
[17] LU Y，LU J H，SHAHABI C.Efficient algorithms and cost models for reverse spatial-keyword k-nearest neighbor search[J].ACM Transactions on Database Systems，2014，39（2）：1-46.
[18] LU J H，LU Y，CONG G.Reverse spatial and textual k nearest neighbor search[C]//Proc of ACM SIGMOD International Conference on Management of Data，Athens，Greece，2011：349-360.
[19] HU H Q，LI G L.Top-k spatio-textual similarity join[J].IEEE Transactions on Knowledge and Data Engineering，2016，28（2）：551-565.
[20] KORN F，MUTHUKRISHNAN S.Influence sets based on reverse nearest neighbor queries[C]//Proc of the 2000 ACM SIGMOD，2000：201-212.
[21] YANG C，LIN K I.An index structure for efficient reverse nearest neighbor queries[C]//Proceedings 17th International Conference on Data Engineering，2001：485-492.
[22] 郝忠孝，刘永山.空间对象的反最近邻查询[J].计算机科学，2005，32（11）：115-118.
HAO Z X，LIU Y S.Reverse nearest neighbor search in spatial database[J].Computer Science，2005，32（11）：115-118.
[23] 李松，郝忠孝.移动对象的动态反向最近邻查询技术[J].计算机工程，2008，34（10）：40-42.
LI S，HAO Z X.Query technology of dynamic reverse nearest neighbors for moving object[J].Computer Engineering，2008，34（10）：40-42.
[24] 王淼，郝忠孝.基于Delaunay图的反向最近邻查询[J].计算机工程，2010，36（5）：59-61.
WANG M，HAO Z X.Reverse nearest neighbor query based on Delaunay diagram[J].Computer Engineering，2010，36（5）：59-61.
[25] PAPADIAS D，TAO Y，MOURATIDIS K，et al.Aggregate nearest neighbor queries in spatial databases[J].ACM Trans Database Syst，2005，30（2）：529-576.
[26] YANG S Y，CHEEMA M A，LIU X M，et al.Reverse k nearest neighbor queries and spatial reverse Top-k queries[J].The VLDB Journal，2017，26（2）：151-176.
[27] 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.
[28] WANG S S，LI Y，CHAI S，et al.SPHLU：an efficient algorithm for processing PRkNN queries on uncertain data[J].Chinese Journal of Electronics，2016，25（3）：403-406.
[29] HIDAYAT A，YANG S Y，MUHAMMAD A C，et al.Reverse approximate nearest neighbor queries[J].IEEE Transactions on Knowledge and Data Engineering，2018，30（2）：339-351.
[30] CUILLAUME C，ELIAS E，MICHAEL E H，et al.Dimensional testing for reverse k-nearest neighbor search[J].Proc of the VLDB Endowment，2017，10（7）：769-780.
[31] FRANCISO G G，ANTONIO C，LIUIS I，et al.RKNN query processing in distributed spatial infrastructures：a performance study[C]//Proc of the 7th Conference on Model and Data Engineering.Berlin：Springer，2017：200-207.
[32] 刘润涛，梁建创.基于新型索引结构的反最近邻查询[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.
[33] CHEN L，LIN X，HU H，et al.Answering why-not questions on spatial keyword top-k queries[C]//Proceedings of ICDE，2015：279-290.
[34] ZHENG K，SU H，ZHENG B，et al.Interactive top-k spatial keyword queries[C]//Proceedings of ICDE，2015：423-434.
[35] 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.
[36] LI G，FENG J，XU J.Desks：direction-aware spatial keyword search[C]//Proceedings of ICDE，2012：474-485.
[37] LIU H W，XU J J，ZHENG K，et al.Semantic-aware query processing for activity trajectories[C]//Proceedings of the Tenth ACM International Conference on Web Search and Data Mining，Cambridge，United Kingdom，Feb 6-10，2017.New York：Association for Computing Machinery，2017：283-292.
[38] YAO B，LI F，HOU K，et al.Approximate string search in spatial satabases[C]//Proceedings of ICDE，2010：545-556.
[39] ZHANG D，CHAN C Y，TAN K L.Processing spatial keyword query as a top-k aggregation query[C]//Proceedings of SIGIR，2014：355-364.
[40] ZHAO P，FANG H，SHENG V S，et al.Monochromatic and bichromatic ranked reverse boolean spatial keyword nearest neighbors search[J].World Wide Web，2017，20（1）：39-59.
[41] JAGADISH H V，OOI B C，TAN K L，et al.iDistance：an adaptive B+-tree based indexing method for nearest neighbor search[J].ACM Transactions on Dootabase Systems，2005，30（2）：364-397.
[42] QIAN Z H，XU J，ZHENG K，et al.Semantic-aware top-k spatial keyword queries[J].World Wide Web-internet & Web Information Systems，2018，21（3）：573-594.
[43] BLEI D M，NG A Y，JORDAN M I.Latent dirichlet allocation[J].The Journal of Machine Learning Research，2012，3：993-1022.
[44] QIAN Z H，XU J，ZHENG K，et al.On efficient spatial keyword querying with semantics[C]//Proceedings of DASFAA，2016：149-164.
[45] BLEI D M，LAFFERTY J D.Dynamic topic models[C]//Proc International Conference on Machine Learning，2006：113-120.
[46] SCH?LKOPF B，PLATT J，HOFMANN T.Hierarchical Dirichlet processes with random effects[C]//Advances in Neural Information Processing Systems，2006：697-704.
[47] DU L，BUNTINE W L，JIN H.Sequential latent Dirichlet allocation：discover underlying topic structures within a document[C]//IEEE International Conference on Data Mining，2011：148-157.
[48] ROCHA-JUNIOR J B，N?RV?G K.Top-k spatial keyword queries on road networks[C]//Proceedings of the 15th International Conference on Extending Database Technology，2012：168-179.
[49] 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.
[50] 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.
[51] LUO S，LUO Y，ZHOU S，et al.Distributed spatial keyword querying on road networks[C]//Proceedings of EDBT，2014：235-246.
[52] ROCHA-JUNIOR J B，VLACHOU A，DOULKERIDIS C，et al.Efficient processing of top-k spatial preference queries[J].Proc of the VLDB Endowment，2010，4（2），93-104.
[53] YUAN Y，LIAN X，CHEN L，et al.RSkNN：KNN search on road networks by incorporating social influence[J].Computers Networks & Communications，2016，28（6）：1575-1588.
[54] LI F F，CHENG D H，TENG S H，et al.On trip planning queries in spatial databases[C]//Proceedings of SSTD，2005：273-290.
[55] SHARIFZADEH M，KOLAHDOUZAN M R，SHAHABI C.The optimal sequenced route query[J].The VLDB Journal，2008，17（4）：765-787.
[56] CAO X，CHEN L S，CONG G，et al.Keyword-aware optimal route search[J].Proc of the VLDB Endowment，2012，5（11）：1136-1147.
[57] YANG D N，SHEN C Y，LEE W C，et al.On socio-spatial group query for location-based social networks[C]//Proceedings of KDD，2012：949-957.
[58] LAPPAS T，LIU K，TERZI E.Finding ateam of experts in social networks[C]//Proceedings of KDD，2009：467-476.
[59] CAO X，CONG G，JENSEN C S，et al.Collective spatial keyword querying[C]//Proceedings of SIGMOD，2011：373-384.
[60] CAO X，CONG G，GUO T，et al.Efficient processing of spatial group keyword queries[J].ACM Trans Database Syst，2015，40（2）：1-48.
[61] YU D，WU Y，LIU C，et al.Collective POI querying based on multiple keywords and user preference[C]//Proceedings of DASFAA，2019：609-625.
[62] PARK S.Reverse collective spatial keyword query processing on road networks with G-Tree index structure[J].Inf Syst，2019，84：49-62.
[63] ZHANG D，CHEE Y M，MONDAL A，et al.Keyword search in spatial databases：towards searching by document[C]//Proceedings of ICDE，2009：688-699.
[64] GAO Y J，ZHAO J W，ZHENG B H，et al.Efficient collective spatial keyword query processing on road networks[J].IEEE Transaction on Intelligent Transportation Systems，2016，17（2）：480-496.
[65] SU S，ZHAO S，CHENG X，et al.Group-based collective keyword querying in road networks[J].Inf Process Lett，2017：83-90.
[66] HE P J，XU H，ZHAO X，et al.Scalable collective spatial keyword query[C]//2015 31st IEEE International Conference on Data Engineering Workshops，2015：182-189.
[67] LONG C，WONG C W，WANG K，et al.Collective spatial keyword queries：a distance owner-driven approach[C]//SIGMOD Conference，2013：689-700.
[68] CHAN H K，LONG C，WONG C W.Inherent-cost aware collective spatial keyword queries[C]//Proceedings of SSTD，2017：357-375.
[69] ZHANG P F，LIN H Z，YAO B，et al.Level-aware collective spatial keyword queries[J].Inform Sci，2017，378：194-214.
[70] CHOUDHURY F M，CULPEPPER J S，CAO X，et al.Maximizing bichromatic reverse spatial and textual knearest neighbor queries[J].Proc of the VLDB Endowment，2016，9（6）：456-467.
[71] 李盼，张霄雁，孟祥福，等.空间关键字个性化语义近似查询方法[J].智能系统学报，2020，15（6）：1163-1174.
LI P，ZHANG X Y，MENG X F，et al.Spatial keywords personalized and semantic approximate query approach[J].CAAI Transactions on Intelligent Systems，2020，15（6）：1163-1174.
[72] LUO S，LUO Y，ZHOU S，et al.Distributed spatial keyword querying on road networks[C]//Proceedings of EDBT，2014：235-246.
[73] DOULKERIDIS C，VLACHOU A，MPESTAS D，et al.Parallel and distributed processing of spatial preference queries using keywords[C]//Proceedings of EDBT，2017：318-329.
[74] HUANG Z S，ZHAO Y，CHEN W，et al.A natural-language-based visual query approach of uncertain human trajectories[J].IEEE Trans Vis Comput Graph，2020，26（1）：1256-1266.
[75] LUO Y Y，QIN X D，TANG N，et al.DeepEye：creating good data visualizations by keyword search[C]//Proceedings of SIGMOD，2018：1733-1736.
[76] ROBERTSON S，ZARAGOZA H.The probabilistic relevance framework：BM25 and beyond[J].Foundations and Trends in Information Retrieval，2009，3（4）：333-389.