Optimal Piecewise Linear Approximation Model for KType keys.

Learns a mapping that returns a position for a KType key which is at most epsilon away from the correct one in a sorted list of keys. It is optimal and piecewise because it learns the minimum number of epsilon-approximate segments.

The PLA-model consists of a sequence segments. A segment s is a triple (key,slope,intercept) that indexes a range of keys through the function fs(k) = k × slope + intercept, which provides an epsilon-approximation of the position of the key k.

Nested and Inner Type Summary

Modifier and Type	Class and Description
private static class	PlaModel.Point Re-usable mutable (x,y) point.
private static class	PlaModel.PointList List of mutable `Point`.
public static interface	PlaModel.SegmentConsumer Consumer notified when a new segment is built by the `PlaModel`.
private static class	PlaModel.Slope Re-usable mutable (dx,dy) slope.

Field Summary

Modifier and Type	Field and Description
private int	epsilon Epsilon precision of the PLA-model.
private double	firstKey First key of the current segment.
private static final int	INITIAL_CAPACITY Initial capacity of the lower and upper point lists.
private final PlaModel.PointList	lower Ordered list of lower points for the current segment.
private int	lowerStart Index of the first lower point to compare to.
private int	numPointsInHull Number of points in the convex hull for the current segment.
private final PlaModel.Point	point1
private final PlaModel.Point	point2
private double	previousKey Previous key used to check that keys are added in strictly increasing sequence.
private final PlaModel.Point[]	rect Enclosing rectangle for the current segment.
private final PlaModel.Slope	slope1
private final PlaModel.Slope	slope2
private final PlaModel.Slope	slopeMax
private final PlaModel.Slope	slopeMin
private final PlaModel.Slope	slopeTmp
private final PlaModel.PointList	upper Ordered list of upper points for the current segment.
private int	upperStart Index of the first upper point to compare to.

Access	Constructor and Description
public	PlaModel(int must be greater than or equal to 0. epsilon) Creates an optimal PLA-model with the provided epsilon precision.

Method Summary

Modifier and Type	Method and Description
private int	addEpsilon(int index)
public void	addKey(double key, int The index of the key in the sorted key list. index, PlaModel.SegmentConsumer The consumer to call when a new segment is built in the PLA-model. segmentConsumer) Adds a key to this PLA-model.
private static double	cross(PlaModel.Point o, PlaModel.Point a, PlaModel.Point b)
public void	finish(PlaModel.SegmentConsumer segmentConsumer) Finishes the PLA-model construction.
private void	produceSegment(PlaModel.SegmentConsumer segmentConsumer)
public long	ramBytesAllocated() Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated. Allocated memory estimation
public long	ramBytesUsed() Implements com.carrotsearch.hppc.Accountable.ramBytesUsed. Bytes that is actually been used
private void	reset()
public void	setEpsilon(int epsilon) Sets epsilon precision which must be greater than or equal to 0.
private int	subtractEpsilon(int index)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

epsilon	back to summary
private int epsilon Epsilon precision of the PLA-model.

firstKey	back to summary
private double firstKey First key of the current segment.

INITIAL_CAPACITY	back to summary
private static final int INITIAL_CAPACITY Initial capacity of the lower and upper point lists.

lower	back to summary
private final PlaModel.PointList lower Ordered list of lower points for the current segment. Inside the list, allocated points are re-used.

lowerStart	back to summary
private int lowerStart Index of the first lower point to compare to.

numPointsInHull	back to summary
private int numPointsInHull Number of points in the convex hull for the current segment.

point1	back to summary
private final PlaModel.Point point1

point2	back to summary
private final PlaModel.Point point2

previousKey	back to summary
private double previousKey Previous key used to check that keys are added in strictly increasing sequence.

rect	back to summary
private final PlaModel.Point[] rect Enclosing rectangle for the current segment.

slope1	back to summary
private final PlaModel.Slope slope1

slope2	back to summary
private final PlaModel.Slope slope2

slopeMax	back to summary
private final PlaModel.Slope slopeMax

slopeMin	back to summary
private final PlaModel.Slope slopeMin

slopeTmp	back to summary
private final PlaModel.Slope slopeTmp

upper	back to summary
private final PlaModel.PointList upper Ordered list of upper points for the current segment. Inside the list, allocated points are re-used.

upperStart	back to summary
private int upperStart Index of the first upper point to compare to.

