Similarity-based access control of data in a data processing system

DC CAFC

US 7,945,544 B2
Filed: 10/31/2007
Issued: 05/17/2011
Est. Priority Date: 04/11/1995
Status: Expired due to Fees

- Alert
- Pin

132

Associated Cases

108

Associated Defendants

First Claim

Patent Images

1. A computer-implemented method, the method comprising:

(A) for a first data item comprising a first plurality of parts,(a1) applying a first function to each part of said first plurality of parts to obtain a corresponding part value for each part of said first plurality of parts, wherein each part of said first plurality of parts comprises a corresponding sequence of bits, and wherein the part value for each particular part of said first plurality of parts is based, at least in part, on the corresponding bits in the particular part, and wherein two identical parts will have the same part value as determined using said first function, wherein said first function comprises a first hash function; and

(a2) obtaining a first value for the first data item, said first value obtained by applying a second function to the part values of said first plurality of parts of said first data item, said second function comprising a second hash function;

(B) for a second data item comprising a second plurality of parts,(b1) applying said first function to each part of said second plurality of parts to obtain a corresponding part value for each part of said second plurality of parts, wherein each part of said second plurality of parts consists of a corresponding sequence of bits, and wherein the part value for each particular part of said second plurality of parts is based, at least in part, on the corresponding bits in the particular part of the second plurality of parts; and

(b2) obtaining a second value for the second data item by applying said second function to the part values of said second plurality of parts of said second data item; and

(C) ascertaining whether or not said first data item corresponds to said second data item based, at least in part, on said first value and said second value.

View all claims

3 Assignments

Timeline View

Assignment View

Litigations

2 Petitions

Accused Products

Abstract

Similarity of data items is determined by analyzing corresponding segments of the data items. A function is applied to each segment of a data item and the output of that function is compared to the output of the same function applied to a corresponding segment of another data item. A function may be applied to the output of the functions. The functions may be hash or message digest functions.

209 Citations

56 Claims

1. A computer-implemented method, the method comprising:
- (A) for a first data item comprising a first plurality of parts,(a1) applying a first function to each part of said first plurality of parts to obtain a corresponding part value for each part of said first plurality of parts, wherein each part of said first plurality of parts comprises a corresponding sequence of bits, and wherein the part value for each particular part of said first plurality of parts is based, at least in part, on the corresponding bits in the particular part, and wherein two identical parts will have the same part value as determined using said first function, wherein said first function comprises a first hash function; and
  
  (a2) obtaining a first value for the first data item, said first value obtained by applying a second function to the part values of said first plurality of parts of said first data item, said second function comprising a second hash function;
  
  (B) for a second data item comprising a second plurality of parts,(b1) applying said first function to each part of said second plurality of parts to obtain a corresponding part value for each part of said second plurality of parts, wherein each part of said second plurality of parts consists of a corresponding sequence of bits, and wherein the part value for each particular part of said second plurality of parts is based, at least in part, on the corresponding bits in the particular part of the second plurality of parts; and
  
  (b2) obtaining a second value for the second data item by applying said second function to the part values of said second plurality of parts of said second data item; and
  
  (C) ascertaining whether or not said first data item corresponds to said second data item based, at least in part, on said first value and said second value.
- View Dependent Claims (2, 3, 4, 5, 6, 7)
- - 2. The method of claim 1 wherein said first data item corresponds to said second data item when said first value is identical to said second value.
  - 3. The method of claim 1 wherein said ascertaining in (C) is used to determine whether the first data item matches the second data item.
  - 4. The method of claim 1 wherein said ascertaining in (C) is used to determine whether the first data item is a copy of the second data item.
  - 5. The method of claim 1 wherein the first function is the same as the second function.
  - 6. The method of claim 1 wherein the first plurality of parts of the first data item are non-overlapping, and wherein the second plurality of parts of the second data item are non-overlapping.
  - 7. The method of claim 1 wherein each of the parts in the first plurality of parts and each of the parts in the second plurality of parts is the same size.

