High-dimensional data similarity connection inquiry method and device based on distance partition tree

Abstract

The embodiment of the invention provides a high-dimensional data similarity connection inquiry method and device based on a distance partition tree. The method comprises the steps of: acquiring high-dimensional original data, and mapping the original data into a one-dimensional space; according to a first distance threshold and a chi square distribution property, determining a second distance threshold, and according to the original data and the second distance threshold, constructing the distance partition tree; traversing the distance partition tree and carrying out comparison on each node in the distance partition tree to obtain a candidate similar node pair set; and calculating an original distance between the original data included in each candidate similar node pair in the candidatesimilar node pair set, and carrying out comparison on each original distance and the first distance threshold to obtain a similarity inquiry result. The device is used for executing the method. According to the embodiment of the invention, complexity of calculation is reduced by mapping the high-dimensional original data to the one-dimensional space, candidate results can be found with low cost bythe distance partition tree, and a filtering effect is improved, so that inquiry efficiency is greatly improved.

Description

technical field [0001] The present invention relates to the technical field of data processing, in particular to a high-dimensional data similarity connection query method and device based on mapping space division. Background technique [0002] With the development of data acquisition technology and the advancement of data acquisition equipment, the data scale, data accuracy, and data dimension have all increased rapidly in unprecedented ways. The dimensions of many types of data can reach thousands of dimensions, or even tens of thousands of dimensions, such as graphic images, videos, trajectories, time series, etc. The purpose of high-dimensional data similarity join query is to find data pairs whose similarity is greater than or equal to a given similarity threshold or whose distance is less than or equal to a given distance threshold from a large number of high-dimensional data sets. Important applications, such as image clustering, document deduplication, similar vide...

AI Technical Summary

Problems solved by technology

[0003] The similarity join query of massive high-dimensional data is a computationally intensive operation. With the continuous increase of data size and dimension, traditional centralized processing methods and index-based algorithms can no longer meet the performance requirements.

[0004] Similarity query is an important operation that is widely used. At present, a lot of research has been done on it. For the performance and expansion problems faced by large-scale data similarity join query, in the prior art, the MapReduce framework is used to solve it , however, for high-dimensional data, when the similarity query is performed through the MapReduce framework, its computational complexity is high, which leads to the problem of low query efficiency

Images