org.processmining.stream.model.datastructure.countmin

Class CountMinSketchImpl<T>

java.lang.Object

org.processmining.stream.model.datastructure.AbstractDataStructure<T,CountMinSketchParameterDefinition>

org.processmining.stream.model.datastructure.countmin.CountMinSketchImpl<T>

All Implemented Interfaces:

DataStructure<T>, SketchBasedDataStructure<T>

Direct Known Subclasses:

PointerBasedCountMinSketch

public class CountMinSketchImpl<T>
extends AbstractDataStructure<T,CountMinSketchParameterDefinition>
implements SketchBasedDataStructure<T>

Implementation of Count Min Sketch: Paper: An Improved Data Stream Summary: The Count-Min Sketch and its Applications; Cormode et al.; 2005; 10.1016/j.jalgor.2003.12.001 Code adapted from: https://github.com/addthis/stream-lib/blob/master/src/main/java/com/ clearspring/analytics/stream/frequency/CountMinSketch.java commit: 9f1bf8bd8d81b4fcaf632a18be90091dd68afd4f License of the original code: * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Nested Class Summary

Nested classes/interfaces inherited from interface org.processmining.stream.model.datastructure.DataStructure

DataStructure.Type

Field Summary

Fields

Modifier and Type	Field and Description
static long	PRIME_MODULUS

Fields inherited from interface org.processmining.stream.model.datastructure.DataStructure

FINITE_ITERABLE_DATA_STRUCTURES, FINITE_ITERABLE_POINTER_DATA_STRUCTURES, FINITE_POINTER_DATA_STRUCTURES, INFIITE_DATA_STRUCTURES, ITERABLE_DATA_STRUCTURES, POINTER_DATA_STRUCTURES

Constructor Summary

Constructors

Constructor and Description
CountMinSketchImpl(java.util.Map<CountMinSketchParameterDefinition,DSParameter<?>> params)

Method Summary

Modifier and Type	Method and Description
java.util.Collection<T>	add(T item) add elements to a stream based data structure may lead to removal of other elements in the data structure If possible, the implementing algorithm will return a collection of elements.
void	clear()
boolean	contains(java.lang.Object o)
long	estimateCount(T item) The estimate is correct within 'epsilon' * (total item count), with probability 'confidence'.
int	getCapacity()
double	getConfidence()
protected int	getDepth()
long	getFrequencyOf(T e)
double	getRelativeError()
long	getSize()
protected long[][]	getTable()
DataStructure.Type	getType()
protected int	getWidth()
boolean	isEmpty()
void	setSize(long size)
long	size()

Methods inherited from class org.processmining.stream.model.datastructure.AbstractDataStructure

getParameters, getUsedMemoryInBytes

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface org.processmining.stream.model.datastructure.DataStructure

getParameters, getUsedMemoryInBytes

Field Detail

PRIME_MODULUS

public static final long PRIME_MODULUS

See Also:

Constant Field Values

Constructor Detail

CountMinSketchImpl

public CountMinSketchImpl(java.util.Map<CountMinSketchParameterDefinition,DSParameter<?>> params)

Method Detail

add

public java.util.Collection<T> add(T item)

Description copied from interface: DataStructure

add elements to a stream based data structure may lead to removal of other elements in the data structure If possible, the implementing algorithm will return a collection of elements.

Specified by:

add in interface DataStructure<T>

Returns:

clear

public void clear()

Specified by:

clear in interface DataStructure<T>

contains

public boolean contains(java.lang.Object o)

Specified by:

contains in interface DataStructure<T>

estimateCount

public long estimateCount(T item)

The estimate is correct within 'epsilon' * (total item count), with probability 'confidence'.

getCapacity

public int getCapacity()

Specified by:

getCapacity in interface DataStructure<T>

getConfidence

public double getConfidence()

getDepth

protected int getDepth()

getFrequencyOf

public long getFrequencyOf(T e)

Specified by:

getFrequencyOf in interface DataStructure<T>

getRelativeError

public double getRelativeError()

getSize

public long getSize()

Specified by:

getSize in interface DataStructure<T>

getTable

protected long[][] getTable()

getType

public DataStructure.Type getType()

Specified by:

getType in interface DataStructure<T>

getWidth

protected int getWidth()

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface DataStructure<T>

setSize

public void setSize(long size)

size

public long size()