# US 2016/0253366 A1 · Analyzing a parallel data stream using a sliding frequent pattern tree

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253366 A1
- Document ID: US20160253366A1
- Status: Published application
- Kind: A1
- Application number: 15/028,785
- Filed: 2013-10-15
- Published: 2016-09-01
- Earliest claimed: 2013-10-15
- Assignees: Hewlett Packard Enterprise Development LP
- Applicants: Hewlett Packard Enterprise Development LP
- Inventors: Meichun Hsu; Qiming Chen
- Web page: https://patentgrep.com/patent/US20160253366A1

## CPC

- G06F 16/2465: {Query processing support for facilitating data mining operations in structured databases}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 16/2246: {Trees, e.g. B+trees}
- G06F 16/24568: {Data stream processing; Continuous queries}
- G06F 18/24323: {Tree-organised classifiers}
- G06F 2218/00: Aspects of pattern recognition specially adapted for signal processing
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## 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

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 4)

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.

### Claim 6 (depends on 1)

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.

### Claim 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.

### Claim 8 (depends on 7)

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.

### Claim 9 (depends on 7)

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.

### Claim 10 (depends on 7)

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.

### Claim 11 (depends on 7)

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.

### Claim 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.

### Claim 13 (depends on 12)

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.

### Claim 14 (depends on 12)

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.

### Claim 15 (depends on 12)

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.
