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 8,131,697 B2
• Filed: 10/31/2007
• Issued: 03/06/2012
• Est. Priority Date: 04/07/2000
• Status: Expired due to Term

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Indeck, Ronald S., Cytron, Ron Kaplan, Franklin, Mark Allen
• Primary Examiner(s): Fleurantin, Jean B
• Application Number:
  US11/932,596
• Publication Number:
  US 20080126320A1
• Time in Patent Office: 1,588 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 709/214, 709/217, 709/219, 711/1, 711/103, 711/111, 711/112, 711/145, 711/172
• US Class Current: 707/705
• 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 method for interfacing a mass storage medium with a computing system, the method comprising:

receiving data from the computing system, wherein the received data comprises a search command;

processing the received data using a programmable logic device, the processing comprising determining a key from the search command;

writing the determined key onto the mass storage medium;

reading the written key from the mass storage medium, wherein the read key comprises an analog read signal for the key;

reading a stream of data from the mass storage medium, wherein the read data stream comprises an analog read signal for the data stream; 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, 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 by 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.

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

receiving data from the computing system, wherein the received data comprises a search command;

processing the received data using a programmable logic device, the processing comprising determining a key from the search command;

writing the determined key onto the mass storage medium;

reading the written key from 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, 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, and 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.

3. The method of claim 2 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.

4. The method of claim 2 further comprising:

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

5. An apparatus for interfacing a mass storage medium with a computing system, the apparatus 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, the received data comprising a search command;

wherein the at least one programmable logic device is configured to determine a key from the received search command;

wherein the approximate matching and pre-fetch processor is further configured to write the determined key onto the mass storage medium;

wherein the approximate matching and pre-fetch processor is further configured to read the written key from 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;

wherein the approximate matching and pre-fetch processor is further configured to sample the analog read signal for the key at a high rate, and sample the analog read signal for the stream of data at a high rate;

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 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 by performing the comparison between the key and the stream of data on the samples resulting from the sampling operations to thereby identify whether any approximate matches exist between the read key and the stream of data.

6. An apparatus for interfacing a mass storage medium with a computing system, the apparatus 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, the received data comprising a search command;

wherein the at least one programmable logic device is configured to determine a key from the received search command;

wherein the approximate matching and pre-fetch processor is further configured to write the determined key onto the mass storage medium;

wherein the approximate matching and pre-fetch processor is further configured to read the written key from 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 compare the read key with a sliding window of the stream of data read from the mass storage medium to thereby identify whether any approximate matches exist between the read key and the stream of data; and

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.

7. The apparatus of claim 6 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.

8. The apparatus of claim 6 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.

9. A programmable logic device for communication with a mass storage medium, said device being configured to process data passing to or from said mass storage medium in response to a plurality of data processing requests, 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, wherein at least one of the data processing requests comprises a data key, a search query and a threshold value, the data key being representative of data of interest, wherein the device is configured to (1) store the data key and the threshold value, (2) receive streaming data from the mass storage medium, the streaming data comprising a plurality of data frames, and (3) perform the approximate matching operation by (i) processing the streaming data against the data key on a frame-by-frame basis to generate a signal indicative of a similarity between frames of the streaming data and the data key, and (ii) comparing the generated signal with the threshold value to thereby determine whether the streaming data is deemed an approximate match to the data key, wherein the threshold value is adjustable to control a degree of approximate matches returned by the approximate match operation.

10. The device of claim 9 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 the data processing requests to the device.

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

12. The device of claim 11 wherein the computer network is the Internet.

13. The device of claim 9 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 the data processing requests to the device.