Associative database scanning and information retrieval

• US 7,953,743 B2
• Filed: 10/31/2007
• Issued: 05/31/2011
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• 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): Fleurantin; Jean B
• Application Number:
  US11/932,391
• Publication Number:
  US 20080109413A1
• Time in Patent Office: 1,308 Days
• Field of Search: 707600-831, 709/214, 711/103, 711/111, 711/112, 711/145
• US Class Current: 707/758
• 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 device for matching comprising:

a processor; and

an approximate matching unit in communication with the processor, wherein the approximate matching unit is configured under control of the processor to (1) store a data key, (2) receive streaming data from a storage medium, and (3) perform a matching operation by (i) processing the streaming data against the data key to generate a signal indicative of a similarity between the streaming data and the data key, and (ii) comparing the generated signal with an adjustable threshold value to thereby determine whether the streaming data is deemed a match to the data key; and

wherein the processor is configured to adjust the predetermined threshold value to control whether the 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 the approximate match operation.

2. The device of claim 1 wherein the matching operation comprises a pattern matching operation, and wherein the approximate matching unit is further configured to perform the pattern matching operation by continuously comparing a sliding window of the streaming data with the data key to generate the signal indicative of the similarity between the streaming data and the data key.

3. The device of claim 1 wherein the data key comprises an analog data key.

4. The device of claim 1 wherein the data key comprises a digital data key, and wherein the approximate matching unit is further configured to process portions of the streaming data against the data key on a frame-by-frame basis.

5. The device of claim 4 wherein the processor is further configured to send a query to the approximate matching unit, the query comprising a plurality of parameters for controlling the matching operation, at least one of the parameters comprising the data key.

6. The device of claim 5 wherein the query parameters further comprise a specification of the threshold value.

7. The device of claim 6 wherein the query parameters further comprise a starting location for the streaming data with respect to the matching operation and a final location for the streaming data with respect to the matching operation for terminating the matching operation if no match is found.

8. The device of claim 6 wherein the query parameters further comprise data representative of information to be returned by the approximate matching unit when a match is found.

9. The device of claim 8 further comprising a system bus and a cache memory, wherein the processor is in communication with the approximate matching unit over the system bus, and wherein the approximate matching unit is in communication with the cache memory, and wherein the query parameters further comprise data representative of whether the approximate matching unit is to return the information to the system bus or the cache memory.

10. The device of claim 4 wherein the approximate matching unit comprises programmable logic.

11. The device of claim 4 further comprising the storage medium.

12. The device of claim 11 wherein the storage medium comprises a disk storage.

13. The device of claim 11 wherein the approximate matching unit is directly coupled to the storage medium.

14. The device of claim 1 wherein the processor comprises a Central Processing Unit (CPU) configured to execute software to define the predetermined threshold value.

15. The device of claim 1 wherein the approximate matching unit is further configured to perform the processing operation by continuously processing the streaming data against the data key to generate the signal indicative of the similarity between the streaming data and the data key.

16. A computer comprising:

a processor,

a memory, and

an approximate matching unit configured to perform a matching operation between a data key representative of data sought to be retrieved from the memory with a data signal representative of a continuous stream of data read from the memory,

wherein the approximate matching unit is switchable between a plurality of different types of matching operations under control of the processor, wherein at least one of the matching operation types comprises an approximate matching operation, wherein the approximate matching unit is configured to perform the approximate matching operation by (i) processing the data stream against the data key to generate a signal indicative of a similarity between the data stream and the data key, and (ii) comparing the generated signal with an adjustable threshold value to thereby determine whether the streaming data is deemed an approximate match to the data key, and

wherein the processor is configured to adjust the predetermined threshold value to control a degree of approximate matches returned by the approximate match operation.

17. The computer of claim 16 wherein at least another of the matching operation types comprises an exact matching operation, wherein the processor is further configured to switch the approximate matching unit such that the approximate matching unit performs the exact matching operation by adjusting the threshold value to a value corresponding to an exact matching operation.

18. The computer of claim 17 wherein the approximate matching unit comprises programmable logic, and wherein the approximate matching unit is further configured to process portions of the data stream against the data key on a frame-by-frame basis.

19. The computer of claim 16 wherein the approximate matching unit comprises programmable logic, and wherein the approximate matching unit is further configured to process portions of the data stream against the data key on a frame-by-frame basis.

20. The computer of claim 16 wherein the memory comprises a mass storage medium.

21. The computer of claim 20 wherein the mass storage medium comprises disk storage.

22. The computer of claim 21 wherein the approximate matching unit is directly coupled to the disk storage.

23. The computer of claim 16 wherein the processor comprises a Central Processing Unit (CPU) configured to execute software to define the predetermined threshold value.

24. The computer of claim 16 wherein the approximate matching unit is further configured to perform the processing operation by continuously processing the data stream against the data key to generate the signal indicative of the similarity between the data stream and the data key.