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

• US 7,617,231 B2
• Filed: 12/06/2006
• Issued: 11/10/2009
• Est. Priority Date: 12/07/2005
• Status: Expired due to Fees

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Yi, Sungwon, Oh, Jintae, Jang, Jong Soo, Kim, Changhoon, Moon, Hwa Shin
• Primary Examiner(s): Pardo; Thuy N
• Application Number:
  US11/634,731
• Publication Number:
  US 20070130188A1
• Time in Patent Office: 1,070 Days
• Field of Search: 707/3, 707/101, 707/200, 707/100, 717/116, 713/176, 713/181, 382/124
• 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

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, wherein a search, comparison, and classification of data may be quickly processed within a time complexity of O(1) or O(n) since the similarity/closeness of data content are quantified by component values for each of the respective corresponding generated 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,

wherein the hash value has at least two variable values that allows for a quick search of the computerized data for determining if the two data are similar, 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, and

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.

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 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.

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

5. The data hashing method of claim 1, 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.

6. The data hashing method of claim 5, 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.

7. The data hashing method of claim 1, 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.

8. The data hashing method of claim 1, 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.

9. The data hashing method of claim 1, 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 θ

_i i=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 them 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.

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

11. The data hashing method of claim 10, 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.

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

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

13. 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,

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.

14. The data processing method of claim 13, 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.

15. The data processing method of claim 14, 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.

16. The data processing method of claim 15, 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.

17. The data processing method of claim 13, 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.

18. A data processing system using a computer-readable medium in association with a computing device which includes a processor and a memory, the computer readable medium including computer instructions which are configured to cause the computing device to perform 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,

wherein the SBH algorithm further comprises;

calcuating 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, and

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.

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

20. The data processing system of claim 18, 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.

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

22. The data processing system of claim 20, 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.

23. The data processing system of claim 22, 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.