8. A computer-implemented method comprising:
- (A) maintaining a database of values, at least one value for each data item of a plurality of data items,wherein each data item of the plurality of data items comprises a corresponding one or more parts, andwherein each of the one or more parts of each data item comprises a corresponding sequence of bits, andwherein each of the one or more parts of each data item has a corresponding part value, the part value for each particular part being based on a first given function of the corresponding sequence bits for that particular part,wherein two identical parts will have the same part value as determined using the first given function, andthe value for each particular data item being based, at least in part, on a second given function of the part values of the one or more parts of that particular data item, andwherein the first given function comprises a first hash function, and the second given function comprises a second hash function;
  
  (B) obtaining a second value, the second value corresponding to a second data item, the second data item comprising a corresponding one or more parts,each of the one or more parts of the second data item comprising a corresponding sequence of bits,each of the one or more parts of the second data item having a corresponding part value,wherein the part value for each particular part of the second data item is based on the first given function of the corresponding sequence of bits in that particular part of the second data item; and
  
  wherein the second value is based on the second function of the one or more part values of the second data item; and
  
  (C) ascertaining whether or not the second data item corresponds to any of the plurality of data items, based, at least in part, on whether or not the second value corresponds to any value in the database of values.
- View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
- - 9. The method of claim 8 wherein the second value corresponds to a particular value in the database of values when the second value is equal to the particular value in the database of values.
  - 10. The method of claim 8 wherein the first hash function is selected from the functions MD5 and SHA.
  - 11. The method of claim 10 wherein the second hash function is selected from the functions MD5 and SHA.
  - 12. The method of claim 8 wherein the first given function is the same as the second given function.
  - 13. The method of claim 8 wherein the database comprises a mapping from data item values to corresponding data items.
  - 14. The method of claim 8 wherein the second value is obtained as part of a search for the second data item.
  - 15. The method of claim 8 wherein the second value is obtained as part of a search for data items matching the second data item.
  - 16. The method of claim 8 further comprising:
    - (D) when the second value corresponds to a particular value in the database, providing information about a particular data item corresponding to the particular entry.
  - 17. The method of claim 8 wherein the step (B) of obtaining the second value comprises calculating the second value.
  - 18. The method of claim 8 wherein at least some of the data items are files.
  - 19. The method of claim 8 wherein the database comprises a mapping from values to corresponding data items, and wherein, when the second value corresponds to the first value, information about the corresponding data item is provided.
  - 20. The method of claim 8 wherein the parts are segments.
  - 21. The method of claim 8 further comprising:
    - (D) adding a new value to the database, wherein the new value corresponds to a new data item distinct from the plurality of data items.

22. A computer-implemented method comprising:
- (A) obtaining a particular data item value corresponding to a particular data item, the particular data item comprising a corresponding one or more parts,each of the one or more parts of the particular data item comprising a corresponding sequence of bits,each of the one or more parts of the particular data item having a corresponding part value,wherein the part value for each specific part of the one or more parts of the particular data item is based, at least in part, on a first given function of the corresponding sequence of bits in that specific part of the particular data item;
  
  wherein two identical parts will have the same part value as determined using the first given function, andwherein the particular data item value is based, at least in part, on a second given function of the one or more part values of the particular data item,wherein the first given function comprises a first hash function, and the second given function comprises a second hash function; and
  
  (B) ascertaining whether or not the particular data item corresponds to any of a plurality of data items, based, at least in part, on whether or not the particular data item value corresponds to any value in a database of data item values,wherein the database of data item values comprises at least one data item value for each data item of the plurality of data items,wherein each data item of the plurality of data items comprises a corresponding one or more parts, andwherein each of the one or more parts of each data item of the plurality of data items comprises a corresponding sequence of bits, andwherein each of the one or more parts of each data item of the plurality of data items has a corresponding part value, the part value for each particular part of the one or more parts of each data item being based on the first given function of the corresponding sequence bits for that particular part,the data item value for each particular data item being based, at least in part, on the second given function of the part values of the one or more parts of that particular data item.
- View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31)
- - 23. The method of claim 22 wherein step (D) of adding is a background process.
  - 24. The method of claim 22 wherein the first given function is selected from the functions MD5 and SHA.
  - 25. The method of claim 22 wherein the second given function is selected from the functions MD5 and SHA.
  - 26. The method of claim 22 wherein the database comprises a mapping from data item values to corresponding data items.
  - 27. The method of claim 22 wherein the particular data item value is obtained as part of a search for the particular data item.
  - 28. The method of claim 22 wherein the particular data item value is obtained as part of a search for data items matching the particular data item.
  - 29. The method of claim 22 wherein the particular data item value corresponds to a value in the database when the particular data item value is equal to the value in the database.
  - 30. The method of claim 22 wherein the data items are files.
  - 31. The method of claim 22 wherein the first given function is the same as the second given function.

