Approximate nearest neighbor retrieval method and retrieval system for high dimensional data based on satellite system diagram

Abstract

The present invention discloses an approximate nearest neighbor retrieval method and retrieval system for high-dimensional data based on a satellite system diagram. The approximate nearest neighbor retrieval method for high-dimensional data based on the satellite system diagram comprises: (1) establishing a satellite system diagram for a high-dimensional database point set; (2) for to-be-retrievedpoints, randomly selecting a plurality of data points as a candidate point set, and performing greedy approximate nearest neighbor retrieval on the satellite system diagram; and (3) taking a given number of points in the obtained candidate point set as a result, namely, a nearest neighbor point set of the to-be-retrieved points. By virtue of the technical scheme of the present invention, logarithmic retrieval complexity can be achieved, so that not only the retrieval precision in a certain period of time can be greatly improved, but also the memory footprint and the time required for indexingduring retrieval can be greatly reduced.

Description

technical field [0001] The invention relates to the technical field of data retrieval, in particular to an approximate nearest neighbor retrieval method and retrieval system for high-dimensional data based on a satellite system map. Background technique [0002] In recent years, approximate nearest neighbor retrieval technology has become more and more widely used, especially in computer vision, machine learning, data mining, natural language processing, text and image retrieval and other fields that need to deal with large-scale high-dimensional data. The object of approximate nearest neighbor retrieval is a large-scale high-dimensional data point collection, and it is required to quickly find several data points closest to a certain point to be retrieved among these data points. [0003] For large-scale high-dimensional data, the computational overhead of traversal brute force retrieval in the original space is expensive. In order to improve the efficiency of nearest neigh...

AI Technical Summary

Problems solved by technology

[0007] However, the NSG method needs to select the navigation point when searching, and cannot randomly select the initial point

At the same time, the edge-cutting strategy of this method uses the rule of mutual exclusion to select edges, mainly referring to the length of the edge, and cannot adjust the angle size according to the distribution of the data set to adapt to the characteristics of the data set, so it cannot radiate the surrounding adjacent areas of each point in the data set

Images