Associative Database Scanning and Information Retrieval

• US 20070118500A1
• Filed: 01/08/2007
• Published: 05/24/2007
• Est. Priority Date: 04/07/2000
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Cytron, Ron, Indeck, Ronald, Franklin, Mark
• Granted Patent: US 7,552,107 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24557 Efficient disk access during query execution
• CPC Class Codes: G06F 16/40 of multimedia data, e.g. slideshows comprising image and additional audio data retrieval of still image data G06F16/50; retrieval of audio data G06F16/60; retrieval of video data G06F16/70
• CPC Class Codes: G06F 16/433 using audio data
• CPC Class Codes: G06F 16/434 using image data, e.g. images, photos, pictures taken by a user
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G06F 16/90344 by using string matching techniques
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A method and device are disclosed for an associative and approximate, analog or digital scanning of databases that allows for the asynchronous accessing of data from a mass storage medium. The invention includes providing dedicated analog and digital circuitry and decision logic at the mass storage medium level for determining a key identifying the data of interest, continuously comparing the key to a signal generated from a reading of the data from the mass storage medium with an approximate or exact matching circuit to determine a pattern match, determining a correlation value between the key and the data as it is read in a continuous fashion, and determining a match based upon a preselected threshold value for the correlation value. The pattern matching technique eliminates any need to compare data based on its intrinsic structure or value, and instead is based on an analog or digital pattern. The key and data may be either analog or digital. This device and method may be provided as part of a stand-alone computer system, embodied in a network attached storage device, or can otherwise be provided as part of a computer LAN or WAN.

Claims

1. A data processing system comprising:

a mass storage medium in which data is stored; and

an approximate matching unit in communication with the mass storage medium, wherein the approximate matching unit is configured to (1) receive a continuous stream of data from the mass storage, and (2) process the data stream to determine whether an approximate match exists via a comparison between the key and the data stream, wherein the approximate matching unit is further configured to perform the comparison by calculating a correlation coefficient that is indicative of a degree of correlation between the key and the data stream, and wherein the approximate matching unit is further configured to determine that an approximate match exists if the correlation coefficient has a value larger than or at least equal to a predetermined threshold value.

2. The system of claim 1 wherein the key comprises a digital key, wherein the data stream comprises a digital data stream, and wherein the approximate matching unit comprises a programmable logic device that is configured to perform the comparison.

3. The system of claim 2 wherein said predetermined threshold value is user-specified.

4. The system of claim 2 wherein said predetermined threshold value is adjustable to control whether said approximate matching unit performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by said approximate match operation.

5. The system of claim 2 further comprising a network and a central processing unit (CPU), wherein the CPU is located across the network from the mass storage medium and the approximate matching unit, wherein the CPU is configured to communicate a search query to the approximate matching unit over the network, and wherein the approximate matching unit is configured to perform the comparison in response to the search query.

6. The system of claim 5 wherein the mass storage medium comprises a bank of hard disk drives.

7. The system of claim 6 wherein the bank of hard disk drives comprises a Redundant Array of Independent Disks (RAID).

8. The system of claim 6 wherein the bank of hard disk drives comprises a disk farm.

9. The system of claim 5 wherein the approximate matching unit is directly coupled to said mass storage medium.

10. The system of claim 5 wherein a plurality of CPUs are in communication with the approximate matching unit over the network, each CPU being configured to communicate a search query to the approximate matching unit for processing thereby.

11. The system of claim 10 wherein each CPU comprises a part of a standalone computer system that is in communication with the network.

12. The system of claim 11 further comprising a plurality of the approximate matching units, wherein each standalone computer further comprises a data storage device and one of the approximate matching units connected thereto, and wherein each data storage device has an assigned network address for access by any of the other CPUs connected to the network through the approximate matching unit connected thereto.

13. The system of claim 5 further comprising a data processing unit in communication with the approximate matching unit, said data processing unit being configured to translate the search query to a format readable by the approximate matching unit for carrying out the comparison.

14. The system of claim 13 wherein said data processing unit comprises a programmable logic device.

15. The system of claim 5 wherein said search query comprises a plurality of parameters corresponding to a starting location for scanning the mass storage medium as part of the comparison, an ending location for scanning the mass storage medium as part of the comparison, the key to be used in the comparison, and what data should be returned upon a finding of a hit as a result of the comparison.

