Method and Apparatus for Approximate Matching Where Programmable Logic Is Used to Process Data Being Written to a Mass Storage Medium and Process Data Being Read from a Mass Storage Medium

• US 20080126320A1
• Filed: 10/31/2007
• Published: 05/29/2008
• Est. Priority Date: 04/07/2000
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Franklin, Mark Allen, Indeck, Ronald S., Cytron, Ron Kaplan
• Granted Patent: US 8,131,697 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• 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-37. -37. (canceled)

38. A method for interfacing a mass storage medium with a computing system, the method comprising:

receiving data from the computing system;

processing the received data using a programmable logic device;

writing the processed received data onto the mass storage medium;

reading a stream of data from the mass storage medium; and

manipulating the stream of data read from the mass storage medium using the programmable logic device, wherein the step of manipulating the stream of data comprises performing an approximate match operation on the stream of data.

39. The method of claim 38 wherein the received data comprises a search command, wherein the step of processing the received data comprises determining a key from the search command, and wherein the writing step comprises writing the determined key onto the mass storage medium.

40. The method of claim 39 further comprising reading the written key from the mass storage medium, and wherein the approximate match operation performing step comprises comparing the read key with a sliding window of the data stream to thereby identify whether an approximate match exists between the read key and the data stream.

41. The method of claim 40 wherein the read key comprises an analog read signal for the key, wherein the read data stream comprises an analog read signal for the data stream, and wherein the comparing step comprises performing the comparison between the read key and the analog read signal.

42. The method of claim 41 wherein the approximate match operation performing step further comprises sampling the analog read signal for the key at a high rate, sampling the analog read signal for the data stream at a high rate, and performing the comparison between the key and the data stream on the samples resulting from the sampling steps.

43. The method of claim 40 wherein the comparing step further comprises:

continuously computing a correlation coefficient between the read key and the sliding window of the data stream using the programmable logic; and

judging the computed correlation coefficients against a threshold value to thereby identify whether an approximate match exists between the key and the data stream.

44. The method of claim 43 further comprising:

adjusting the threshold value to control a degree of approximate matches which is identified as a result of the comparing step.

45. An apparatus for interfacing a mass storage medium with a computing system, the method comprising:

an approximate matching and pre-fetch processor that interfaces the computing system with the mass storage medium, the approximate matching and pre-fetch processor comprising at least one programmable logic device;

wherein the approximate matching and pre-fetch processor is configured to receive data from the computing system;

wherein the at least one programmable logic device is configured to process the received data;

wherein the approximate matching and pre-fetch processor is further configured to write the processed received data onto the mass storage medium;

wherein the approximate matching and pre-fetch processor is configured to read a stream of data from the mass storage medium; and

wherein the at least one programmable logic device is further configured to manipulate the stream of data read from the mass storage medium, wherein the manipulation of the stream of data comprises an approximate match operation that is performed on the stream of data.

46. The apparatus of claim 45 wherein the approximate matching and pre-fetch processor is further configured to receive a search command from the computing system, wherein the at least one programmable logic device is further configured to determine a key from the search command, and wherein the approximate matching and pre-fetch processor is further configured to write the determined key onto the mass storage medium.

47. The apparatus of claim 46 wherein the approximate matching and pre-fetch processor is further configured to read the written key from the mass storage medium, and wherein the at least one programmable logic device is further configured to compare the read key with a sliding window of the stream of data to thereby identify whether any approximate matches exist between the read key and the stream of data.

48. The apparatus of claim 47 wherein the at least one programmable logic device is further configured to perform the comparison between the read key and the stream of data at a level corresponding to an analog read signal from the mass storage medium for the key and an analog read signal from the mass storage medium for the stream of data.

49. The apparatus of claim 48 wherein the approximate matching and pre-fetch processor is further configured to sample the analog read signal for the key at a high rate, sample the analog read signal for the stream of data at a high rate, and perform the comparison between the key and the stream of data on the samples resulting from the sampling operations.

50. The apparatus of claim 47 wherein the at least one programmable logic device is further configured to:

continuously compute a correlation coefficient between the read key and the sliding window of the stream of data; and

judge the computed correlation coefficients against a threshold value to thereby identify whether any approximate matches exist between the key and the stream of data.

51. The apparatus of claim 50 wherein the approximate matching and pre-fetch processor is further configured to adjust the threshold value to control a degree of approximate matches which are identified as a result of the comparing step.

52. A programmable logic device in communication with a mass storage medium, said device being configured to process data passing to or from said mass storage medium, and wherein said device is further configured to process data passing from said mass storage in a continuous data stream via an approximate matching operation.

53. The device of claim 52 wherein the device interfaces the mass storage medium with a system bus, and wherein a computer system is configured to access the system bus to communicate data processing requests to the device.

54. The device of claim 52 wherein the device is in communication with the mass storage medium over a computer network.

55. The device of claim 54 wherein the computer network is the Internet.

56. The device of claim 52 wherein the device interfaces the mass storage medium with a system bus, wherein a computer system is configured to access the system bus over a computer network to communicate data processing requests to the device.