Data hashing method, data processing method, and data processing system using similarity-based hashing algorithm

• US 20070130188A1
• Filed: 12/06/2006
• Published: 06/07/2007
• Est. Priority Date: 12/07/2005
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Oh, Jintae, Kim, Changhoon, Jang, Jong, Yi, Sungwon, Moon, Hwa
• Granted Patent: US 7,617,231 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: H04L 9/3231 Biological data, e.g. fingerprint, voice or retina network architectures or network communication protocols for supporting authentication of entities using biometrical features in a packet data network H04L63/0861
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

Provided are a data hashing method, a data processing method, and a data processing system using a similarity-based hashing (SBH) algorithm in which the same hash value is calculated for the same data and the more similar data, the smaller difference in the generated hash values. The data hashing method includes receiving computerized data, and generating a hash value of the computerized data using the SBH algorithm in which two data are the same if calculated hash values are the same and two data are similar if the difference of calculated hash values is small. Therefore, a search, comparison, and classification of data can be quickly processed within a time complexity of O(1) or O(n) since the similarity/closeness of data content are quantified by that of the corresponding hash values.

Claims

1. A data hashing method using a similarity-based hashing (SBH) algorithm, the data hashing method comprising:

receiving computerized data; and

generating a hash value of the computerized data using the SBH algorithm in which two data are the same if calculated hash values are the same and two data are similar if the difference of calculated hash values is small.

2. The data hashing method of claim 1, wherein the computerized data is one of the group consisting of a computer file document, a packet transferred through a network, and a database query, represented with a bit string.

3. The data hashing method of claim 1, wherein the generating of the hash value of the computerized data using the SBH algorithm comprises:

calculating a fingerprint value from the content of the computerized data;

changing a component value of an Nth-order hash vector to correspond to the fingerprint value according to a predetermined rule;

determining whether the entire amount of the content of the computerized data has been processed; and

if it is determined that the entire amount of the content of the computerized data has been processed, converting the Nth-order hash vector to the hash value.

4. The data hashing method of claim 3, wherein if it is determined that the entire amount of the content of the computerized data has not been processed, a subsequent fingerprint value is calculated from the content of the computerized data by returning to the calculating of a fingerprint value.

5. The data hashing method of claim 3, wherein the calculating of the fingerprint value comprises:

extracting a shingle, which is a continuous or discontinuous byte-string having a predetermined length, from the computerized data; and

generating a fingerprint value using a data hashing algorithm which satisfies uniformity and randomness criteria for the shingle and has a low possibility of collision.

6. The data hashing method of claim 5, wherein the data hashing algorithm is one of a Rabin-Karp fingerprinting algorithm, a byte-wise foldering algorithm, and an XORing algorithm.

7. The data hashing method of claim 3, wherein the changing of the component value of the Nth-order hash vector comprises:

grouping the fingerprint value in one of N groups by applying the predetermined rule to the fingerprint value or a portion of the fingerprint value; and

if the fingerprint value belongs to a certain group among the N groups, increasing a component value of the Nth-order hash vector, which corresponds to the certain group.

8. The data hashing method of claim 7, wherein an initial value of each component of the Nth-order hash vector is set to a uniform or non-uniform integer, and

the increasing of the component value of the Nth-order hash vector occurs in the same unit for all groups or in a different unit with a different weight per group.

9. The data hashing method of claim 3, further comprising, before the changing of the component value of the Nth-order hash vector, performing a sampling based on the entire fingerprint value or a portion of the fingerprint value according to a predetermined rule, and

in the changing of the component value of the Nth-order hash vector, only the sampled fingerprint values can be used to change the component values of the Nth-order hash vector.

10. The data hashing method of claim 3, wherein the hash value comprises a first hash value and a second hash value, wherein

the first hash value is an interior angle θ

or cos θ

between the Nth-order hash vector and an Nth-order base vector, and

the second hash value is a distance D between an end point of the Nth-order hash vector and an end point of the Nth-order base vector or a scalar product between the Nth-order hash vector and the Nth-order base vector.

11. The data hashing method of claim 3, wherein the Nth-order hash vector is divided into m sub-hash vectors, and

the hash value comprises a first M hash value and a second M hash value, each having m components, wherein

the m components of the first M hash value are respectively interior angles θ

_i or cos θ

_ii=1˜

m between the m sub-hash vectors and m base sub-vectors, each having the same order as a corresponding sub-hash vector, and

the m components of the second M hash value are respectively distances D_i;

i=1˜

m between end points of the m sub-hash vectors and end points of the m base sub-vectors or scalar products between the m sub-hash vectors and the m base sub-vectors.

12. The data hashing method of claim 11, wherein the sum of the orders of the m sub-hash vectors is equal to or greater than N.

13. The data hashing method of claim 12, wherein each of the m sub-hash vectors is an Nth-order vector in which corresponding components of the Nth-order hash vector have the same components values of the Nth-order hash vector and the value of the other components is 0.

