Package org.roaringbitmap
Class FastAggregation
java.lang.Object
org.roaringbitmap.FastAggregation
Fast algorithms to aggregate many bitmaps.
-
Constructor Summary
ConstructorsModifierConstructorDescriptionprivate
Private constructor to prevent instantiation of utility class -
Method Summary
Modifier and TypeMethodDescriptionstatic RoaringBitmap
and
(long[] aggregationBuffer, RoaringBitmap... bitmaps) Compute the AND aggregate.static RoaringBitmap
and
(Iterator<? extends RoaringBitmap> bitmaps) Compute the AND aggregate.static RoaringBitmap
and
(RoaringBitmap... bitmaps) Compute the AND aggregate.static int
andCardinality
(RoaringBitmap... bitmaps) Compute cardinality of the AND aggregate.static RoaringBitmap
horizontal_or
(Iterator<? extends RoaringBitmap> bitmaps) Deprecated.static RoaringBitmap
horizontal_or
(List<? extends RoaringBitmap> bitmaps) Minimizes memory usage while computing the or aggregate on a moderate number of bitmaps.static RoaringBitmap
horizontal_or
(RoaringBitmap... bitmaps) Minimizes memory usage while computing the or aggregate on a moderate number of bitmaps.static RoaringBitmap
horizontal_xor
(RoaringBitmap... bitmaps) Minimizes memory usage while computing the xor aggregate on a moderate number of bitmaps.private static int
horizontalOrCardinality
(RoaringBitmap... bitmaps) static RoaringBitmap
naive_and
(Iterator<? extends RoaringBitmap> bitmaps) Compute overall AND between bitmaps two-by-two.static RoaringBitmap
naive_and
(RoaringBitmap... bitmaps) Compute overall AND between bitmaps two-by-two.static RoaringBitmap
naive_or
(Iterator<? extends RoaringBitmap> bitmaps) Compute overall OR between bitmaps two-by-two.static RoaringBitmap
naive_or
(RoaringBitmap... bitmaps) Compute overall OR between bitmaps two-by-two.static RoaringBitmap
naive_xor
(Iterator<? extends RoaringBitmap> bitmaps) Compute overall XOR between bitmaps two-by-two.static RoaringBitmap
naive_xor
(RoaringBitmap... bitmaps) Compute overall XOR between bitmaps two-by-two.static RoaringBitmap
or
(Iterator<? extends RoaringBitmap> bitmaps) Compute overall OR between bitmaps.static RoaringBitmap
or
(RoaringBitmap... bitmaps) Compute overall OR between bitmaps.static int
orCardinality
(RoaringBitmap... bitmaps) Compute cardinality of the OR aggregate.static RoaringBitmap
priorityqueue_or
(Iterator<? extends RoaringBitmap> bitmaps) Uses a priority queue to compute the or aggregate.static RoaringBitmap
priorityqueue_or
(RoaringBitmap... bitmaps) Uses a priority queue to compute the or aggregate.static RoaringBitmap
priorityqueue_xor
(RoaringBitmap... bitmaps) Uses a priority queue to compute the xor aggregate.static RoaringBitmap
workAndMemoryShyAnd
(long[] buffer, RoaringBitmap... bitmaps) Computes the intersection by first intersecting the keys, avoids materialising containers, limits memory usage.static RoaringBitmap
workShyAnd
(long[] buffer, RoaringBitmap... bitmaps) Computes the intersection by first intersecting the keys, avoids materialising containers.private static int
workShyAndCardinality
(RoaringBitmap... bitmaps) static RoaringBitmap
xor
(Iterator<? extends RoaringBitmap> bitmaps) Compute overall XOR between bitmaps.static RoaringBitmap
xor
(RoaringBitmap... bitmaps) Compute overall XOR between bitmaps.
-
Constructor Details
-
FastAggregation
private FastAggregation()Private constructor to prevent instantiation of utility class
-
-
Method Details
-
and
Compute the AND aggregate. In practice, calls {#link naive_and}- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
and
Compute the AND aggregate.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
and
Compute the AND aggregate.- Parameters:
aggregationBuffer
- a buffer for aggregationbitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
andCardinality
Compute cardinality of the AND aggregate.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated cardinality
-
orCardinality
Compute cardinality of the OR aggregate.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated cardinality
-
horizontal_or
Deprecated.Calls naive_or.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
horizontal_or
Minimizes memory usage while computing the or aggregate on a moderate number of bitmaps. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
- See Also:
-
horizontal_or
Minimizes memory usage while computing the or aggregate on a moderate number of bitmaps. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
- See Also:
-
horizontal_xor
Minimizes memory usage while computing the xor aggregate on a moderate number of bitmaps. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
- See Also:
-
naive_and
Compute overall AND between bitmaps two-by-two. Performance hint: if you have very large and tiny bitmaps, it may be beneficial performance-wise to put a tiny bitmap in first position. This function runs in linear time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
naive_and
Compute overall AND between bitmaps two-by-two. Performance hint: if you have very large and tiny bitmaps, it may be beneficial performance-wise to put a tiny bitmap in first position. This function runs in linear time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
workShyAnd
Computes the intersection by first intersecting the keys, avoids materialising containers.- Parameters:
buffer
- an 8KB bufferbitmaps
- the inputs- Returns:
- the intersection of the bitmaps
-
workShyAndCardinality
-
horizontalOrCardinality
-
workAndMemoryShyAnd
Computes the intersection by first intersecting the keys, avoids materialising containers, limits memory usage. You must provide a long[] array of length at least 1024, initialized with zeroes. We do not check whether the array is initialized with zeros: it is the caller's responsability. You should expect this function to be slower than workShyAnd and the reduction in memory usage might be small.- Parameters:
buffer
- should be a 1024-long arraybitmaps
- the inputs- Returns:
- the intersection of the bitmaps
-
naive_or
Compute overall OR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
naive_or
Compute overall OR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
naive_xor
Compute overall XOR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
naive_xor
Compute overall XOR between bitmaps two-by-two. This function runs in linear time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
or
Compute overall OR between bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
or
Compute overall OR between bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
priorityqueue_or
Uses a priority queue to compute the or aggregate. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
- See Also:
-
priorityqueue_or
Uses a priority queue to compute the or aggregate. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
- See Also:
-
priorityqueue_xor
Uses a priority queue to compute the xor aggregate. This function runs in linearithmic (O(n log n)) time with respect to the number of bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
- See Also:
-
xor
Compute overall XOR between bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-
xor
Compute overall XOR between bitmaps.- Parameters:
bitmaps
- input bitmaps- Returns:
- aggregated bitmap
-