空间文本数据流上连续查询评估技术综述

doi:10.3778/j.issn.1673-9418.2009053

摘要/Abstract

摘要：

空间文本数据流上连续查询（CQST）在基于位置的服务中应用广泛，其在不断更新的数据流上，持续监控满足空间和文本约束的结果。为了将数据流中的对象尽快匹配给CQST，在CQST上构建高效的过滤技术是关键。CQST查询评估方法——为查询选取恰当的空间文本索引，构建高效的过滤策略提升索引的空间文本过滤性能，为数据流中到来的对象过滤大量不相关的查询，避免高昂的验证代价，提高对象与查询的匹配效率。现有工作利用有限的空间索引和文本索引构建空间文本混合索引，其评估性能差异取决于采用的过滤策略，即提升索引过滤性能的技术。以现有CQST查询优化技术为主要研究对象，对评估CQST的流程以及存在的挑战进行了介绍；对在中央服务器及分布式集群上评估CQST的空间过滤技术及文本过滤技术进行综述比较，包含采用的空间文本混合索引，为提升索引过滤性能采用的空间过滤策略、文本过滤策略及二者的结合机制，分析总结其利弊，讨论评估CQST未来可能的研究方向。

关键词: 空间文本查询, 连续查询, 过滤策略, 数据流

Abstract:

The continuous queries over spatial-textual data streams (CQST) are widely used in location-based services, which continuously monitor the results satisfying spatial and textual constraints over updated data streams. To match the objects over the data streams with CQST as soon as possible, building efficient filtering techniques on the CQST is the key. The approach to evaluating CQST is to select the appropriate spatial and textual index to organize the CQST, construct efficient filtering strategies to improve the spatial and textual filtering capabilities of the index, filter large number of unpromising queries for the objects over the data streams, avoid costly verification cost and improve the efficiency of matching objects and queries. The existing works construct spatial-textual hybrid index by using limited spatial index and textual index, and the difference in evaluation performance depends on the filtering strategies used, i.e. the techniques of improving the filtering performance of the index. This paper takes the techniques of evaluating CQST as the research object, introduces the framework and challenges of evaluating CQST, reviews and compares the spatial and textual filtering techniques of evaluating CQST on a central server and distributed clusters, including the adopted spatial-textual hybrid index, the spatial and textual filtering strategies and the combination scheme of the spatial and textual index to improve the filtering performance of the index, analyzes and summarizes their advantages and disadvantages, and discusses possible future research directions.

Key words: spatial-textual queries, continuous queries, filtering strategy, data streams

杨茸, 牛保宁. 空间文本数据流上连续查询评估技术综述[J]. 计算机科学与探索, 2021, 15(4): 631-640.

