Research Overview on Spatial Nearest Neighbor and Its Variant Queries

doi:10.3778/j.issn.1673-9418.2410049

Abstract

Abstract: The nearest neighbor query and its extended variants are crucial topics in the field of spatial databases and have been widely applied in geographic information systems, pattern recognition, decision support, urban planning, and many other fields. In recent years, numerous algorithms for nearest neighbor queries and their variants have been proposed, prompting a comprehensive analysis of existing work in this area. Regarding nearest neighbor query index structures, this paper introduces the research progress of current spatial index structures in detail, including grid-based spatial index structures, tree-based spatial index structures, and hybrid spatial index structures, analyzing the advantages and disadvantages of each. For variant query algorithms of nearest neighbor queries, the focus is on analyzing several types of nearest neighbor variant queries: reverse nearest neighbor query algorithms, continuous nearest neighbor query algorithms, nearest pair query algorithms, obstacle nearest neighbor query algorithms, and nearest neighbor-based spatial Skyline query algorithms. For each variant, the characteristics, research status, and core technologies of the algorithms are thoroughly analyzed, and the advantages, disadvantages, and application scopes of the variant algorithms are summarized. Finally, it clarifies the current challenges faced in research, such as the continuously increasing volume of spatial data, the high dimensionality of spatial data, and the diversity of data query demands. It also looks forward to future development trends.

Key words: spatial indexing structure, nearest neighbor query, reverse nearest neighbor query, continuous nearest neighbor query, nearest pair query, obstructed nearest neighbor query, spatial Skyline query

摘要： 空间最近邻查询及其扩展的变体查询是空间数据库研究领域中的重要内容，被广泛地应用于地理信息系统、模式识别、决策支持、城市规划等众多领域。近年来许多空间最近邻及其变体查询算法被提出，对现有的空间最近邻查询工作进行综合分析和梳理。针对最近邻查询索引结构，从基于网格的空间索引结构、基于树的空间索引结构和混合空间索引结构详细介绍目前空间索引结构的研究进展，分析索引结构的优缺点；针对最近邻查询算法的变体查询算法，重点研究分析了以下几种最近邻变体查询：反最近邻查询算法、连续最近邻查询算法、最近对查询算法、障碍最近邻查询算法和基于最近邻的空间Skyline查询算法等。对于每种变体详细分析其算法的特点、研究现状和核心技术，并归纳出变体算法的优缺点和适用范围等。阐明了当前研究工作面临空间数据量大量增加、空间数据维度高和数据查询需求的多样性等问题，并对其未来的发展趋势进行了展望。

关键词: 空间索引结构, 最近邻查询, 反最近邻查询, 连续最近邻查询, 最近对查询, 障碍最近邻查询, 空间Skyline查询

