Patent US957473A successfully refreshed from Google Patents.
US5758147A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Efficient information collection method for parallel data mining
Assignee: International Business Machines Corp
•
Filing: 1995-06-28
•
Granted: 1998-05-26
•
Expires: 2015-06-28
Abstract
Abstract An efficient method and system of communicating and accumulating global information for parallel data mining. Since each database is partitioned, a single node in a parallel environment will be unable to make decisions based on global information. A novel technique of progressive thresholding is devised to accumulates global information as a function of a transaction support threshold while minimizing transmission overhead. The transaction support threshold is varied as a function of the number of nodes contributing to the global information progresses.
Inventors
- 👤 Ming-Syan Chen
- 👤 Philip Shi-lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 12:29
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2465; G06F2216/00; G06F2216/03; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99935; Y10S707/99936
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
120 words
A method of communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, comprising the steps of: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; and determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying.
Claim 2
Independent Claim
120 words
A method of communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, comprising the steps of: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; and determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying.
Claim 3
Dependent Claim
24 words
The method of claim 1, further comprising the step of: generating association rules amongst events meeting the transaction support threshold, responsive to said determining.
Claim 4
Dependent Claim
37 words
The method of claim 1 wherein said determining the set of global events further comprises polling nodes which did not contribute to the cumulative count of events when a maximum count value exceeds the transaction support threshold.
Claim 5
Dependent Claim
25 words
The method of claim 1 wherein said accumulating the local count of events across all nodes is accomplished using a hash table and hashing function.
Claim 6
Independent Claim
186 words
A method of communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, comprising the steps of: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; wherein said accumulating the local count of events across all nodes is accomplished using a hash table and hashing function; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying; wherein said determining the set of global events further comprises polling nodes which did not contribute to the cumulative count of events when a maximum count value exceeds the transaction support threshold; and generating association rules amongst events meeting the transaction support threshold, responsive to said determining.
Claim 7
Independent Claim
186 words
A method of communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, comprising the steps of: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; wherein said accumulating the local count of events across all nodes is accomplished using a hash table and hashing function; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying; wherein said determining the set of global events further comprises polling nodes which did not contribute to the cumulative count of events when a maximum count value exceeds the transaction support threshold; and generating association rules amongst events meeting the transaction support threshold, responsive to said determining.
Claim 8
Dependent Claim
140 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, said method steps comprising: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; and determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying.
Claim 9
Dependent Claim
140 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, said method steps comprising: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; and determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying.
Claim 10
Dependent Claim
26 words
The program storage device of claim 6, further comprising the step of: generating association rules amongst events meeting the transaction support threshold, responsive to said determining.
Claim 11
Dependent Claim
45 words
The program storage device of claim 6 wherein said determining the set of global events further comprises polling nodes which did not previously contribute to the cumulative count of events, said polling being a function of a maximum count value exceeding the transaction support threshold.
Claim 12
Dependent Claim
34 words
The program storage device of claim 6 further comprising a hash table wherein said accumulating the local count of events across all nodes is accomplished using a hashing function associated with said hash table.
Claim 13
Dependent Claim
212 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, said method steps comprising: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; wherein said accumulating the local count of events across all nodes is accomplished using a hash table and hashing function; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying; wherein said determining the set of global events further comprises polling nodes which did not previously contribute to the cumulative count of events, said polling being a function of a maximum count value exceeding the transaction support threshold; and generating association rules amongst events meeting the transaction support threshold, responsive to said determining.
Claim 14
Dependent Claim
212 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes, wherein a transaction has at least one event associated therewith, said method steps comprising: determining a local count of all events associated with each node; communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said determining; wherein said accumulating the local count of events across all nodes is accomplished using a hash table and hashing function; varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said communicating and accumulating; determining a set of global events which meet the transaction support threshold, responsive to said communicating and said varying; wherein said determining the set of global events further comprises polling nodes which did not previously contribute to the cumulative count of events, said polling being a function of a maximum count value exceeding the transaction support threshold; and generating association rules amongst events meeting the transaction support threshold, responsive to said determining.
Claim 15
Independent Claim
175 words
A system for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes which are communicatively coupled by an interconnection network, wherein a transaction has at least one event associated therewith, said system comprising: a memory coupled to each node for storing and accessing each parallel transaction database; a local event counter for determining a local count of all events associated with each node; an event accumulator for communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said local event counter; a progressive threshold controller associated with each node wherein said progressive threshold controller is adapted for varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said event accumulator; and a global event counter for determining a set of global events which meet the transaction support threshold, responsive to said event accumulator and said progressive threshold controller.
Claim 16
Independent Claim
175 words
A system for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes which are communicatively coupled by an interconnection network, wherein a transaction has at least one event associated therewith, said system comprising: a memory coupled to each node for storing and accessing each parallel transaction database; a local event counter for determining a local count of all events associated with each node; an event accumulator for communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said local event counter; a progressive threshold controller associated with each node wherein said progressive threshold controller is adapted for varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said event accumulator; and a global event counter for determining a set of global events which meet the transaction support threshold, responsive to said event accumulator and said progressive threshold controller.
Claim 17
Dependent Claim
25 words
The system of claim 11, further comprising: means for generating association rules amongst events meeting the transaction support threshold, responsive to said global event counter.
Claim 18
Dependent Claim
41 words
The system of claim 11 wherein said global event counter further comprises means for polling nodes which did not previously contribute to the cumulative count of events, said polling being a function of maximum count value exceeding the transaction support threshold.
Claim 19
Dependent Claim
27 words
The system of claim 11 wherein said memory comprises a hash table stored therein and said event accumulator includes a hashing function for accessing said hash table.
Claim 20
Independent Claim
245 words
A system for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes which are communicatively coupled by an interconnection network, wherein a transaction has at least one event associated therewith, said system comprising: a memory coupled to each node for storing and accessing both the parallel transaction database and a hash table; a local event counter for determining a local count of all events associated with each node; an event accumulator including a hashing function associated with the hash table for communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said local event counter; a progressive threshold controller associated with each node wherein said progressive threshold controller is adapted for varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said event accumulator; and a global event counter for determining a set of global events which meet the transaction support threshold, responsive to said event accumulator and said progressive threshold controller wherein said global event counter further comprises means for polling nodes which did not previously contribute to the cumulative count of events, said polling being a function of a maximum count value exceeding the transaction support threshold; and means for generating association rules amongst events meeting the transaction support threshold, responsive to said global event counter.
Claim 21
Independent Claim
245 words
A system for communicating and accumulating global information contained in a parallel transaction database which is partitioned across a plurality of nodes which are communicatively coupled by an interconnection network, wherein a transaction has at least one event associated therewith, said system comprising: a memory coupled to each node for storing and accessing both the parallel transaction database and a hash table; a local event counter for determining a local count of all events associated with each node; an event accumulator including a hashing function associated with the hash table for communicating and accumulating the local count of events across all nodes as a function of a transaction support threshold, responsive to said local event counter; a progressive threshold controller associated with each node wherein said progressive threshold controller is adapted for varying the transaction support threshold as a function of how many nodes have contributed to a cumulative count of events in a given node, responsive to said event accumulator; and a global event counter for determining a set of global events which meet the transaction support threshold, responsive to said event accumulator and said progressive threshold controller wherein said global event counter further comprises means for polling nodes which did not previously contribute to the cumulative count of events, said polling being a function of a maximum count value exceeding the transaction support threshold; and means for generating association rules amongst events meeting the transaction support threshold, responsive to said global event counter.
References Cited (Backward Citations)
US4799156A
Cited
US5197002A
Cited
US5255181A
Cited
US5223827A
Cited
US5324922A
Cited
US5495656A
Cited
US5461699A
Cited
US5467268A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |