摘 要：随着基于位置服务应用的不断普及，实现移动对象轨迹实时查询成为当前时空数据库领域的研究热点，其中，移动对象轨迹的 Top-K 查询是面向轨迹大数据的一种快速查询方法。文章对移动对象轨迹查询方法及应用的研究现状进行全面梳理，从不同角度对 Top-K 查询优化算法进行归纳分析，对 Top-K 查询研究中存在的问题和未来研究方向进行总结和展望。
关键词：时空数据库；轨迹查询；Top-K；大数据
DOI:10.19850/j.cnki.2096-4706.2022.23.021
中图分类号：TP301 文献标识码：A 文章编号：2096-4706（2022）23-0077-05
A Summary of Research on Moving Objects Trajectory Top-K Queries
ZHOU Kailai, FENG Xinwei, MENG Qinglei
(College of Software Engineering, Zhengzhou University of Light Industry, Zhengzhou 450001, China)
Abstract: With the growing popularity of location-based service applications, real-time query of moving object trajectories has become a research hotspot in the current spatio-temporal database field. Among them, Top-K query of moving object trajectories is a fast query method for trajectory big data. This paper comprehensively combs the research status of moving object trajectory query methods and applications, summarizes and analyzes the optimization algorithm of Top-K query from different perspectives, and summarizes and prospects the problems and future research directions in Top-K query research.
Keywords: spatio-temporal database; trajectory query; Top-K; big data
参考文献：
[1] OLIVETTI S，GIL M A，SRIDHARAN V K，et al. Merging computational fluid dynamics and machine learning to reveal animal migration strategies [J].Methods in Ecology and Evolution，2021，12（7）：1186-1200.
[2] LAAN Z V，FRANZ M，MARKOVI N. Scalable framework for enhancing raw GPS trajectory data: application to trip analytics for transportation planning [J].Journal of Big Data Analytics in Transportation，2021，3：119-139.
[3] TU W，KE M，ZHANG Y T，et al. Real-Time route recommendations for E-Taxies leveraging GPS trajectories [J].IEEE Transactions on Industrial Informatics，2020，17（5）：3133-3142.
[4] LUAN W J，LIU G J，JIANG C J，et al. MPTR: A maximal-marginal-relevance-based personalized trip recommendation meth-od [J]. IEEE Transactions on Intelligent Transportation Systems，2018，19（11）： 3461-3474.
[5] DENG K，XIE K，ZHENG K，et al. Trajectory indexing and retrieval [C]//Computing with spatial trajectories. New York： Springer，2011：35-60.
[6] FINKEL R A，BENTLEY J L. Quad trees: A data structure for retrieval on composite keys [J].Acta Informatica，1974，4（1）：1-9.
[7] 熊才权，马乐乐，孙贤斌 . 空间索引技术研究 [J]. 计算机技术与发展，2010，20（10）：219-223+227.
[8] CSABAI I，TRENCSENI M，HERCZEGH G，et al. Spatial indexing of large multidimensional databases [J/OL].arXiv:1209.6490[cs.DB].[2022-07-02].https://doi.org/10.48550/arXiv.1209.6490.
[9] JAE L E，RYU K H，NAM K W. Indexing for efficient managing current and past trajectory of moving object [C]//Asia-Pacific Web Conference. Berlin：Springer，2004：782-787.
[10] CHEN Z B，SHEN H T，ZHOU X F，et al. Searching trajectories by locations: An efficiency study [EB/OL].[2022-06-13].https://www.microsoft.com/en-us/research/publication/searchingtrajectories-by-locations-an-efficiency-study/.
[11] TANG L A，ZANG Y，XIE X，et al. Retrieving k-nearest neighboring trajectories by a set of point locations [EB/OL].[2022-06-15].https://dl.acm.org/doi/10.5555/2035253.2035272.
[12] QI S Y，SACHARIDIS D，BOUROS P，et al. Snapshot and continuous points-based trajectory search [J].GeoInformatica，2017，21（4）：669-701.
[13] GÜNTZER U，BALKE W T，KIEßLING W. Optimizing multi-feature queries for image databases [EB/OL].[2022-06-09].https:// dl.acm.org/doi/10.5555/645926.671875.
[14] YADAMJAV M E，WANG S，BAO Z F，et al. Boosting point-based trajectory search with quad-tree [EB/OL].[2022-06-19]. https://www.doc88.com/p-0824873132915.html.
[15] AFZALI P，SHOA N A，RASHIDINEJAD M，et al. Technoeconomic study driven based on available efficiency index for optimal operation of a smart grid in the presence of energy storage system [J].Journal of Energy Storage，2020，32：101853.
[16] Al R T，ARMAN A，ALI M E. Maximizing reverse k-nearest neighbors for trajectories [C]//Australasian Database Conference. Gold Coast：Springer，2018：262-274.
[17] LETTICH F，ORLANDO S，SILVESTRI C. Processing streams of spatial k-NN queries and position updates on manycore GPUs [EB/OL].[2022-05-24].https://dl.acm.org/doi/10.1145/2820783.2820803.
[18] LI J，WANG X T，ZHANG T，et al. Efficient parallel K best connected trajectory (K-BCT) query with GPGPU: A combinatorial min-distance and progressive bounding box approach [EB/OL].[2022-06-19].https://www.doc88.com/p-2751792871495.html.
[19] TRAJCEVSKI G，TAMASSIA R，DING H，et al. Continuous probabilistic nearest-neighbor queries for uncertain trajectories [EB/OL].[2022-06-13].http://users.ece.northwestern. edu/~peters/references/EDBT09submissionSept08.pdf.
[20] LIAN X，CHEN L，YU J X. Pattern matching over cloaked time series[C]//2008 IEEE 24th International Conference on Data Engineering. Cancun：IEEE，2008：1462-1464.
[21] YEH M Y，WU K L，YU P S，et al. PROUD: a probabilistic approach to processing similarity queries over uncertain data streams [C]//Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology. NewYork：ACM，2009：684-695.
[22] CHEN M M，WANG N，LIN G F，et al. Network-Based trajectory search over time intervals [J].Big Data Research，2021，25（1）：100221.
[23] 周星星，吉根林，张书亮 . 时空轨迹相似性度量方法综述 [J]. 地理信息世界，2018，25（4）：11-18.
[24] HSU C C，KUNG P H，YEH M Y，et al. Bandwidthefficient distributed k-nearest-neighbor search with dynamic time warping [C]//2015 IEEE International Conference on Big Data (Big Data).Santa Clara：IEEE，2015：551-560.
[25] ZHANG Z，WANG Y，MAO J，et al. DT-KST: Distributed top-k similarity query on big trajectory streams [C]//International Conference on Database Systems for Advanced Applications. Suzhou： Springer，2017：199-214.
[26] ZHANG Z，MAO J，JIN C，et al. MDTK: bandwidthsaving framework for distributed top-k similar trajectory query [C]//International Conference on Database Systems for Advanced Applications. Gold Coast：Springer，2018：613-629.
[27] LI H，QIU N，CHEN M，et al. FASTDB: An array database system for efficient storing and analyzing massive scientific data [C]// International conference on algorithms and architectures for parallel processing. Zhangjiajie：Springer，2015：606-616.
[28] PAVLO A. In-memory, horizontal, and transactional: the H-store OLTP DBMS project [M]//Making Databases Work: the Pragmatic Wisdom of Michael Stonebraker. 2018：245-251.
[29] RAGAB M，TOMMASINI R，EYVAZOV S, et al. Towards making sense of Spark-SQL performance for processing vast distributed RDF datasets [C]//Proceedings of The International Workshop on
Semantic Big Data. Portland：ACM，2020：1-6.[30] XIE D，LI F，YAO B，et al. Simba: Efficient in-memory spatial analytics[C]//Proceedings of the 2016 International Conference on Management of Data. Burlingame：ACM，2016：1071-1085.
[31] ZHENG B，WANG H，ZHENG K，et al. Sharkdb: an inmemory column-oriented storage for trajectory analysis [J]. World Wide Web，2018，21（2）455-485.
[32] SHANG Z，LI G，BAO Z. DITA: distributed in-memory trajectory analytics [C]//Proceedings of the 2018 International Conference on Management of Data. Houston：ACM，2018：725-740.
[33] ATOOFIAN E. Approximate cache in GPGPUs [J]. ACM Transactions on Embedded Computing Systems (TECS)，2020，19（5）：1-22.
[34] LEAL E，GRUENWALD L，Zhang J T，et al. TKSimGPU: A parallel top-K trajectory similarity query processing algorithm for GPGPUs [C]//2015 IEEE International Conference on Big Data (Big Data). Santa Clara：IEEE，2015：461-469.
[35] MUSTAFA H，LEAL E，GRUENWALD L. FastTopK: A fast top-ktrajectory similarity query processing Algorithm for GPUs [C]//2018 IEEE International Conference on Big Data (Big Data). Seattle：IEEE，2018：542-547.
[36] DONG K X，ZHANG B W，SHEN Y Y，et al. GAT: A unified GPU-accelerated framework for processing batch trajectory queries [J].IEEE Transactions on Knowledge and Data Engineering， 2018，32（1）：92-107.
作者简介：周开来（1978—），男，汉族，湖北襄阳人，副教授，博士研究生，研究方向：数据库和并行计算；冯鑫伟（1997—），男，汉族，河南郑州人，硕士研究生在读，研究方向：数据库和大数据分析；孟庆磊（1998—），男，汉族，河南商丘人，硕士研究生在读，研究方向：数据库和大数据分析。