FAST SEARCH FOR NEARBY OBJECTS

Abstract

The subject of study. The article proposes a method of fast search for the closest objects in Euclidean space, which is based on the necessary proximity conditions proved for two metrics. The method involves randomly selecting landmarks, projecting objects into a k-dimensional space, and using special hash structures to speed up the search. It has been experimentally proven that the proposed method outperforms known analogs in terms of execution speed. The aim of the work was to develop an efficient algorithm for finding close objects that can be used in intelligent search engines, big data processing technologies, and learning systems for knowledge clustering. Tasks. To develop a method that would allow to quickly find objects that satisfy the proximity conditions in Euclidean space. Prove the theoretical foundations of the method, including the necessary proximity conditions, and experimentally test its effectiveness in comparison with existing approaches. Consider two cases: search for ordered m-ary trees and for strings using the Levenshtein distance. Methods used. The method is based on randomly selecting landmarks, projecting objects into a k-dimensional space, and using hash structures to filter candidates. To evaluate the effectiveness, experiments have been conducted comparing the execution time of the proposed method with the basic and modified analogs. The theoretical foundations include the proof of proximity conditions that reduce the number of computations. Results. Experiments have shown that the proposed method (Nearest Hash) outperforms the known analogs (Basic and Modified) by 1.67-3.80 times in terms of search speed, depending on the size of the dataset. For trees, we use editing metrics that take into account the operations of renaming, deleting, and inserting nodes. For strings, the Levenshtein distance is used. The results confirm that the method effectively eliminates unnecessary computations at the first stage and speeds up the search due to the hash matrix. The scientific novelty of the work lies in the introduction of the necessary proximity conditions that allow to increase the search efficiency. The proposed method can be used in search engines, big data processing, and educational technologies. Further research will be aimed at optimizing the choice of landmarks and expanding the application of the method in practical problems.