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

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 and review 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 studying and 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 ahead to future development trends, providing reference and inspiration for further research in spatial database theory.

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