METHODS AND FRAMEWORK FOR CONSTRAINT-BASED ACTIVITY MINING (CMAP)

• US 20090043766A1
• Filed: 08/07/2007
• Published: 02/12/2009
• Est. Priority Date: 08/07/2007
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Wang, Changzhou, Tjoelker, Rodney A., Kao, Anne, Choi, Jai J.
• Granted Patent: US 8,046,322 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases

Abstract

A method of mining data to discover activity patterns within the data is described. The method includes receiving data to be mined from at least one data source, determining which of a number of specified interests and constraints are associated with the mining process, selecting corresponding mining agents that combine search algorithms with propagators from the specified constraints, and finding any activity patterns that meet the specified interests and constraints.

Claims

6-1. A method according to claim 1 further comprising:

at least one of adding, removing, and modifying pattern destinations based on a configuration of the found activity patterns; and

providing mining tasks based on a configuration of the pattern destinations.

11. A computer-based system for constraint-based mining of activity patterns within a framework, said system comprising:

a data input;

a plurality of data mining tools within the framework and operable to run on said system, said data mining tools configured to search data received at said data input for one or both of temporal and spatial patterns for activities of interest within one or more scenarios;

a plurality of constraints, said constraints based on knowledge and experiences, and operable to cause said system to determine whether one or more patterns satisfies the said constraints, said constraints organized based on a subsumption relationship among the constraints; and

at least one database configured for operation as a pattern repository.

12. A computer-based system according to claim 11 wherein said plurality of constraints comprises a mode constraint, said mode constraint configured to:

specify permissions on each argument for a given predicate; and

specify a maximum number of atoms matching a permission combination allowed in a pattern.

13. A computer-based system according to claim 11 wherein said plurality of constraints comprises a syntactic filter constraint, said syntactic filter constraint configured to:

utilize a sequence of modes to filter patterns; and

avoid generation of patterns with redundant atoms.

14. A computer-based system according to claim 11 wherein said plurality of constraints comprises a semantic filter constraint, said semantic filter constraint comprising:

a minimum frequency threshold;

a sequence of modes; and

a Boolean expression on the arguments in the modes.

15. A computer-based system according to claim 11 wherein said plurality of constraints comprises a generation rule constraint, said generation rule constraint comprising:

a sequence of modes as matching conditions; and

a set of modes used to generate new atoms.

16. A computer-based system according to claim 11 wherein said plurality of constraints comprises at least one of a maximum length constraint, an extended length constraint, and a complex constraint.

17. A computer-based system according to claim 11 wherein to search data received at said data input, said system is configured to:

initialize the search by creating a single pattern using a target predicate; and

invoke a refining process with the single pattern.

18. A computer-based system according to claim 17 wherein to invoke the refining process, said system is configured to stop the refining process if a maximum length is reached or if an extended length constraint cannot be met by the single pattern.

19. A computer-based system according to claim 17 wherein to invoke the refining process, said system is configured to:

generate candidate patterns according to a generation rule constraint if the single pattern does not meet at least one generation rule constraint; and

generate candidate patterns according to the mode constraints using variables introduced in a splitting atom, and generate candidate patterns by copying atoms that are younger children of the splitting atom if the single pattern meets all generation rule constraints.

20. A computer-based system according to claim 19 wherein said system is configured to:

remove from a candidate pattern set those candidate patterns that do not met at least one of a specified syntactic constraint, a semantic constraint, a generic data independent constraint, and a generic data dependent constraint; and

recursively invoke the refining process for each candidate pattern in the candidate pattern set.