32. A computer-implemented method comprising:
- (A) maintaining a database comprising a mapping of data item keys to corresponding data item information for each of a plurality of data items, wherein each data item of the plurality of data items has at least one data item key,wherein each data item of the plurality of data items comprises a corresponding one or more portions, andwherein each of the one or more portions of each data item comprises a corresponding sequence of bits, andwherein each of the one or more portions of each data item has a corresponding portion value, the portion value for each particular portion being based on a first given function of the corresponding sequence bits for that particular portion, wherein the first given function comprises a first hash function, and wherein two identical portions will have the same portion value as determined using the first given function,the particular data item key for each particular data item being based on a second given function of the portion values of the one or more portions of that particular data item, wherein the second given function comprises a second hash function;
  
  (B) obtaining a particular value, the particular value having been determined from a corresponding one or more particular portions,each of the one or more particular portions comprising a corresponding sequence of bits,each of the one or more particular portions having a corresponding portion value, wherein the portion value for each specific portion of the one or more particular portions is based on the first given function of the corresponding bits in that specific portion; and
  
  wherein the particular value is based on the second function of the portion values of the one or more particular portions; and
  
  (C) using the particular value and the database to ascertain whether or not the one or more particular portions correspond to any of the plurality of data items.
- View Dependent Claims (33, 34, 35)
- - 33. The method of claim 32 wherein the one or more particular portions are obtained as part of a search.
  - 34. The method of claim 32 further comprising:
    - (D) when the one or more particular portions correspond to a specific data item, providing information about that specific data item.
  - 35. The method of claim 34 wherein the information provided in (D) includes information about a location of a copy of the specific data item.

36. A computer-implemented method comprising:
- (A) for each particular data item of a plurality of data items;
  
  (a1) determining a corresponding particular data item key; and
  
  (a2) adding an entry to a database to map said particular data item key to information about the particular data item,wherein each data item of the plurality of data items comprises a corresponding one or more parts, andwherein each of the one or more parts of each data item comprises a corresponding sequence of bits, andwherein each of the one or more parts of each data item has a corresponding part value, the part value for each particular part being based on a first given function of the corresponding sequence bits for that particular part, wherein the first given function comprises a first hash function, wherein two identical parts will have the same part value as determined using the first given function,the data item key for each particular data item being based on a second given function of the part values of the one or more parts of that data item, wherein the second given function comprises a second hash function;
  
  (B) determining a second key value, the second key value being based on one or more particular parts,each of the one or more particular parts comprising a corresponding sequence of bits,each of the one or more particular parts having a corresponding part value, wherein the part value for each specific part of the one or more particular parts is based on the first given function of the corresponding bits in that specific part; and
  
  wherein the second key value is based on the second function of the part values of the one or more particular parts; and
  
  (C) using the second key value and the database to ascertain whether or not the one or more particular parts correspond to any of the plurality of data items.
- View Dependent Claims (37, 38, 39, 40, 41, 42, 43, 44, 45)
- - 37. The method of claim 36 wherein the one or more particular parts are obtained as part of a search.
  - 38. The method of claim 36 wherein the one or more particular parts are obtained as part of a search for data items comprising the one or more particular parts.
  - 39. The method of claim 36 wherein the one or more particular parts correspond to a specific data item of the plurality of data items when the second key value is equal to a data item key of the specific data item.
  - 40. The method of claim 36 wherein the parts are segments.
  - 41. The method of claim 36 wherein the step (C) of using comprises:
    - looking up the second key value in the database.
  - 42. The method of claim 36 wherein step (A) is a background process.
  - 43. The method of claim 36 wherein the information about a particular data item in the database includes location information about the particular data item.
  - 44. The method of claim 43 wherein the location information includes a list of one or more locations of the particular data item.
  - 45. The method of claim 36 wherein the information about a particular data item in the database includes a copy of the data item.

