Data mining accelerator for efficient data searching

• US 20040167897A1
• Filed: 02/25/2003
• Published: 08/26/2004
• Est. Priority Date: 02/25/2003
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rincon, Ann M., Strole, Norman C., Kuhlmann, Charles E.
• Application Number:
  US10/373,811
• Publication Number:
  US 20040167897A1
• Time in Patent Office: Days
• US Class Current: 707/10
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

A data mining accelerator is used with network processor technology to enable real time pattern searching of large databases. The classification and search capability of a processor element array inside the network processor is used to format database records having variable length fields in random order into ordered data packets containing fixed length fields. The contents of the fields are hashed and formatted into binary key values. Searching can be by parallel processing of multiple database records or distributed processing of a single record for multiple match conditions. A classification engine is used to sort records from a single database into separate streams based on one or more special fields, or to sort records from different databases into separate search streams for routing to search engines dedicated to each stream. The search engine collects and matches statistics in real time or searches for new, statistically significant match conditions.

Claims

1. A computer readable medium containing instructions for searching one or more database records, said instructions comprising:

a. Formatting database records containing variable length fields in random order into searchable data packets containing fixed field length in fixed order;

b. Randomly dispatching the data packets to one of several separate search engines, and

c. Repeating the formatting and dispatching of new records in real time as they are added to a database.

2. The medium according to claim 1 wherein the instructions are carried out in a network processor and the search engines utilize multiple processor elements within the network processor.

3. The medium according to claim 1 wherein the instructions determine whether searching will be carried out by parallel processing of multiple data packets using multiple search engines or by distributed processing of a single data packet for multiple match conditions using multiple match counters.

4. The medium according to claim 1 wherein the instructions control a classification engine for generating a search key.

5. A method for analyzing at least one information database comprising:

a. Providing a searchable database record table comprising a data packet containing fixed length fields in fixed order;

b. Establishing criteria for a search through the record table;

c. Constructing at least one classification record to match the criteria; and

d. Determining an action to be taken as determined by a positive or a negative criteria match.

6. The method according to claim 5 wherein the database analysis is conducted on a network processor.

7. The method according to claim 6 wherein a variable field length randomly ordered database record is formatted into said searchable fixed field length data packet in fixed order.

8. The method according to claim 6 wherein the records in the record table are preclassified using one or more of the fixed length fields into separate record streams, and the streams are dispatched to separate search engines.

9. The method according to claim 8 wherein the records are preclassified by generating fixed length keys using a hashing scheme.

10. The method according to claim 6 including the further step of conducting real-time searching of new records as they are added to the database record table.

11. The method according to claim 6 further including the step of identifying new correlations or trends among selected data records for future comparison.

12. The method according to claim 6 wherein the database record table is searched based on the criteria established for the search.

13. The method according to claim 6 wherein the database record is searched either by parallel processing or by distributed processing.

14. A system for analyzing at least one information database comprising:

a. a searchable database record table comprising a data packet containing fixed length fields in fixed order;

b. criteria for a search through the record table;

c. at least one classification record constructed so as to match the criteria; and

d. a mechanism for determining an action to be taken based on a positive or a negative criteria match.

15. The system according to claim 14 comprising a network processor.

16. The system according to claim 15 including a variable field length randomly ordered database record formatted into said searchable fixed field length data packet in fixed order.

17. The system according to claim 16 including means for preclassifying the records in the table, using one or more of the fixed length fields, into separate record streams, and a dispatcher is used for forwarding the streams to separate search engines.

18. The system according to claim 17 wherein the records can be preclassified by generating fixed length keys using a hashing scheme.

19. The system according to claim 14 including the further capability of conducting real-time searching of new records as they are added to the database record table.

20. The system according to claim 15 wherein the network processor includes special hardware means for searching the database record table.

21. The system according to claim 14 further including a key search engine implemented in hardware.

22. The system according to claim 15 wherein the network processor is capable of searching the database either by parallel processing or by distributed processing.

23. The system according to claim 15 wherein the network processor uses a plurality of processor elements as packet processors.