Associative database scanning and information retrieval

• US 7,181,437 B2
• Filed: 11/24/2003
• Issued: 02/20/2007
• Est. Priority Date: 04/07/2000
• Status: Expired due to Term

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Franklin, Mark Allen, Indeck, Ronald S., Cytron, Ron Kaplan
• Primary Examiner(s): Alam; Shahid
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US10/722,691
• Publication Number:
  US 20040111392A1
• Time in Patent Office: 1,184 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 711/103, 711111-112, 711/1, 711/145, 711/172, 709/214
• 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 retrieval system comprising:

a mass storage medium in which data is stored;

a retrieval device in communication with the mass storage medium, wherein the retrieval device is configured to (1) receive a continuous stream of data from the mass storage medium, and (2) continuously process the data stream to determine whether an approximate match exists therein with respect to a key that is representative of data sought to be retrieved,

wherein the retrieval device is further configured to process the data stream to determine whether an approximate match exists via a pattern comparison between the key and the data stream,

wherein the key is an analog key and wherein the data stream is an analog data stream,

wherein the retrieval device is further configured to perform the pattern comparison by calculating a correlation coefficient that is indicative of a degree of correlation between the key and the data stream, and

wherein the retrieval device 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 threshold value is user-specified.

3. A data retrieval system comprising:

a mass storage medium in which data is stored; and

a retrieval device in communication with the mass storage medium, wherein the retrieval device 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 pattern comparison between the key and the data stream, wherein the retrieval device is further configured to perform the pattern comparison by calculating a correlation coefficient that is indicative of a degree of correlation between the key and the data stream, and wherein the retrieval device 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.

4. The system of claim 3 wherein the threshold value is user-specified.

5. The system of claim 3 wherein the key is an analog key and wherein the data stream is an analog data stream.

6. The system of claim 3 wherein the key is a digital key and wherein the data stream is a digital data stream.

7. A retrieval device for retrieving data from a mass storage medium, said retrieval device comprising an approximate matching unit that is configured to framelessly perform a pattern comparison between a determined key representative of the data sought to be retrieved and a data signal representative of a continuous stream of data read from said mass storage medium, wherein said approximate matching unit is further configured to perform said pattern 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.

8. The retrieval device of claims 7 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.

9. The retrieval device of claim 7 wherein said approximate matching unit comprises digital logic that is configured to framelessly perform said pattern comparison, wherein said data key is a digital data key and wherein said data signal is a digital data signal.

10. The retrieval device of claim 9 further comprising an approximate matching and pre-fetch processor, said approximate matching and pre-fetch processor comprising said approximate matching unit, wherein said approximate matching and pre-fetch processor is configured to generate said digital data signal by sampling a continuous stream of analog data read from said mass storage medium at a high rate.

11. The retrieval device of claim 10 wherein said approximate matching and pre-fetch processor is configured to generate said digital data key by sampling an analog key at a high rate.

12. The retrieval device of claim 10 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 control, for an approximate match operation, a degree of approximate matches returned by said approximate match operation.

13. The retrieval device of claim 10 wherein said approximate matching unit is implemented on a programmable logic device.

14. The retrieval device of claim 10 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.

15. The retrieval device of claim 9 further comprising a data path extending from said mass storage medium to a system bus, said data path comprising a digital decoder and said approximate matching unit, said digital decoder having an input and an output, said input being configured to receive a continuous stream of analog data that corresponds to data read from said mass storage medium, said output being in communication with said approximate matching unit.

16. The retrieval device of claim 15 further comprising a plurality of said paths connected in parallel between said mass storage medium and said system bus.

17. The retrieval device of claim 9 further comprising a data path extending from said mass storage medium to a system bus, said data path comprising a digital decoder, error correction circuitry, and said approximate matching unit, said digital decoder having an input and an output, said error correction circuitry having an input and an output, said digital decoder input being configured to receive a continuous stream of analog data that corresponds to data read from said mass storage medium, said digital decoder output being in communication with said error correction circuitry input, said error correction circuit output being in communication with said approximate matching unit.

18. The retrieval device of claim 17 further comprising a plurality of said paths connected in parallel between said mass storage medium and said system bus.

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

20. The retrieval device of claim 9 wherein said approximate matching unit is implemented on a programmable logic device.

21. The retrieval device of claim 7 wherein said approximate matching unit comprises analog circuitry that is configured to framelessly perform said pattern comparison, wherein said data key is an analog data key and wherein said data signal is an analog data signal.

22. The retrieval device of claim 21 further comprising an approximate matching and pre-fetch processor, said approximate matching and pre-fetch processor comprising said approximate matching unit, wherein said approximate matching and pre-fetch processor is configured to generate said analog data key from a digital data key.

23. The retrieval device of claim 21 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.

24. The retrieval 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 retrieved data for processing thereof.

25. The retrieval device of claim 7 wherein said approximate matching unit is implemented on a programmable logic device.

26. The retrieval device of claim 7 wherein said approximate matching unit is directly coupled to said mass storage medium and interfaces said mass storage medium with a processor desiring said retrieved data for processing thereof.

27. A method for retrieving data from a mass storage medium, said method comprising the steps of:

receiving a search command from a processor for said mass storage medium,

determining a key representative of the data desired to be retrieved from said mass storage medium,

making a pattern comparison between said key and a data signal representative of a continuous stream of data read from said mass storage medium, said determined key being an analog key or a digital representation of an analog key, said data signal being an analog data signal or a digital representation of an analog data signal, wherein said data signal is said analog data signal if said key is said analog key, and wherein said data signal is said digital representation of said analog signal if said key is said digital representation of said analog key,

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

wherein said pattern 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.

28. The method of claim 27 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.

29. The method of claim 27 wherein said key comprises said analog key and wherein said data signal comprises said analog data signal, and wherein said pattern comparison making step further comprises performing said pattern comparison making step with analog circuitry.

30. The method of claim 29 wherein the key determining step comprises generating said analog key from a digital key that is representative of the data desired to be retrieved from said mass storage medium.

31. The method of claim 27 further comprising reading data from said mass storage medium as a continuous analog data stream and sampling said continuous analog data stream at a high rate to thereby generate said digital representation of said analog data signal, and 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 at a high rate to thereby generate said digital representation of said analog key, and wherein said pattern comparison making step further comprises performing said pattern comparison making step with digital logic.

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