46. A computer-implemented method comprising:
- (A) for each particular file of a plurality of files;
  
  (a2) determining a particular digital key for the particular file, wherein the particular file comprises a first one or more parts,each part of said first one or more parts having a corresponding part value,the part value of each specific part of said first one or more parts being based on a first function of the contents of the specific part,wherein two identical parts will have the same part value as determined by the first function, andwherein the particular digital key for the particular file is determined using a second function of the one or more of part values of said first one or more parts; and
  
  (a2) adding the particular digital key of the particular file to a database, the database including a mapping from digital keys of files to information about the corresponding files;
  
  (B) determining a search key based on search criteria,wherein the search criteria comprise a second one or more parts, each of said second one or more parts of said search criteria having a corresponding part value, the part value of each specific part of said second one or more parts being based on the first function of the contents of the specific part, and wherein the search key is determined using the second function of the one or more of part values of said second one or more parts;
  
  (C) attempting to match the search key with a digital key in the database; and
  
  (D) if the search key matches a particular digital key in the database, providing information about the file corresponding to the particular digital key.
- View Dependent Claims (47, 48, 49, 50, 51)
- - 47. The method of claim 46 wherein step (A) is a background process.
  - 48. The method of claim 46 wherein the plurality of files are files located in a network of computers.
  - 49. The method of claim 46 wherein the information provided in (D) includes location information about the file corresponding to the particular digital key.
  - 50. The method of claim 49 wherein the location information includes a list of one or more locations of the file corresponding to the particular digital key.
  - 51. The method of claim 46 wherein the information provided in (D) includes a copy of the file corresponding to the particular digital key.

52. A computer-implemented method comprising:
- (A) for each particular file of a plurality of files;
  
  (a1) determining a corresponding particular file key; and
  
  (a2) adding an entry to a database to map said particular file key to information about the particular file, the information about the particular file including one or more locations of the particular file,wherein each file of the plurality of files comprises a corresponding one or more parts, andwherein each of the one or more parts of each file has a corresponding part value, the part value for each particular part being based on a first hash function of that particular part, wherein two identical parts will have the same part value as determined using the first hash function,the file key for each particular file being based on a second hash function of the part values of the one or more parts of that file;
  
  (B) determining a second key value, the second key value being based on one or more particular parts,each of the one or more particular parts having a corresponding part value, wherein the part value for each specific part of the one or more particular parts is based on the first hash function of that specific part; and
  
  wherein the second key value is based on the second hash function of the part values of the one or more particular parts; and
  
  (C) comparing the second key value to key values in the database to ascertain whether or not the one or more particular parts correspond to any of the plurality of files.
- View Dependent Claims (53, 54, 55, 56)
- - 53. The method of claim 52 wherein step (A) is a background process.
  - 54. The method of claim 52 wherein the information about a particular file in the database includes a copy of the file.
  - 55. The method of claim 52 further comprising:
    - (D) when the second key value corresponds to a certain key value in the database, providing information from the database corresponding to the certain key value.
  - 56. The method of claim 55 wherein the certain key value was determined from a certain file, and wherein the information provided in (D) includes one or more locations of the certain file.

Specification

Resources

Litigation Campaign Assessment

Litigation Data

Current Assignee
PersonalWeb Technologies, L.L.C.
Original Assignee
Kinetech, Inc. (Brilliant Digital Entertainment Incorporated), Level 3 Communications LLC (Lumen Technologies, Inc.)
Inventors
Lachman, Ronald D., Farber, David A.
Primary Examiner(s)
Pham; Khanh B

Application Number

US11/980,688
Publication Number

US 20080065635A1
Time in Patent Office

1,294 Days
Field of Search

707/609, 707821-828, 707697-698
US Class Current

707/698
CPC Class Codes

G06F 16/13   File access structures, e.g...

G06F 16/164   File meta data generation

G06F 16/174   Redundancy elimination perf...

Y10S 707/914   Video

Y10S 707/915   Image

Y10S 707/916   Audio

Y10S 707/922   Communications

Y10S 707/959   Network

Y10S 707/961   Associative

Y10S 707/966   Distributed

Y10S 707/99931   Database or file accessing

Y10S 707/99932   Access augmentation or opti...

Y10S 707/99933   Query processing, i.e. sear...

Y10S 707/99942   Manipulating data structure...

Similarity-based access control of data in a data processing system

First Claim

3 Assignments

Litigations

2 Petitions

Accused Products

Abstract

209 Citations

56 Claims

Specification

Use Cases

Quick Links

Others

Similarity-based access control of data in a data processing system

First Claim

3 Assignments

Subscription Required

Subscription Required

Litigations

2 Petitions

Subscription Required

Accused Products

Subscription Required

Abstract

209 Citations

56 Claims

Specification

Subscription Required

Use Cases

Quick Links

Others