Approximate k ‐Nearest Neighbor Query Algorithm of Two‐Level Index Based on SOM Clustering in High‐Dimensional Space

ABSTRACT To address the limitations of traditional high‐dimensional A k NN (Approximate k ‐nearest neighbor) query algorithms, which often overlook the data distribution issues, a novel method leveraging SOM (self‐organizing map) neural network clustering for high‐dimensional data A k NN queries is proposed. To efficiently index bloc k ‐distributed data after clustering, the concept of clustering polygons is introduced to partition the clustered data into points and polygons. Subsequently, a new hierarchical index structure, termed the VG index, is proposed. The VG index, combined with Voronoi diagrams, enables effective point/plane division and indexing. Based on this framework, five theorems for data filtering and refinement are given. A dataset pruning algorithm and an approximate k NN query algorithm are presented. The proposed method also achieves dynamic refinement through a dual‐index structure, significantly boosting query speed. Experimental results demonstrate that the approach can effectively handle high‐dimensional A k NN queries. Additionally, the VG index provides valuable insights for indexing block‐distributed datasets in two‐dimensional space.