WANG Luqi, GAO Jixun, TANG Hao, LI Song, ZHAO Yuanyuan. Research Overview on Spatial Nearest Neighbor and Its Variant Queries[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(9): 2319-2340.

王璐琦, 高继勋, 唐昊, 李松, 赵媛媛. 空间最近邻及其变体查询研究综述[J]. 计算机科学与探索, 2025, 19(9): 2319-2340.

References

[1] CARNIEL A C. Defining and designing spatial queries: the role of spatial relationships[J]. Geo-spatial Information Science, 2024, 27(6): 1868-1892.
[2] 丁际文, 刘卓锦, 王家兴, 等. LayerLSB: 基于分层局部敏感B树的最近邻搜索[J]. 计算机科学, 2023, 50(4): 32-39.
DING J W, LIU Z J, WANG J X, et al. LayerLSB: nearest neighbors search based on layered locality sensitive B-tree[J]. Computer Science, 2023, 50(4): 32-39.
[3] BORUTTA F, NASCIMENTO M A, NIEDERMAYER J, et al. Reverse k-nearest neighbour schedules in time-dependent road networks[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2015: 1-10.
[4] GAO Y J, ZHENG B H, CHEN G C, et al. Continuous visible nearest neighbor query processing in spatial databases[J]. The VLDB Journal, 2011, 20(3): 371-396.
[5] 贺广福, 薛源海, 陈翠婷, 等. 基于容忍因子的近似最近邻混合查询算法[J]. 大数据, 2024, 10(1): 17-34.
HE G F, XUE Y H, CHEN C T, et al. Approximate nearest neighbor hybrid query algorithm based on tolerance factor[J]. Big Data Research, 2024, 10(1): 17-34.
[6] GOTOH Y, OKUBO C. A searching method for bichromatic reverse k-nearest neighbor with network Voronoi diagram[C]//Proceedings of the 14th International Conference on Advances in Mobile Computing and Multi Media. New York: ACM, 2016: 71-78.
[7] POURNAJAF L, TAHMASEBIAN F, XIONG L, et al. Privacy preserving reverse k-nearest neighbor queries[C]//Proceedings of the 2018 19th IEEE International Conference on Mobile Data Management. Piscataway: IEEE, 2018: 177-186.
[8] KAMOUSI P, CHAN T M, SURI S. Closest pair and the post office problem for stochastic points[J].?Computational Geometry,?2014, 47(2): 214-223.
[9] LI G B, TANG J E. A new DR-tree K-nearest neighbor query algorithm based on direction relationship[C]//Proceedings of the 2nd Conference on Environmental Science and Information Application Technology. Piscataway: IEEE, 2010: 246-250.
[10] YAO B, CHEN Z P, GAO X F, et al. Flexible aggregate nearest neighbor queries in road networks[C]//Proceedings of the 2018 IEEE 34th International Conference on Data Engineering. Piscataway: IEEE, 2018: 761-772.
[11] ZENG Y F, CHEN G, LI K L, et al. M-Skyline: taking sunk cost and alternative recommendation in consideration for skyline query on uncertain data[J]. Knowledge-Based Systems, 2019, 163: 204-213.
[12] DUAN J X, ZHAI W X, CHENG C Q. A spatial grid index based on inverted index and its query method[C]//Proceedings of the 2017 IEEE International Geoscience and Remote Sensing Symposium. Piscataway: IEEE, 2017: 6189-6192.
[13] FINKEL R A, BENTLEY J L. Quad trees a data structure for retrieval on composite keys[J]. Acta Informatica, 1974, 4(1): 1-9.
[14] HU F, YANG C W, JIANG Y Y, et al. A hierarchical indexing strategy for optimizing Apache Spark with HDFS to efficiently query big geospatial raster data[J]. International Journal of Digital Earth, 2020, 13(3): 410-428.
[15] ROBINSON J T. The K-D-B-Tree: a search structure for large multidimensional dynamic indexes[C]//Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1981: 10-18.
[16] CHAUDHRY N, YOUSAF M M. A hash-based index for processing frequent updates and continuous location-based range queries[J]. Knowledge and Information Systems, 2023, 65(10): 4233-4271.
[17] GUTTMAN A. R-Trees: a dynamic index structure for spatial searching[C]//Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1984: 47-57.
[18] 董鹏, 杨崇俊, 刘冬林, 等. 基于R+树的地图叠加分析双重循环算法[J]. 中国图象图形学报, 2003, 8(6): 107-114.
DONG P, YANG C J, LIU D L, et al. A dual loop map overlay algorithm based on R+Tree[J]. Journal of Image and Graphics, 2003, 8(6): 107-114.
[19] SUN L, JIN B. Improving NoSQL spatial-query processing with server-side in-memory R*-Tree indexes for spatial vector data[J].?Sustainability,?2023, 15(3): 2442.
[20] KAMEL I, FALOUTSOS C. Hilbert R-Tree: an improved R-tree using fractals[C]//Proceedings of the 20th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann, 1994: 500-509.
[21] PAOLOCIACCIA M P. M-Tree: an efficient access method for similarity search in metric spaces[C]//Proceedings of the 23rd International Conference on Very Large Data Bases.San Francisco: Morgan Kaufmann, 1997: 357-368.
[22] PFOSER D, JENSEN C S, THEODORIDIS Y. Novel approaches to the indexing of moving object trajectories[C]//Proceedings of the 26th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2000:395-406.
[23] 周芹, 钟耳顺, 黄耀欢, 等. 大型空间数据库的并发索引策略CQR树[J]. 武汉大学学报(信息科学版), 2009, 34(7): 856-858.
ZHOU Q, ZHONG E S, HUANG Y H, et al. CQR-Tree: concurrent strategy for spatial index structure in spatial database[J]. Geomatics and Information Science of Wuhan University, 2009, 34(7): 856-858.
[24] SHI R M, QI X L. Research on mixed indexing model for cloud points[C]//Proceedings of the 2012 IEEE International Geoscience and Remote Sensing Symposium. Piscataway: IEEE, 2012: 5301-5303.
[25] 李佳佳, 王波涛, 王国仁, 等. 不确定移动对象的查询处理技术研究综述[J]. 计算机科学与探索, 2013, 7(12): 1057-1072.
LI J J, WANG B T, WANG G R, et al. A survey of query processing techniques over uncertain mobile objects[J]. Journal of Frontiers of Computer Science and Technology, 2013, 7(12): 1057-1072.
[26] XU J L, ZHENG B, LEE W C, et al. The D-tree: an index structure for planar point queries in location-based wireless services[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1526-1542.
[27] 胡久乡, 何松, 钟瑜. 空间数据库网格索引机制的最优划分[J]. 计算机学报, 2002, 25(11): 1227-1230.
HU J X, HE S, ZHONG Y. Optimum mesh-indexing for spatial database[J]. Chinese Journal of Computers, 2002, 25(11): 1227-1230.
[28] 章登义, 李想. 一种基于密度网格索引的k-最近邻查询算法[J]. 电子学报, 2017, 45(2): 376-383.
ZHANG D Y, LI X. A k-nearest neighbor query algorithm for density grid-based index[J]. Acta Electronica Sinica, 2017, 45(2): 376-383.
[29] LIU H, YAN J N, WANG J L, et al. HGST: a Hilbert-GeoSOT spatio-temporal meshing and coding method for efficient spatio-temporal range query on massive trajectory data[J]. ISPRS International Journal of Geo-Information, 2023, 12(3): 113.
[30] LEI Y, TONG X C, WANG D L, et al. W-Hilbert: a W-shaped Hilbert curve and coding method for multiscale geospatial data index[J]. International Journal of Applied Earth Observation and Geoinformation, 2023, 118: 103298.
[31] 陈俊杰, 朱维, 王宪锴, 等. 空间索引技术及其GIS应用综述[J]. 地理与地理信息科学, 2024, 40(2): 1-10.
CHEN J J, ZHU W, WANG X K, et al. A review of spatial index and its applications in GIS[J]. Geography and Geo-Information Science, 2024, 40(2): 1-10.
[32] SAMET H. The quadtree and related hierarchical data structures[J]. ACM Computing Surveys, 1984, 16(2): 187-260.
[33] 赵慧慧, 赵凡, 陈仁海, 等. 基于地理空间大数据的高效索引与检索算法[J]. 计算机研究与发展, 2020, 57(2): 333-345.
ZHAO H H, ZHAO F, CHEN R H, et al. Efficient index and query algorithm based on geospatial big data[J]. Journal of Computer Research and Development, 2020, 57(2): 333-345.
[34] 陈根深, 刘刚, 董洋, 等. 基于Inverted-B+树的海量三维地质块体模型高效索引方法[J]. 计算机科学, 2025, 52(8): 146-153.
CHEN G S, LIU G, DONG Y, et al. An efficient indexing method for massive 3D geological block models based on Inverted-B+ tree[J]. Computer Science, 2025, 52(8): 146-153.
[35] SELLIS T, ROUSSOPOULOS N, FALOUTSOS C. The R+-tree: a dynamic index for multi-dimensional objects[C]//Proceedings of the 13th International Conference on Very Large Data Bases, 1987: 507-518.
[36] BECKMANN N, KRIEGEL H P, SCHNEIDER R, et al. The R*-tree: an efficient and robust access method for points and rectangles[C]//Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. New York: ACM, 1990: 322-331.
[37] XIONG W, WU Y, CAO J Z, et al. IB-CBB: an improved spatial index considering intersection based on clipped bounding boxes[J]. Annals of GIS, 2024, 30(2): 233-250.
[38] FU Y C, HU Z Y, GUO W, et al. QR-tree: a hybrid spatial index structure[C]//Proceedings of the 2003 International Conference on Machine Learning and Cybernetics. Piscataway: IEEE, 2003: 459-463.
[39] ?ALTENIS S, JENSEN C S, LEUTENEGGER S T, et al. Indexing the positions of continuously moving objects[C]//Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2000: 331-342.
[40] TAO Y F, PAPADIAS D, SUN J M. The TPR*-tree an optimized spatio-temporal access method for predictive queries[C]//Proceedings of the 29th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2003: 790-801.
[41] ZHENG Y L. A fast index method for moving objects on full temporal query[C]//Proceedings of the 2011 3rd International Conference on Computer Research and Development. Piscataway: IEEE, 2011: 205-208.
[42] 马龙, 姜岚, 张正义, 等. 基于十六叉树-多尺度表达R树的TGIS时空数据索引算法[J]. 计算机应用与软件, 2022, 39(9): 56-64.
MA L, JIANG L, ZHANG Z Y, et al. Spatiotemproal data indexing algorithm for TGIS based on hex tree and multi-scale represented R-tree[J]. Computer Applications and Software, 2022, 39(9): 56-64.
[43] 孟祥福, 翁雪, 徐永杰. 时空数据查询技术研究综述[J]. 计算机科学与探索, 2025, 19(8): 2001-2023.
MENG X F, WENG X, XU Y J. Review of research on spatio-temporal data query technologies[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(8): 2001-2023.
[44] ZHANG Y N, ZHANG A M, GAO M, et al. Research on three-dimensional electronic navigation chart hybrid spatial index structure based on quadtree and R-tree[J]. ISPRS International Journal of Geo-Information, 2022, 11(5): 319.
[45] KOLAHDOUZAN M, SHAHABI C. Voronoi-based K nearest neighbor search for spatial network databases[C]//Proceedings of the 30th International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann, 2004: 840-851.
[46] SMITH E, TREFFTZ C, DEVRIES B. A divide-and-conquer algorithm for computing voronoi diagrams[C]//Proceedings of the 2020 IEEE International Conference on Electro Information Technology. Piscataway: IEEE, 2020: 495-499.
[47] 王淼. 基于Voronoi图的最近邻查询的研究[J]. 微计算机信息, 2008, 24(33): 259-260.
WANG M. Research on nearest neighbors queries for moving query point based on Voronoi diagrams[J]. Microcomputer Information, 2008, 24(33): 259-260.
[48] SHARIFZADEH M, SHAHABI C. VoR-Tree: R-trees with voronoi diagrams for efficient processing of spatial nearest neighbor queries[J]. Proceedings of the VLDB Endowment, 2010, 3(1): 1231-1242.
[49] 黄冬梅, 邓斌, 赵丹枫. 带权不确定图的K最近邻查询算法[J]. 计算机应用与软件, 2016, 33(2): 212-216.
HUANG D M, DENG B, ZHAO D F. K-nearest neighbours query in weighted uncertain graph[J]. Computer Applications and Software, 2016, 33(2): 212-216.
[50] 杨泽雪, 王阿川, 李陆, 等. 障碍环境中可视反向视域K最近邻查询[J]. 计算机工程, 2022, 48(8): 258-265.
YANG Z X, WANG A C, LI L, et al. Visible reverse view field K-nearest neighbor queries in obstacle environment[J]. Computer Engineering, 2022, 48(8): 258-265.
[51] 李松, 宾婷亮, 郝晓红, 等. 道路网多用户偏好Top-k天际线查询方法[J]. 计算机研究与发展, 2023, 60(10): 2348-2358.
LI S, BIN T L, HAO X H, et al. Multi-user preference Top-k skyline query method based on road network[J]. Journal of Computer Research and Development, 2023, 60(10): 2348-2358.
[52] 宋宝燕, 孟彦伟, 丁琳琳. 基于Voronoi划分的位置数据KNN查询处理方法[J]. 计算机科学与探索, 2019, 13(12): 2015-2028.
SONG B Y, MENG Y W, DING L L. KNN query method for location data based on Voronoi partition[J]. Journal of Frontiers of Computer Science and Technology, 2019, 13(12): 2015-2028.
[53] GUO X, YANG X C. Direction-aware nearest neighbor query[J]. IEEE Access, 2019, 7: 30285-30301.
[54] AGARWAL P K, ARONOV B, HAR-PELED S, et al. Nearest neighbor searching under uncertainty II[J]. ACM Transactions on Algorithms, 2016, 13(1): 1-25.
[55] KORN F, MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries[J]. ACM SIGMOD Record, 2000, 29(2): 201-212.
[56] YANG C Y, LIN K I. An index structure for efficient reverse nearest neighbor queries[C]//Proceedings of the 17th International Conference on Data Engineering. Piscataway: IEEE, 2001: 485-492.
[57] 郝忠孝, 刘永山. 空间对象的反最近邻查询[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.
[58] 刘润涛, 梁建创. 基于新型索引结构的反最近邻查询[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.
[59] 李松, 郝忠孝. 移动对象的动态反向最近邻查询技术[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.
[60] 王淼, 郝忠孝. 基于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.
[61] DUAN X Q, LI L, GE Y, et al. Exact Voronoi diagram for topographic spatial analysis[J]. GIScience & Remote Sensing, 2023, 60(1): 2171703.
[62] YANG S Y, CHEEMA M A, LIN X M, et al. Reverse k nearest neighbors queries and spatial reverse top-k queries[J]. The VLDB Journal, 2017, 26(2): 151-176.
[63] HIDAYAT A, YANG S Y, CHEEMA M A, et al. Reverse approximate nearest neighbor queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(2): 339-352.
[64] WANG S, BAO Z F, CULPEPPER J S, et al. Reverse k nearest neighbor search over trajectories[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(4): 757-771.
[65] 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.
[66] YU Z Q, LIU Y, YU X H, et al. Scalable distributed processing of K nearest neighbor queries over moving objects[J]. IEEE Transactions on Knowledge and Data Engineering, 2015, 27(5): 1383-1396.
[67] SAFAEE S, MIRABI M, RAHMANI A M, et al. A distributed B+Tree indexing method for processing range queries over streaming data[J]. Cluster Computing, 2024, 27(2): 1251-1274.
[68] GARCíA-GARCíA F, CORRAL A, IRIBARNE L, et al. RkNN query processing in distributed spatial infrastructures: a performance study[C]//Proceedings of the 7th International Conference on Model and Data Engineering. Cham: Springer, 2017: 200-207.
[69] 杨泽雪, 张毅, 李陆, 等. 基于Spark的并行反向k最近邻查询[J]. 计算机工程与设计, 2022, 43(12): 3340-3347.
YANG Z X, ZHANG Y, LI L, et al. Parallel reverse k nearest neighbor query based on Spark[J]. Computer Engineering and Design, 2022, 43(12): 3340-3347.
[70] SONG Z, ROUSSOPOULOS N. K-nearest neighbor search for moving query point[C]//Proceedings of the 2001 International Symposium on Spatial and Temporal Databases. Berlin, Heidelberg: Springer, 2001: 79-96.
[71] TAO Y F, PAPADIAS D. Time-parameterized queries in spatio-temporal databases[C]//Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2002: 334.
[72] 孙冬璞, 郝晓红, 郝忠孝. 频繁更新移动对象的索引方法[J]. 计算机工程, 2013, 39(11): 52-56.
SUN D P, HAO X H, HAO Z X. Indexing method of moving objects with frequent update[J]. Computer Engineering, 2013, 39(11): 52-56.
[73] XIAO Y Y, WANG H Y, WANG F Y, et al. Efficient algorithm for continuous nearest neighbor queries based on the VDTPR-tree[J]. Journal of Computational Information Systems, 2008, 4(2): 527-534.
[74] WANG M, YU J R. Continuous near neighbor sequence queries in spatial databases[J]. ICIC Express Letters, Part B: Applications, 2013, 4(4): 921- 927.
[75] WANG Y J. Research in continuous nearest neighbor queries[J]. Advanced Materials Research, 2012, 457/458: 461-466.
[76] 张丽平, 郭莹莹, 李松, 等. 路网中线段反k最近邻查询研究[J]. 计算机科学与探索, 2017, 11(6): 908-920.
ZHANG L P, GUO Y Y, LI S, et al. Line reverse k nearest neighbor query in road network[J]. Journal of Frontiers of Computer Science and Technology, 2017, 11(6): 908-920.
[77] 冯惠妍, 郭俊凤. 道路网络中的连续最近邻查询[J]. 计算机工程, 2010, 36(8): 79-82.
FENG H Y, GUO J F. Continuous nearest neighbor queries in road network[J]. Computer Engineering, 2010, 36(8): 79-82.
[78] 刘德高, 李晓宇. 基于道路网的连续k近邻查询算法[J]. 计算机应用, 2013, 33(7): 1964-1968.
LIU D G, LI X Y. Continuous k nearest neighbor query algorithm based on road network[J]. Journal of Computer Applications, 2013, 33(7): 1964-1968.
[79] SACK J R, URRUTIA J. Closest-point problems in computational geometry[M]//Handbook of computational geometry. Ottawa: Elsevier Science, 2000: 877-935.
[80] CORRAL A, MANOLOPOULOS Y, THEODORIDIS Y, et al. Algorithms for processing K-closest-pair queries in spatial databases[J]. Data & Knowledge Engineering, 2004, 49(1): 67-104.
[81] 张丽平, 李松. 网络环境中近邻对的查询方法[J]. 计算机技术与发展, 2008, 18(6): 119-121.
ZHANG L P, LI S. Methods of near neighbor pair query in network[J]. Computer Technology and Development, 2008, 18(6): 119-121.
[82] 张丽平, 李松. 数据集中强邻近对的查询方法[J]. 计算机工程与设计, 2008, 29(16): 4353-4355.
ZHANG L P, LI S. Methods of strong neighborhood pair query in datasets[J]. Computer Engineering and Design, 2008, 29(16): 4353-4355.
[83] 张丽平, 李松, 刘文强, 等. 强邻近对查询的新方法[J]. 计算机工程与应用, 2009, 45(27): 123-126.
ZHANG L P, LI S, LIU W Q, et al. New methods of strong neighborhood pair query[J]. Computer Engineering and Applications, 2009, 45(27): 123-126.
[84] 李松, 张丽平, 郝忠孝. 动态数据集环境下的强邻近对查询[J]. 计算机研究与发展, 2015, 52(3): 749-759.
LI S, ZHANG L P, HAO Z X. Strong neighborhood pair query in dynamic dataset[J]. Journal of Computer Research and Development, 2015, 52(3): 749-759.
[85] SHAN J, ZHANG D, SALZBERG B. On spatial-range closest-pair query[C]//Proceedings of the 2003?International Symposium on Spatial and Temporal Databases. Berlin, Heidelberg: Springer, 2003: 252-269.
[86] 郝忠孝, 王玉东, 何云斌. 空间数据库平面线段近邻查询问题研究[J]. 计算机研究与发展, 2008, 45(9): 1539-1545.
HAO Z X, WANG Y D, HE Y B. Line segment nearest neighbor query of spatial database[J]. Journal of Computer Research and Development, 2008, 45(9): 1539-1545.
[87] 杨泽雪, 郝忠孝. 基于Voronoi图的线段最近对查询[J]. 计算机科学, 2012, 39(6): 143-146.
YANG Z X, HAO Z X. Line segment closest pair queries based on voronoi diagram[J]. Computer Science, 2012, 39(6): 143-146.
[88] ZHANG J, PAPADIAS D, MOURATIDIS K, et al. Spatial queries in the presence of obstacles[C]//Proceedings of the 9th International Conference on Extending Database Technology. Berlin, Heidelberg: Springer, 2004: 366-384.
[89] 鲍金玲, 王斌, 杨晓春, 等. 路网环境下的最近邻查询技术[J]. 软件学报, 2018, 29(3): 642-662.
BAO J L, WANG B, YANG X C, et al. Nearest neighbor query in road networks[J]. Journal of Software, 2018, 29(3): 642-662.
[90] GAO Y J, ZHENG B H. Continuous obstructed nearest neighbor queries in spatial databases[C]//Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2009: 577-590.
[91] XIA C Y, HSU D, TUNG A K H. A fast filter for obstructed nearest neighbor queries[C]//Proceedings of the 21st British National Conference on Databases. Berlin, Heidelberg: Springer, 2004: 203-215.
[92] NUTANONG S, TANIN E, ZHANG R. Incremental evaluation of visible nearest neighbor queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2010, 22(5): 665-681.
[93] WANG Y Q, ZHANG R, XU C F, et al. Continuous visible k nearest neighbor query on moving objects[J]. Information Systems, 2014, 44: 1-21.
[94] LI C W, GU Y, QI J Z, et al. A safe region based approach to moving KNN queries in obstructed space[J]. Knowledge and Information Systems, 2015, 45(2): 417-451.
[95] 李松, 张丽平, 刘艳, 等. 障碍物环境下的动态单纯型连续近邻链查询[J]. 计算机工程, 2014, 40(8): 52-57.
LI S, ZHANG L P, LIU Y, et al. Dynamic simple continues near neighbor chain query with obstacles[J]. Computer Engineering, 2014, 40(8): 52-57.
[96] 张丽平, 李松, 郝晓红, 等. 障碍物增减情况下的单纯型连续近邻链查询[J]. 计算机工程与应用, 2015, 51(11): 99-103.
ZHANG L P, LI S, HAO X H, et al. Simple continues near neighbor chain query with increase and decrease of obstacles[J]. Computer Engineering and Applications, 2015, 51(11): 99-103.
[97] ZHANG L P, LIU L, HAO X H, et al. Voronoi-based group reverse k nearest neighbor query in obstructed space[J]. Computer Research and Development, 2017, 54(4): 861-871.
[98] 朱怀杰, 王佳英, 王斌, 等. 障碍空间中保持位置隐私的最近邻查询方法[J]. 计算机研究与发展, 2014, 51(1): 115-125.
ZHU H J, WANG J Y, WANG B, et al. Location privacy preserving obstructed nearest neighbor queries[J]. Journal of Computer Research and Development, 2014, 51(1): 115-125.
[99] YI X, PAULET R, BERTINO E, et al. Practical approximate k nearest neighbor queries with location and query privacy[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(6): 1546-1559.
[100] 李博涵, 张潮, 李东静, 等. 支持室内障碍空间的DSP-Topk查询优化算法研究[J]. 计算机研究与发展, 2017, 54(3): 557-569.
LI B H, ZHANG C, LI D J, et al. A DSP-Topk query optimization algorithm supporting indoor obstacle space[J]. Journal of Computer Research and Development, 2017, 54(3): 557-569.
[101] 杨泽雪, 郝忠孝. 空间数据库中的组障碍最近邻查询研究[J]. 计算机研究与发展, 2013, 50(11): 2455-2462.
YANG Z X, HAO Z X. Group obstacle nearest neighbor query in spatial database[J]. Journal of Computer Research and Development, 2013, 50(11): 2455-2462.
[102] BORZSONY S, KOSSMANN D, STOCKER K. The skyline operator[C]//Proceedings of the 17th International Conference on Data Engineering. Piscataway: IEEE, 2001: 421-430.
[103] SHARIFZADEH M, SHAHABI C. The spatial skyline queries[C]//Proceedings of the 32nd International Conference on Very Large Data Bases. New York: ACM, 2006: 751-762.
[104] MAO R. Spatial skyline query problem in Euclidean and road-network spaces[D]. Burnaby: Simon Fraser University, 2020.
[105] CAI Z, CUI X R, SU X, et al. Continuous road network-based skyline query for moving objects[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(12): 7383-7394.
[106] LIN Q, ZHANG Y, ZHANG W, et al. General spatial skyline operator[C]//Proceedings of the 17th International Conference on Database Systems for Advanced Applications. Berlin, Heidelberg: Springer, 2012: 494-508.
[107] CHEN Z M, AREFIN M S, MORIMOTO Y. Skyline queries for spatial objects: a method for selecting spatial objects based on surrounding environments[C]//Proceedings of the 2012 3rd International Conference on Networking and Computing. Piscataway: IEEE, 2012: 215-220.
[108] YOU G W, LEE M W, IM H, et al. The farthest spatial skyline queries[J]. Information Systems, 2013, 38(3): 286-301.
[109] KOSSMANN D, RAMSAK F, ROST S. Shooting stars in the sky[C]//Proceedings of the 28th International Conference on Very Large Databases. San Francisco: Morgan Kaufmann, 2002: 275-286.
[110] PAPADIAS D, TAO Y F, FU G, et al. Progressive skyline computation in database systems[J]. ACM Transactions on Database Systems, 2005, 30(1): 41-82.
[111] GUO X, ISHIKAWA Y, GAO Y J. Direction-based spatial skylines[C]//Proceedings of the 9th ACM International Workshop on Data Engineering for Wireless and Mobile Access. New York: ACM, 2010: 73-80.
[112] ATTIQUE M, AFZAL M, ALI F, et al. Geo-social top-k and skyline keyword queries on road networks[J]. Sensors, 2020, 20(3): 798.
[113] CHEN G, ZHAO J W, GAO Y J, et al. Time-aware Boolean spatial keyword queries[J]. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(11): 2601-2614.
[114] DONG L G, LIU G H, CUI X W, et al. G-skyline query over data stream in wireless sensor network[J]. Wireless Networks, 2020, 26(1): 129-144.
[115] DZOLKHIFLI Z, IBRAHIM H, HASSIN M H B M. Review on skyline query processing techniques over data stream[C]//Proceedings of the 2021 International Conference on Software Engineering & Computer Systems and the 4th International Conference on Computational Science and Information Management. Piscataway: IEEE, 2021: 443-446.
[116] JIANG T, ZHANG B, LIN D, et al. Efficient column-oriented processing for mutual subspace skyline queries[J]. Soft Computing, 2020, 24(20): 15427-15445.
[117] 魏亮, 林子雨, 赖永炫. DFTS: 面向大数据集的Top-k Skyline查询算法[J]. 计算机科学, 2019, 46(5): 150-156.
WEI L, LIN Z Y, LAI Y X. DFTS: a Top-k Skyline query for large datasets[J]. Computer Science, 2019, 46(5): 150-156.
[118] 王海翔, 郑吉平, 王永阁. 结合非空间属性的通用Skyline查询处理技术[J]. 计算机科学与探索, 2016, 10(7): 936-947.
WANG H X, ZHENG J P, WANG Y G. General Skyline query processing technology combining with non-spatial attributes[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(7): 936-947.