ANALYZING A PARALLEL DATA STREAM USING A SLIDING FREQUENT PATTERN TREE

• US 20160253366A1
• Filed: 10/15/2013
• Published: 09/01/2016
• Est. Priority Date: 10/15/2013
• Status: Abandoned Application

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Hsu, Meichun, Chen, Qiming
• Application Number:
  US15/028,785
• Publication Number:
  US 20160253366A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2465 Query processing support for facilitating data mining operations in structured databases
• CPC Class Codes: G06F 18/24323 Tree-organised classifiers
• CPC Class Codes: G06F 2218/00 Aspects of pattern recognition specially adapted for signal processing
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A technique for analyzing a parallel data stream using a sliding FP tree can include create a sliding FP tree using input tuples belonging to a parallel sliding window boundary and analyze patterns of the parallel data stream in the parallel sliding window boundary.

Claims

1. A non-transitory computer-readable medium storing instructions executable by a processing resource to cause a computer to:

identify input channels for a plurality of sliding frequent pattern (FP) tree task instances of a parallel data stream;

create a sliding FP tree for each of the plurality of sliding FP tree task instances using input tuples from the identified input channels belonging to a first parallel sliding window boundary; and

analyze patterns of the parallel data stream first parallel sliding window boundary using the plurality of sliding FP trees.

2. The non-transitory computer-readable medium of claim 1, wherein the instructions executable by the processing resource to analyze patterns of the parallel data stream include instructions executable to:

combine patterns of each of the plurality of sliding FP trees in response to an input tuple from each input channel reaching a granule boundary of the first parallel sliding window.

3. The non-transitory computer-readable medium of claim 1, wherein the instructions executable by the processing resource include instructions executable to hold an input tuple from the first parallel sliding window based on the input tuple belonging to a second parallel sliding window boundary.

4. The non-transitory computer readable medium of claim 1, wherein the instructions executable by the processing resource to analyze patterns of the parallel data stream include instructions executable to extract frequent item-sets from each of the plurality of sliding FP trees.

5. The non-transitory computer-readable medium of claim 4, wherein the instructions executable by the processing resource include instructions executable to disregard item-sets with a frequency below a threshold frequency.

6. The non-transitory computer-readable medium of claim 1, wherein the instructions executable by the processing resource include instructions executable to update a current granule number as a minimum granule number of each input channel.

7. A method for analyzing a parallel data stream, including:

ordering a plurality of item-sets associated with a parallel data stream based on a frequency of each of the plurality of item-sets;

incrementally creating a sliding frequent pattern (FP) tree over a plurality of parallel sliding windows using the order of the plurality of item-sets; and

analyzing patterns of the parallel data stream using the sliding FP tree in each parallel sliding window in response to an input tuple for each input channel of the parallel data stream reaching a boundary of the corresponding parallel sliding window.

8. The method of claim 7, wherein creating the sliding FP tree includes incrementally building and pruning the sliding FP tree along the plurality of parallel sliding windows.

9. The method of claim 7, wherein creating the sliding FP tree includes:

adding patterns to the sliding FP tree identified in a current parallel sliding window; and

subtracting patterns from the sliding FP tree identified in a slide in a previous parallel sliding window.

10. The method of claim 7, wherein analyzing patterns of the parallel data stream includes:

summarizing the patterns from a plurality of sliding FP trees, wherein each of the plurality of sliding FP trees is associated with a sliding FP tree task instance among a plurality of sliding FP tree task instances of the parallel data stream; and

placing the pattern of each sliding FP tree in a pattern count map.

11. The method of claim 7, wherein incrementally creating the sliding FP tree includes holding an input tuple belonging to a different parallel sliding window than a current parallel sliding window.

12. A system for analyzing a parallel data stream, comprising:

a processing resource; and

a memory resource communicatively coupled to the processing resource containing instructions executable by the processing resource to implement a number of engines including;

a parallel window engine to define a plurality of parallel sliding window boundaries;

an item-set order engine to organize input tuples using a defined frequency baser order of a plurality of item-sets;

an input tuple engine to store input tuples belonging to a future parallel sliding window;

a sliding FP tree engine to incrementally create a sliding FP tree for each of a plurality of sliding FP tree task instances using the defined frequency based order, wherein each increment to one of the sliding FP trees includes;

add item-sets to the sliding FP tree identified in a current parallel sliding window boundary among the plurality of parallel sliding window boundaries; and

subtract item-sets from the sliding FP tree identified in a previous parallel sliding window boundary among the plurality of sliding window boundaries; and

an analyze engine to identify frequent item-sets in the parallel data stream using the plurality of sliding FP trees.

13. The system of claim 12, wherein an item-set is identified as frequent in response to an identified frequency in the current parallel sliding window boundary being greater than a threshold frequency.

14. The system of claim 12, wherein the analyze engine further summarizes results at each parallel sliding window, wherein a summarized result at one of the parallel sliding windows includes a combined pattern count map from each of the plurality of sliding FP tree task instances.

15. The system of claim 12, wherein the subtracted item-sets from the sliding FP tree includes a subtraction of counts of nodes belonging to a transaction in the previous parallel sliding window in a reverse order.