Associative database scanning and information retrieval using FPGA devices

• US 7,139,743 B2
• Filed: 05/21/2002
• Issued: 11/21/2006
• Est. Priority Date: 04/07/2000
• Status: Expired due to Term

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Washington University In St Louis
• Inventors: Chamberlain, Roger D., Franklin, Mark Allen, Indeck, Ronald S., Cytron, Ron Kaplan
• Primary Examiner(s): Breene, John
• Assistant Examiner(s): FLEURANTIN, JEAN B
• Application Number:
  US10/153,151
• Publication Number:
  US 20030018630A1
• Time in Patent Office: 1,645 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-206, 709/205, 709/225, 711/4, 711/112, 704/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 40/06 Asset management; Financial planning or analysis
• 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 data storage and retrieval device and method is disclosed. The device includes at least one magnetic storage medium configured to store target data and at least one re-configurable logic device comprising an FPGA coupled to the at least one magnetic storage medium and configured to read a continuous stream of target data therefrom, having been configured with a template or as otherwise desired to fit the type of search and data being searched. The reconfigurable logic device is configured to receive at least one search inquiry in the form of a data key and to determine a match between the data key and the target data as it is being read from the at least one magnetic storage medium. This device and method can perform a variety of searches on the target data including without limitation exact and approximate match searches, sequence match searches, image match searches and data reduction searches. 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 storage and retrieval device comprising at least one mass data storage device configured to at least temporarily store target data and at least one re-configurable logic device comprising an FPGA coupled to the at least one mass data storage device,

said re-configurable logic device being configurable to read a continuous stream of target data therefrom;

and

wherein the re-configurable logic device is configured to receive at least one search inquiry in the form of a data key, and to determine a match between the data key and the target data as it is read from the at least one mass data storage device.

2. The data storage and retrieval device of claim 1 wherein the reconfigurable logic device is configured to search for matches between an analog data key and an analog target data.

3. The data storage and retrieval device of claim 1 wherein the reconfigurable logic device is configured to search for matches between a digital data key and a digital target data.

4. The data storage and retrieval device of claim 1 further comprising a plurality of magnetic storage media, each of said magnetic storage media having an associated re-configurable logic device.

5. The data storage and retrieval device of claim 1 wherein the data key is a sequence having a plurality of elements, and the re-configurable logic device comprises:

a table generator configured to generate a table having a plurality of table entries based on the elements of the sequence and the target data read from the at least one magnetic storage medium; and

a comparator configured to compare each table entry to a predetermined threshold and determine the match based on the comparison therebetween.

6. The data storage and retrieval device of claim 1 wherein the data key is an image having a plurality of pixels, and the re-configurable logic device comprises an array generator configured to generate at least one array having a plurality of cells, each cell being configured to determine a match between one pixel of the data key and one pixel of the target data as it is read from the at least one magnetic storage medium.

7. The data storage and retrieval device of claim 6 wherein each cell of the array comprises:

a data key pixel register configured to store the data key pixels;

a target data pixel register configured to load the target data pixels; and

a comparator configured to compare the data key pixels stored in the data key pixel register with the target data pixels stored in the target data pixel register to determine whether there is a match therebetween.

8. The data storage and retrieval device of claim 7 wherein the comparator is further configured to communicate with other neighboring cells of the array to determine a match between each cell and its other neighboring cells.

9. The data storage and retrieval device of claim 7 further comprising a copy register configured to store a copy of the target data pixel register once an entire target image has been loaded therein and wherein the comparator is configured to compare in parallel the last image loaded in the target data pixel register with the current image being loaded in the target data pixel register.

10. The data storage and retrieval device of claim 7 further comprising a load data key pixel register configured to load the data key pixels of the array concurrently with the loading of the target data pixels in the target data pixel register.

11. The data storage and retrieval device of claim 1 wherein the re-configurable logic device is configured to compute aggregate data reductions on any matches determined thereby.

12. The data storage and retrieval device of claim 11 further comprising a plurality of re-configurable logic devices, and a plurality of data shift registers configured to store target data as it is read from the at least one magnetic storage medium, each data shift register connected between the at least one magnetic storage medium and each re-configurable logic device. device.

13. The data storage and retrieval device of claim 1 wherein the at least one mass data storage device comprises a hard disk.

14. The data storage and retrieval device of claim 1 wherein the at least one mass data storage device comprises a bank of magnetic tape drives.

15. The data storage and retrieval device of claim 1 wherein the bank of magnetic tape drives is comfigured to store voice recordings.