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
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
13 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. - View Dependent Claims (3, 4)
-
-
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. - View Dependent Claims (7, 8)
-
- 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.
Specification