YANG Rong, NIU Baoning. Survey of Continuous Queries over Spatial-Textual Data Streams[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 631-640.

参考文献

[1] LI G L, WANG Y, WANG T, et al. Location-aware publish/subscribe[C]//Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, Aug 11-14, 2013. New York: ACM, 2013: 802-810.
[2] CHEN L S, CONG G, CAO X. An efficient query indexing mechanism for filtering geo-textual data[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, New York, Jun 22-27, 2013. New York: ACM, 2013: 749-760.
[3] YU M H, LI G L, FENG J H. A cost-based method for location- aware publish/subscribe services[C]//Proceedings of the 24th ACM International Conference on Information and Knowledge Management, Melbourne, Oct 19-2, 2015. New York: ACM, 2015: 693-702.
[4] MAHMOOD A R, ALY A M, AREF W G. FAST: frequency-aware indexing for spatio-textual data streams[C]//Proceedings of the 2018 IEEE 34th International Conference on Data Engineering, Paris, Apr 16-20, 2018. Piscataway: IEEE, 2018: 305-316.
[5] WANG X, ZHANG Y, ZHANG W J, et al. AP-Tree: efficiently support location-aware publish/subscribe[J]. The VLDB Journal, 2015, 24(6): 823-848.
[6] DENG Z, WANG M, WANG L Z, et al. An efficient indexing approach for continuous spatial approximate keyword queries over geo-textual streaming data[J]. International Journal of Geo-Information, 2019, 8(2): 57-76.
[7] GUO L, ZHANG D X, LI G L, et al. Location-aware pub/sub system: when continuous moving queries meet dynamic event streams[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, May 31-Jun 4, 2015. New York: ACM, 2015: 843-857.
[8] MAHMOOD A R, ALY A M, QADAH T, et al. Tornado: a distributed spatio-textual stream processing system[J]. Procee-dings of the VLDB Endowment, 2015, 8(12): 2020-2023.
[9] MAHMOOD A R, DAGHISTANI A, ALY A M, et al. Adaptive processing of spatial-keyword data over a distributed streaming cluster[C]//Proceedings of the 2018 ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Seattle, Nov 6-9, 2018. New York: ACM, 2018: 219-228.
[10] CHEN Z D, CONG G, ZHANG Z J, et al. Distributed publish/subscribe query processing on the spatio-textual data stream[C]//Proceedings of the 2017 IEEE 33rd International Conference on Data Engineering, San Diego, Apr 19-22, 2017. Piscataway: IEEE, 2017: 1095-1106.
[11] CHEN Y, CHEN Z D, CONG G, et al. SSTD: a distributed system on streaming spatio-textual data[J]. Proceedings of the VLDB Endowment, 2020, 13(11): 2284-2296.
[12] HU H Q, LIU Y Q, LI G L, et al. A location-aware publish/subscribe framework for parameterized spatio-textual subscriptions[C]//Proceedings of the 31st IEEE International Conference on Data Engineering, Seoul, Apr 13-17, 2015. Washington: IEEE Computer Society, 2015: 711-722.
[13] YU M H, LI G L, WANG T, et al. Efficient filtering algorithms for location-aware publish/subscribe[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(4): 950-963.
[14] HU J F, CHENG R, WU D, et al. Efficient top-k subscription matching for location-aware publish/subscribe[C]//LNCS 9239: Proceedings of the 14th International Symposium on Spatial and Temporal Databases, Hong Kong, China, Aug 26-28, 2015. Berlin, Heidelberg: Springer, 2015: 333-351.
[15] HULAWALE S, BURGHATE B. A novel RI-tree based top-k subscription matching for location-aware publish/subscribe [J]. International Journal of Advance Research and Innovative Ideas in Education, 2016, 2(3): 3928-3935.
[16] CHEN L S, CONG G, CAO X, et al. Temporal spatial-keyword top-k publish/subscribe[C]//Proceedings of the 31st IEEE International Conference on Data Engineering, Seoul, Apr 13-17, 2015. Washington: IEEE Computer Society, 2015: 255-266.
[17] CHEN L S, SHANG S. Approximate spatio-temporal top-k publish/subscribe[J]. World Wide Web, 2019, 22(5): 2153-2175.
[18] WANG X, ZHANG W J, ZHANG Y, et al. Top-k spatial-keyword publish/subscribe over sliding window[J]. The VLDB Journal, 2017, 26(3): 301-326.
[19] CHEN L S, SHANG S, JENSEN C S, et al. Top-k term publish/subscribe for geo-textual data streams[J]. The VLDB Journal, 2020, 29(5): 1101-1128.
[20] CHEN L S, SHANG S, ZHENG K, et al. Cluster-based subscription matching for geo-textual data streams[C]//Proceedings of the 35th IEEE International Conference on Data Engineering, Macao, China, Apr 8-11, 2019. Piscataway: IEEE, 2019: 890-901.
[21] CHEN L S, SHANG S. Region-based message exploration over spatio-temporal data streams[C]//Proceedings of the 33rd AAAI Conference on Artificial Intelligence, the 31st Innovative Applications of Artificial Intelligence Conference, the 9th AAAI Symposium on Educational Advances in Artificial Intelligence, Honolulu, Jan 27-Feb 1, 2019. Menlo Park: AAAI, 2019: 873-880.
[22] GUO L, SHAO J, AUNG H H, et al. Efficient continuous top-k spatial keyword queries on road networks[J]. Geo-Informatica, 2015, 19(1): 29-60.
[23] ZHENG B L, ZHENG K, XIAO X H, et al. Keyword-aware continuous kNN query on road networks[C]//Proceedings of the 32nd IEEE International Conference on Data Engineering, Helsinki, May 16-20, 2016. Washington: IEEE Computer Society, 2016: 871-882.
[24] SALGADO C, CHEEMA M A, ALI M E. Continuous monitoring of range spatial keyword query over moving objects[J]. World Wide Web, 2018, 21(3): 687-712.
[25] OH S, JUNG H R, KIM U M. An efficient processing of range spatial keyword queries over moving objects[C]//Proceedings of the 2018 International Conference on Information Networking, Chiang Mai, Jan 10-12, 2018. Piscataway: IEEE, 2018: 525-530.
[26] QI J Z, ZHANG R, JENSEN C S, et al. Continuous spatial query processing: a survey of safe region based techniques[J]. ACM Computing Surveys, 2018, 51(3): 1-39.
[27] MAGDY A, ALY A M, MOKBEL M F, et al. GeoTrend: spatial trending queries on real-time microblogs[C]//Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Burlingame, Oct 31-Nov 3, 2016. New York: ACM, 2016: 7.
[28] MAGDY A, MOKBEL M F, Elnikety S, et al. Mercury: a memory-constrained spatio-temporal real-time search on microblogs[C]//Proceedings of the 30th International Conference on Data Engineering, Chicago, Mar 31-Apr 4, 2014. Washington: IEEE Computer Society, 2018: 172-183.
[29] ZHANG C Y, ZHANG Y, ZHANG W J, et al. Inverted linear Quadtree: efficient top k spatial keyword search[J]. IEEE Transactions on Knowledge & Data Engineering, 2016, 28(7): 1706-1721.
[30] CHUNG Y C, SU F I, LEE C, et al. Multiple k nearest neighbor search[J]. World Wide Web, 2017, 20(2): 371-398.
[31] CHEN L S, CONG G, JENSEN C S, et al. Spatial keyword query processing: an experimental evaluation[J]. Proceedings of the VLDB Endowment, 2013, 6(3): 217-228.