Data store for knowledge-based data mining system

• US 20030212699A1
• Filed: 05/08/2002
• Published: 11/13/2003
• Est. Priority Date: 05/08/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Zien, Jason Yeong, Meyer, Joerg, Tomkins, Andrew S., Gruhl, Daniel Frederick, Denesuk, Matthew, McCurley, Kevin Snow, Rajagopalan, Sridhar
• Granted Patent: US 6,993,534 B2
• Time in Patent Office: Days
• US Class Current: 707/102
• 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; and

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.

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 an indexer associated with the data store.

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

8. The system of claim 7, 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.

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

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

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

12. The system of claim 11, wherein the indexer contains Boolean indices storing “

yes”

or “

no”

values to queries of the form, “

does key k have value v?”

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

14. The system of claim 11, wherein the indexer contains text indices.

15. The system of claim 6, 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.

16. The system of claim 6, 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.

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

18. The system of claim 6, wherein the indexer contains graph data to support inlink and outlink queries.

19. The system of claim 6, wherein tokenization is decoupled from indexing in the indexer.

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

storing entities in at least one data store;

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.

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

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

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

24. The method of claim 20, wherein the data store is a relational database system.

25. The method of claim 20, wherein the data store is a file system.

26. The method of claim 20, further comprising associating an indexer with the data store.

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

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

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

30. The method of claim 20, wherein an entity identification encodes a corresponding entity identification and entity type.

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

32. The method of claim 31, wherein the indexer contains Boolean indices storing “

yes”

or “

no”

values to queries of the form, “

does key k have value v?”

33. The method of claim 31, wherein the indexer contains range indices storing ranges of key values.

34. The method of claim 31, wherein the indexer contains text indices.

35. The method of claim 26, 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. The method of claim 26, 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.

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

38. The method of claim 26, wherein the indexer contains graph data to support inlink and outlink queries.

39. The method of claim 26, wherein tokenization is decoupled from indexing in the indexer.

44. The system of claim 20, wherein the data store is a relational database system.

40. A system for data mining, comprising:

means for storing entities in at least one data store in both horizontal tables and vertical tables;

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 using a second set of rules associated with the second engine; and

means for associating the outputs with entities.

41. The system of claim 40, comprising means for entering the vertical tables using one of the outputs.

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

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

45. The system of claim 40, wherein the data store is a file system.

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

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

48. The system of claim 47, 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.

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

50. The system of claim 40, wherein an entity identification encodes a corresponding entity identification and entity type.

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

52. The system of claim 51, wherein the indexer contains Boolean indices storing “

yes”

or “

no”

values to queries of the form, “

does key k have value v?”

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

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

55. The system of claim 46, 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.

56. The system of claim 46, 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.

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

58. The system of claim 46, wherein the indexer contains graph data to support inlink and outlink queries.