Association rule mining in peer-to peer systems

A method for data mining, comprising:

• defining a global condition relating to a distributed database system, which includes a plurality of partitions stored on respective storage devices associated with respective computing nodes that are interconnected by a communication network;
• at each node and independently of the other nodes, evaluating a local condition responsively to data in a respective partition associated with the node and to messages received from a subset of the nodes that neighbor the node, wherein the local condition is defined such that fulfillment of the local condition at all the nodes is indicative of the fulfillment of the global condition;
• when the local condition is not fulfilled at the node, exchanging at least one message with at least one node in the subset of the nodes;
• and
• performing an action with respect to the distributed database responsively to the fulfillment of the global condition.

A system for mining association rules, comprising

• a plurality of storage devices, adapted to hold respective partitions of a database;
• and
• a corresponding plurality of computing nodes, each node associated with a respective one of the storage devices and coupled to communicate over a communication network with neighbor nodes among the plurality of the computing nodes,
• wherein each node in at least a subset of the nodes is adapted:
• to generate a candidate association rule defining an association relationship between itemsets in the database,
• to assess a global correctness of the candidate association rule asynchronously with the other computing nodes by communicating with only the neighbor nodes, and
• to perform an action with respect to the itemsets based on the assessed global correctness.

A computer software product for mining association rules using computing nodes that are associated with respective storage devices holding respective partitions of a database and are coupled to communicate over a communication network with neighbor nodes among the plurality of computing nodes, the product comprising;

• a computer-readable medium, in which program instructions are stored, which instructions, when read by the computing nodes, cause each node in at least a subset of the computing nodes:
• to generate a candidate association rule defining an association relationship between itemsets in the database,
• to assess a global correctness of the candidate association rule asynchronously with the other computing nodes by communicating with only the neighbor nodes, and
• to perform an action with respect to the itemsets based on the assessed global correctness.

A computer software product for mining data using computing nodes that are associated with respective storage devices holding respective partitions of a database and are coupled to communicate over a communication network with neighbor nodes among the plurality of computing nodes, the product comprising:

• a computer-readable medium, in which program instructions are stored, which instructions, when read by the computing nodes, cause each node:
• to accept a definition of a global condition relating to at least part of the distributed database,
• to evaluate, independently of the other nodes, a local condition responsively to data in a respective partition associated with the node and to messages received from the neighbor nodes,
• wherein the local condition is defined such that fulfillment of the local condition at all the nodes is indicative of the fulfillment of the global condition,
• to exchange at least one message with at least one of the neighbor nodes when the local condition is not fulfilled at the node, and
• to perform an action with respect to the distributed database responsively to the fulfillment of the global condition.