PlaModel	back to summary
public PlaModel(int epsilon) Creates an optimal PLA-model with the provided epsilon precision. Parameters epsilon:int must be greater than or equal to 0.

Method Detail

addEpsilon	back to summary
private int addEpsilon(int index)

addKey	back to summary
public void addKey(double key, int index, PlaModel.SegmentConsumer segmentConsumer) Adds a key to this PLA-model. The keys must be provided in a strictly increasing sequence. That is, the key must be greater than the previous key. Parameters index:int The index of the key in the sorted key list. segmentConsumer:PlaModel.SegmentConsumer The consumer to call when a new segment is built in the PLA-model.

addKey

back to summary

public void addKey(double key, int index, PlaModel.SegmentConsumer segmentConsumer)

Adds a key to this PLA-model. The keys must be provided in a strictly increasing sequence. That is, the key must be greater than the previous key.

Parameters

index:int: The index of the key in the sorted key list.
segmentConsumer:PlaModel.SegmentConsumer: The consumer to call when a new segment is built in the PLA-model.

cross	back to summary
private static double cross(PlaModel.Point o, PlaModel.Point a, PlaModel.Point b)

finish	back to summary
public void finish(PlaModel.SegmentConsumer segmentConsumer) Finishes the PLA-model construction. Declares that no additional keys will be added. Builds the last segment and calls the provided `SegmentConsumer`.

produceSegment	back to summary
private void produceSegment(PlaModel.SegmentConsumer segmentConsumer)

ramBytesAllocated	back to summary
public long ramBytesAllocated() Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated. Doc from com.carrotsearch.hppc.Accountable.ramBytesAllocated. Allocated memory estimation Returns:long Ram allocated in bytes Annotations @Override

ramBytesAllocated

back to summary

public long ramBytesAllocated()

Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Doc from com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Allocated memory estimation

Returns:long

Ram allocated in bytes

Annotations

@Override

ramBytesUsed	back to summary
public long ramBytesUsed() Implements com.carrotsearch.hppc.Accountable.ramBytesUsed. Doc from com.carrotsearch.hppc.Accountable.ramBytesUsed. Bytes that is actually been used Returns:long Ram used in bytes Annotations @Override

ramBytesUsed

back to summary

public long ramBytesUsed()

Implements com.carrotsearch.hppc.Accountable.ramBytesUsed.

Doc from com.carrotsearch.hppc.Accountable.ramBytesUsed.

Bytes that is actually been used

Returns:long

Ram used in bytes

Annotations

@Override

reset	back to summary
private void reset()

setEpsilon	back to summary
public void setEpsilon(int epsilon) Sets epsilon precision which must be greater than or equal to 0.

subtractEpsilon	back to summary
private int subtractEpsilon(int index)

com.carrotsearch.hppc back to summary

private Class PlaModel.Point

Class Inheritance

extends Object

java.lang.Object
com.carrotsearch.hppc.PlaModel.Point

Re-usable mutable (x,y) point.

Field Summary

Modifier and Type	Field and Description
pack-priv static final int	RAM_BYTES_ALLOCATED
pack-priv double	x
pack-priv long	y

Constructor Summary

Access	Constructor and Description
private	Point()

Method Summary

Modifier and Type	Method and Description
pack-priv PlaModel.Point	set(double x, long y)
pack-priv PlaModel.Point	set(PlaModel.Point p)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

RAM_BYTES_ALLOCATED	back to summary
pack-priv static final int RAM_BYTES_ALLOCATED

x	back to summary
pack-priv double x

y	back to summary
pack-priv long y

Constructor Detail

Point	back to summary
private Point()

Method Detail

set	back to summary
pack-priv PlaModel.Point set(double x, long y)

set	back to summary
pack-priv PlaModel.Point set(PlaModel.Point p)

com.carrotsearch.hppc back to summary

private Class PlaModel.PointList

Class Inheritance

extends Object
implements Accountable

java.lang.Object
com.carrotsearch.hppc.PlaModel.PointList

All Implemented Interfaces

com.carrotsearch.hppc.Accountable

List of mutable Point. Re-uses allocated points instead of creating new instances.

Field Summary

Modifier and Type	Field and Description
pack-priv int	numAllocated
pack-priv PlaModel.Point[]	points
pack-priv int	size

Constructor Summary

Access	Constructor and Description
pack-priv	PointList(int initialCapacity)

Method Summary

