Data store for knowledge-based data mining system

• US 6,993,534 B2
• Filed: 05/08/2002
• Issued: 01/31/2006
• Est. Priority Date: 05/08/2002
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Meyer, Joerg, Tomkins, Andrew S., Gruhl, Daniel Frederick, Denesuk, Matthew, McCurley, Kevin Snow, Rajagopalan, Sridhar, Zien, Jason Yeong
• Primary Examiner(s): Pardo, Thuy N.
• Application Number:
  US10/142,673
• Publication Number:
  US 20030212699A1
• Time in Patent Office: 1,364 Days
• Field of Search: 707/2, 707/3, 707/4, 707/6, 707/103, 707/10, 707/102, 707/101, 707/104, 707/104.1, 709/206, 709/224, 709/225, 713/168, 713/166, 705/10
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

In a data mining system, data is gathered into a data store using, e.g., a Web crawler. The data is classified into entities and stored into underlying vertical and horizontal tables respectively representing miner outputs and entities that can be the subjects of indexing. Data miners use rules to process the entities and append respective keys to the entities representing characteristics of the entities as derived from rules embodied in the miners, with the keys being associated with the entities in the tables. With these keys, characteristics of entities as defined by disparate expert authors of the data miners are identified for use in responding to complex data requests from customers.

Claims

1. A system, comprising:

at least one data store containing entities;

at least one lower level analysis engine communicating with the data store and generating an output using a first set of rules;

at least one higher level analysis engine receiving the output of the lower level analysis engine and generating an output using a second set of rules, wherein the outputs are associated with entities in the data store; and

an indexer associated with the data store, wherein tokenization is decoupled from indexing in the indexer.

2. The system of claim 1, wherein the data store includes vertical tables and horizontal tables, and the vertical tables are entered using one of the outputs and the horizontal tables are entered using an entity identification.

3. The system of claim 1, wherein the outputs are keys representing respective characteristics of the associated entity.

4. The system of claim 1, wherein the data store is a relational database system.

5. The system of claim 1, wherein the data store is a file system.

6. The system of claim 1, further comprising a fast, semiconductor-implemented cache associated with the indexer and data store.

7. The system of claim 6, further comprising a query processor accessing one or more of the cache, indexer, and data store to execute queries from at least one analysis engine.

8. The system of claim 7, further comprising at least one work queue associated with at least one analysis engine.

9. The system of claim 1, wherein an entity identification encodes a corresponding entity identification and entity type.

10. The system of claim 1, wherein the indexer includes indices of keys and key values found in the data store.

13. The system of claim 10, wherein the indexer contains text indices.

15. The system of claim 1, wherein the indexer is a generalization of an inverted file text indexer that indexes web documents and provides a keyword search application programming interface (API) to the documents.

16. The system of claim 1, wherein the indexer holds defined keys for a particular entity to allow Boolean queries.

11. A system, comprising:

at least one data store containing entities;

at least one lower level analysis engine communicating with the data store and generating output using a first set of rules;

at least one higher level analysis engine receiving the output of the lower level analysis engine and generating an output using a second set of rules, wherein the outputs are associated with entities in the data store; and

an indexer associated with the data score, wherein the indexer includes indices of keys and key values found in the data store and further wherein the indexer contains Boolean indices storing “

yes”

or “

no”

values to queries of the form, “

does key k have value v?”

.

12. A system, comprising:

at least one data store containing entities;

at least one lower level analysis engine communication with the data store and generating an output using a first set of rules;

at least one higher level analysis engine receiving the output of the lower level analysis engine and generating an output using a second set of rules, wherein the outputs are associated with entities in the data store; and

an indexer associated with the data store, wherein the indexer includes indices of keys and key values found in the data store and further wherein the indexer contains range indices storing ranges of key values.

14. A system, comprising:

at least one data store containing entities;

at least one lower level analysis engine communicating with the data store and generating an output using a first set of rules;

at least one higher level analysis engine receiving the output of the lower level analysis engine and generating an output using a second set of rules, wherein the outputs are associated with entities in the data store; and

an indexer associated with the data store, wherein the indexer includes indices and the data store includes tables that do not indicate where in an entity a particular name or text occurs, but only that an entity has a particular characteristic.

17. A system, comprising:

at least one data store containing entities;

at least one lower level analysis engine communicating with the data store and generating an output using a first set of rules;

at least one higher level analysis engine receiving the output of the lower level analysis engine and generating an output using a second set of rules, wherein the outputs are associated with entities in the data store; and

an indexer associated with the data store, wherein the indexer contains graph data to support inlink and outlink queries.

18. A method for storing data to support a knowledge-band data mining system, comprising:

storing entities in at least one data store associated with an index;

communicating with the data store using at least a first analysis engine;

generating an output using a first set of rules associated with the first analysis engine;

sending the output to at least a second analysis engine;

generating an output using a second set of rules associated with the second engine; and

associating the outputs with entities, wherein the indexer contains graph data to support inlink and outlink queries.

19. The method of claim 18, wherein the data store includes vertical tables and horizontal tables, and the method comprises entering the vertical cables using one of the outputs.

20. The method of claim 18, wherein the data store includes vertical tables and horizontal cables, and the method comprises entering horizontal cables using an entity identification.

21. The method of claim 18, wherein the outputs are keys representing respective characteristics of the associated entity.

22. The method of claim 18, wherein the data score is a relational database system.

23. The method of claim 18, wherein the data score is a file system.

24. The method of claim 18, further comprising associating the indexer with the data store.