14. The data hashing method of claim 11, wherein multiple hash values, each having 2m components, are generated for multiple computerized data, and

the similarity between the multiple computerized data can be determined by respectively comparing 2m components of a reference hash value with the 2m components of each of multiple hash values, setting sub-weights inversely proportional to differences between the components, and summing all the sub-weights.

15. The data hashing method of claim 1, wherein the generating of the hash value of the computerized data using the SBH algorithm comprises:

calculating a plurality of fingerprint values from the content of the computerized data;

creating an Nth-order hash vector corresponding to the fingerprint values according to a predetermined rule; and

convertng the Nth-order hash vector into the hash value.

16. The data hashing method of claim 15, wherein the creating of the Nth-order hash vector comprises:

grouping the fingerprint values into N groups by applying the predetermined rule to the entire fingerprint values or a portion of the fingerprint values; and

creating the Nth-order hash vector by designating the number of fingerprint values included in each of the N groups or a value obtained by multiplying the number by a weight assigned to each of the N groups as a relevant component value of the Nth-order hash vector.

17. The data hashing method of claim 15, further comprising, before the creating of the Nth-order hash vector, performing a sampling based on the fingerprint values or on a portion of the fingerprint values according to a predetermine rule, and

in the creating of the Nth-order hash vector, only fingerprint values selected by the sampling can be used for the creation of the Nth-order hash vector.

18. A data processing method using the SBH algorithm of claim 1, the data processing method comprising:

making a hash value table for a plurality of computerized data using the SBH algorithm; and

processing the plurality of computerized data using the hash value table.

19. The data processing method of claim 18, wherein the plurality of computerized data is processed using at least one of comparison, search, classification, change, and similarity calculation of data, and

can be processed within a time complexity of O(1), which is a constant, or O(n), which is proportional to the number n of data, by using the magnitude of a difference between hash values included in the hash value table.

20. The data processing method of claim 19, wherein if the plurality of computerized data is processed in order to search for data that is the same as or similar to data to be searched for,

the processing of the plurality of computerized data comprises:

receiving the search data;

generating a hash value of the search data using the SBH algorithm; and

searching for the same or similar data by indexing the hash value in the hash value table.

21. The data processing method of claim 20, wherein the generating of the hash value of the computerized data or search data comprises:

calculating a plurality of fingerprint values from the content of the computerized data or search data;

creating an Nth-order hash vector corresponding to the fingerprint values according to a predetermined rule; and

converting the Nth-order hash vector into the hash value.

22. The data processing method of claim 21, wherein in the making of the hash value table, the hash values of the plurality of computerized data are generated, and

in the searching for the same or similar data, data the same as or similar to the search data is found within a predetermined hash value difference range defined by a user by comparing the hash value of the search data to hash values of the plurality of computerized data.

23. The data processing method of claim 18, wherein the plurality of computerized data are packets transmitted through a network, and

in the making of the hash value table, a hash value table for the packets is made, and

in the processing of the plurality of computerized data, a rapid increase of packets that are the same as or similar to a specific packet can be monitored or blocked.

24. A data processing system using a similarity-based hashing (SBH) algorithm, the data processing system comprising:

an inputting unit to which computerized data is input;

a hash value generator generating a hash value of the input computerized data using the SBH algorithm; and

a data processing unit processing the computerized data using hash values.

25. The data processing system of claim 24, wherein the SBH algorithm comprises:

calculating a plurality of fingerprint values from the content of the computerized data;

creating an Nth-order hash vector corresponding to the fingerprint values according to a predetermined rule; and

converting the Nth-order hash vector into the hash value.

26. The data processing system of claim 25, wherein the computerized data are packets transmitted through a network,

hash values corresponding to the packets are listed in a hash value table, and

the data processing unit monitors or blocks a rapid increase of packets that are the same as or similar to a specific packet by checking whether the number of specific hash values or hash values that have a difference compared to the specific hash value within a predetermined range is greater than a threshold number.

27. The data processing system of claim 25, wherein the data processing system is a system for monitoring or controlling an illegal distribution of a digitized original document protected by copyright.

28. The data processing system of claim 25, wherein the data processing system is a document management system executing at least one of comparison, search, tracking, and classification functions for a plurality of documents.

29. The data processing system of claim 28, wherein the document management system is a concurrent versions system (CVS) which a plurality of users can use simultaneously.

30. The data processing system of claim 28, wherein the data processing system further comprises a data comparison and search unit using a same data comparison algorithm, wherein

the data processing unit uses the SBH algorithm for a quick search for the same or similar data, and

the same data comparison algorithm is used for a detailed comparison of the found same or similar data.

31. The data processing system of claim 30, wherein the same data comparison algorithm is a Legacy Comparison (LEG-CMP) algorithm comprising one of a diff tool, a Longest Common Subsequence (LCSeq) algorithm, and a Longest Common Substring (LCStr) algorithm.