16. The system of claim 15 wherein said search query further comprises a parameter corresponding to a value for said predetermined threshold that controls whether said approximate matching unit performs an approximate match operation or an exact match operation, and further controls, for an approximate match operation, a degree of approximate matches returned by said approximate match operation.

17. A device for processing data from a mass storage medium to identify data of interest therein, said device comprising:

an approximate matching unit that is configured to perform a comparison between a data signal representative of a continuous stream of data read from a mass storage medium and a determined key representative of the data of interest, and

wherein said approximate matching unit is further configured to perform said comparison by computing a correlation coefficient between said data key and said data signal, and

wherein said approximate matching unit is further configured to compare said computed correlation coefficient with a predetermined threshold value to thereby determine whether an approximate match exists between said data key and said data signal.

18. The device of claim 17 wherein said predetermined threshold value is adjustable to control whether said approximate matching unit performs an approximate match operation or an exact match operation, and further to control, for an approximate match operation, a degree of approximate matches returned by said approximate match operation.

19. The device of claim 18 wherein said approximate matching unit comprises a programmable logic device that is configured to perform said comparison.

20. The device of claim 19 wherein said approximate matching unit is directly coupled to said mass storage medium and interfaces said mass storage medium with a processor desiring said data of interest for processing thereof.

21. The device of claim 17 wherein said approximate matching unit comprises a programmable logic device that is configured to perform said comparison, wherein said data key is a digital data key and wherein said data signal is a digital data signal.

22. The device of claim 21 wherein said approximate matching unit is directly coupled to said mass storage medium and interfaces said mass storage medium with a processor desiring said data of interest for processing thereof.

23. The device of claim 21 further comprising a data processing unit in communication with the approximate matching unit, said data processing unit being configured to translate a search query received from a remote processor to a format readable by the approximate matching unit for carrying out the comparison, and wherein the approximate matching unit is further configured to perform said comparison in response to said translated search query.

24. The device of claim 23 wherein said data processing unit comprises a programmable logic device.

25. The device of claim 23 wherein the data processing unit is further configured to receive the search query from the remote processor via a computer network connection to the remote processor.

26. The device of claim 23 wherein said search query comprises a plurality of parameters corresponding to a starting location for scanning the mass storage medium as part of the comparison, an ending location for scanning the mass storage medium as part of the comparison, the key to be used in the comparison, and what data should be returned upon a finding of a hit as a result of the comparison.

27. The device of claim 26 wherein said search query further comprises a parameter corresponding to a value for said predetermined threshold that controls whether said approximate matching unit performs an approximate match operation or an exact match operation, and further controls, for an approximate match operation, a degree of approximate matches returned by said approximate match operation.

28. The device of claim 17 wherein the approximate matching unit is further configured to framelessly perform said comparison.

29. A method for processing data, said method comprising:

receiving a search command from a processor for searching data stored in a mass storage medium to determine whether any data of interest is located therein,

determining a key from the search command, wherein the key is representative of the data of interest,

making a comparison between said key and a data signal representative of a continuous stream of data read from said mass storage medium,

determining, in response to said comparison, which data within said data signal matches said key; and

wherein said comparison making step comprises computing a correlation coefficient between said key and said data signal, and wherein said match determining step comprises comparing said computed correlation coefficient with a predetermined threshold value to thereby determine whether a match exists between said data key and said data signal.

30. The method of claim 29 further comprising adjusting said predetermined threshold value to control whether said match determining step corresponds to an exact match operation or an approximate match operation.

31. The method of claim 29 further comprising reading data from said mass storage medium as a continuous analog data stream and sampling said continuous analog data stream to thereby generate said data signal.

32. The method of claim 31 wherein said key determining step comprises sampling an analog key that is representative of the data desired to be retrieved from said mass storage medium to thereby generate said key that is used in said comparison making step.

33. The method of claim 29 wherein said comparison making step further comprises performing said comparison making step with a programmable logic device.

34. The method of claim 33 wherein said search command receiving step comprises receiving said search command from a remote processor over a network interface.

35. The method of claim 34 further comprising receiving a plurality of search commands from a plurality of remote processors over a network interface.

36. The method of claim 34 further comprising translating the search command to a format for the comparison making step, the translating step comprising processing the search command to determine a starting location in the mass storage medium for reading data therefrom for use in the comparison making step, an ending location in the mass storage medium for reading data therefrom for use in the comparison making step, the key for use in the comparison making step, and what data should be returned upon a finding of a hit as a result of the in comparison making step.

37. The method of claim 36 further comprising performing the translating step with a programmable logic device.