25. The method of claim 24, further comprising associating a fast, semiconductor-implemented cache with the indexer and data store.

26. The method of claim 25, further comprising accessing, with a query processor, one or more of the cache, indexer, and data store to execute queries from at least one analysis engine.

27. The method of claim 26, further comprising associating at least one work queue with at least one analysis engine.

28. The method of claim 18, wherein an entity identification encodes a corresponding entity identification and entity type.

29. The method of claim 24, wherein the indexer includes indices of keys and key values found in the data store.

32. The method of claim 29, wherein the indexer contains text indices.

34. The method of claim 24, wherein the indexer is a generalization of an inverted file text indexer that indexes web documents and provides a keyword search application programming interface (API) to the documents.

35. The method of claim 24, wherein the indexer holds defined keys for a particular entity to allow boolean queries.

30. A method for storing data to support a knowledge-based data mining system, comprising:

storing entities in at least one data store associated with an index;

communicating with the data store using at least a first analysis engine;

generating an output using a first set of rules associated with the first analysis engine;

sending the cutout to at least a second analysis engine;

generating an cutout using a second set of rules associated with the second engine; and

associating the cutouts with entities, wherein the Indexer includes indices of keys and key values found in the data store and further wherein the indexer contains Boolean indices storing “

yes”

or “

no”

values to queries of the form, “

does key k have value v?”

.

31. A method for storing data to support a knowledge-based data mining system, comprising:

storing entities in at least one data store associated with an index;

communicating with the data store using at least a first analysis engine;

generating an output using a first set of rules associated with the first analysis engine;

sending the output to at least a second analysis engine;

generating an output using a second set of rules associated with the second engine; and

associating the outputs with entities, wherein the indexer includes indices of keys and key values found in the data store and further wherein the indexer contains range indices storing ranges of key values.

33. A method for storing data to support a knowledge-based data mining system, comprising:

storing entities in at least one data score associated with an index;

communicating with the data store using at least a first analysis engine;

generating an output using a first set of rules associated with the first analysis engine;

sending the output to at least a second analysis engine;

generating an output using a second set of rules associated with the second engine; and

associating the outputs with entities, wherein the indexer includes indices and the data store includes tables that do not indicate where in an entity a particular name or text occurs, but only that an entity has a particular characteristic.

36. A method for storing data to support a knowledge-based data mining system, comprising:

storing entities in at least one data store associated with an index;

communicating with the data store using at least a first analysis engine;

generating an output using a first set of rules associated with the first analysis engine;

sending the output to at least a second analysis engine;

generating an output using a second set of rules associated with the second engine; and

associating the outputs with entities, wherein tokenization is decoupled from indexing in the indexer.

37. A system for data mining, comprising:

means for storing entities in at least one data store in both horizontal tables and vertical tables, the data store being associated with an index;

means for communicating with the data store using at least a first analysis engine;

means for generating an output using a first set of rules associated with the first analysis engine;

means for sending the output to at least a second analysis engine;

means for generating an output wing a second set of rules associated with the second engine; and

means for associating the outputs with entities, wherein the indexer includes indices and the data store includes tables that do not indicate where in an entity a particular name or text occurs, but only that an entity has a particular characteristic.

38. The system of claim 37, comprising means fir entering the vertical tables using one of the outputs.

39. The system of claim 37, means for comprising entering horizontal tables using an entity identification.

40. The system of claim 37, wherein the outputs are keys representing respective characteristics of the associated entity.

41. The system of claim 37, wherein the data store is a relational database system.

42. The system of claim 37, wherein the data store is a file system.

43. The system of claim 37, further comprising means for associating an indexer with the data store.

44. The system of claim 43, further comprising means for associating a fast, semiconductor-implemented cache with the indexer and data store.

45. The system of claim 44, further comprising means for accessing, with a query processor, one or more of the cache, indexer, and data store to execute queries from at least one analysis engine.

46. The system of claim 45, further comprising means for associating at least one work queue with at least one analysis engine.

47. The system of claim 37, wherein an entity identification encodes a corresponding entity identification and entity type.

48. The system of claim 43, wherein the indexer includes indices of keys and key values found in the tables.

50. The system of claim 48, wherein the indexer contains range indices storing ranges of key values.

51. The system of claim 48, wherein the indexer contains text indices.

52. The system of claim 43, wherein the indexer is a generalization of an inverted file text indexer that indexes web documents and provides a keyword search application programming interface (API) to the documents.

53. The system of claim 43, wherein the indexer holds defined keys for a particular entity to allow boolean queries.

49. A system for data mining, comprising:

means for storing entities in at least one data store in both horizontal tables and vertical tables, the data store being associated wit an index;

means for communicating with the data store using at least a first analysis engine;

means for generating an output using a first set of rules associated with the first analysis engine;

means for sending the cutout to at least ,a second analysis engine;

means for generating an cutout using a second set of rules associated with the second engine; and

means for associating the cutouts with entities, wherein the indexer include indices of keys and key values found in the tables and further wherein the indexer contains Boolean indices storing “

yes”

or “

no”

values to queries of the form, “

does key k have value v?”

.

54. A system for data mining, comprising:

means for storing entities in at least one data store in both horizontal tables and vertical tables, the data store being associated with an index;

means for communicating with the data store using at least a first analysis engine;

means for generating an cutout using a first set of rules associated with the first analysis engine;

means for sending the output to at least a second analysis engine;

means for generating an output using a second set of rules associated with the second engine; and

means for associating the outputs with entities, wherein the indexer contains graph data to support inlink and outlink queries.