Modifier and Type	Method and Description
pack-priv void	add(PlaModel.Point point)
pack-priv void	clear()
pack-priv void	clearFrom(int end)
pack-priv PlaModel.Point	get(int index)
public long	ramBytesAllocated() Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated. Allocated memory estimation
public long	ramBytesUsed() Implements com.carrotsearch.hppc.Accountable.ramBytesUsed. Bytes that is actually been used
pack-priv int	size()

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

numAllocated	back to summary
pack-priv int numAllocated

points	back to summary
pack-priv PlaModel.Point[] points

size	back to summary
pack-priv int size

Constructor Detail

PointList	back to summary
pack-priv PointList(int initialCapacity)

Method Detail

add	back to summary
pack-priv void add(PlaModel.Point point)

clear	back to summary
pack-priv void clear()

clearFrom	back to summary
pack-priv void clearFrom(int end)

get	back to summary
pack-priv PlaModel.Point get(int index)

ramBytesAllocated

back to summary

public long ramBytesAllocated()

Implements com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Doc from com.carrotsearch.hppc.Accountable.ramBytesAllocated.

Allocated memory estimation

Returns:long

Ram allocated in bytes

Annotations

@Override

ramBytesUsed

back to summary

public long ramBytesUsed()

Implements com.carrotsearch.hppc.Accountable.ramBytesUsed.

Doc from com.carrotsearch.hppc.Accountable.ramBytesUsed.

Bytes that is actually been used

Returns:long

Ram used in bytes

Annotations

@Override

size	back to summary
pack-priv int size()

com.carrotsearch.hppc back to summary

public Interface PlaModel.SegmentConsumer

Known Direct Implementers: com.carrotsearch.hppc.IntPgmIndex.IntBuilder, com.carrotsearch.hppc.DoublePgmIndex.DoubleBuilder, com.carrotsearch.hppc.LongPgmIndex.LongBuilder, com.carrotsearch.hppc.FloatPgmIndex.FloatBuilder

Consumer notified when a new segment is built by the PlaModel.

Method Summary

Modifier and Type	Method and Description
public void	accept(double The first key of the segment. firstKey, double The segment slope. slope, long The segment intercept. intercept) Consumes a new segment.

Method Detail

back to summary

public void accept(double firstKey, double slope, long intercept)

Consumes a new segment. The segment is defined by the epsilon-approximation function fs(k) = k × slope + intercept.

Parameters

firstKey:double: The first key of the segment.
slope:double: The segment slope.
intercept:long: The segment intercept.

com.carrotsearch.hppc back to summary

private Class PlaModel.Slope

Class Inheritance

extends Object

java.lang.Object
com.carrotsearch.hppc.PlaModel.Slope

Re-usable mutable (dx,dy) slope.

Field Summary

Modifier and Type	Field and Description
pack-priv double	dx
pack-priv long	dy
pack-priv static final int	RAM_BYTES_ALLOCATED

Constructor Summary

Access	Constructor and Description
private	Slope()

Method Summary

Modifier and Type	Method and Description
pack-priv static double	asDouble(PlaModel.Point p1, PlaModel.Point p2)
pack-priv boolean	isEqual(PlaModel.Slope s)
pack-priv boolean	isGreaterThan(PlaModel.Slope s)
pack-priv boolean	isLessThan(PlaModel.Slope s)
pack-priv void	set(PlaModel.Slope s)
pack-priv PlaModel.Slope	set(PlaModel.Point p1, PlaModel.Point p2)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

dx	back to summary
pack-priv double dx

dy	back to summary
pack-priv long dy

RAM_BYTES_ALLOCATED	back to summary
pack-priv static final int RAM_BYTES_ALLOCATED

Constructor Detail

Slope	back to summary
private Slope()

Method Detail

asDouble	back to summary
pack-priv static double asDouble(PlaModel.Point p1, PlaModel.Point p2)

isEqual	back to summary
pack-priv boolean isEqual(PlaModel.Slope s)

isGreaterThan	back to summary
pack-priv boolean isGreaterThan(PlaModel.Slope s)

isLessThan	back to summary
pack-priv boolean isLessThan(PlaModel.Slope s)

set	back to summary
pack-priv void set(PlaModel.Slope s)

set	back to summary
pack-priv PlaModel.Slope set(PlaModel.Point p1, PlaModel.Point p2)

public Class PlaModel

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private Class PlaModel.Point

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private Class PlaModel.PointList

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

public Interface PlaModel.SegmentConsumer

Method Summary

Method Detail

private Class PlaModel.Slope

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail