Fast recognition algorithm of similarity data in big data set

Abstract

A fast recognition algorithm of similarity data in a big data set comprises the steps of correcting the length of a data file, calculating the distance between sampling data blocks, calculating the positions of the sampling data blocks, extracting the data blocks, extracting one data block at the head of the data file and one data block at the tail of the data file, calculating the characteristic value of the extracted data blocks and judging the similarity of data through set operation. According to the fast recognition algorithm, the space-time overhead does not increase along with increase of the size of the data file, the length of the data file is corrected through a position influence factor, recognition failure of the similarity data due to position offset of the sampling data blocks can be avoided, and the effectiveness and the accuracy of recognition of the similarity data are effectively guaranteed through the information retrieval method.

Description

technical field [0001] The invention relates to the technical field of big data processing, in particular to a fast recognition algorithm for similarity data under a big data set. Background technique [0002] In 2013, IDC predicted that the total amount of global data will reach 4ZB by 2014, and the data growth will reach 50% compared with 2012. IBM uses 4V: volume, variety, value, and veracity to describe the characteristics of these data, which directly shows that these data are very complex. For example, there are a lot of structured, semi-structured and unstructured data in these data. It is precisely because of these complex characteristics that there are still many unsolved problems in the existing data processing methods. Among them, file similarity plays a very important role in data processing methods. For example, cluster analysis in data mining, plagiarism detection, remote file backup, identification of similar data in the file system, identification of hot d...

AI Technical Summary

Problems solved by technology

When using the traditional similarity data recognition algorithm to calculate the summary of the data, it takes a lot of CPU time and a lot of memory space, and it also causes a lot of disk IO

It should be pointed out that these disk accesses are random, which seriously reduces the performance of similarity data identification

In addition, the computational overhead of traditional acacia data recognition algorithms grows with the growth of the dataset

[0005] 2. Shorten the time for similarity data identification: Under the dataset, traditional similarity data identification algorithms need a lot of time to identify similar data, which directly leads to very serious delays

[0007] Although the typical similarity algorithms Shingle and Simhash can effectively identify similar data, the time and space overhead of these two algorithms is very large in large data sets. In particular, the time and space overhead of these two algorithms doubles as the size of the data file increases.

Therefore, the two typical similarity algorithms cannot effectively solve the above challenges under large data sets

[0008] Although the traditional sampling similarity algorithm has a short recognition time and fixed overhead, which does not increase with the increase of the length of the data file, the traditional sampling similarity algorithm is very sensitive to the modification of the content of the data file

For example, a single byte modification of the data file content will cause the traditional similarity recognition algorithm to fail.

Images