Skip to content

HyperLogLog data type

For the complete documentation index see: llms.txt

All documentation pages available in markdown.

The HyperLogLog bin data type gives you estimated counts of members in a large dataset for your application to form fast, reasonable approximations of members in the union or intersection between multiple HyperLogLog bins. HyperLogLog’s estimates are a balance between complete accuracy and efficient savings in space and speed in dealing with extremely large datasets.

Operations across HLL bin types are processed on the server side. Only results are returned to the client.

These operations have expression counterparts, which evaluate to a value instead of writing it. See HLL expressions for the set, and Operations and expressions for which to reach for.

In this discussion, the words “set” and “dataset” are used with the meaning from mathematical set theory, not the Aerospike concept of sets.

Set theory fundamental background

The HyperLogLog data returned to your application is based on some basic ideas from set theory. The article Probabilistic: Definition, Models, and Theory Explained gives some brief background information.

Union of sets

Union

Intersection of sets

Intersection

Business use cases

The HyperLogLog data type is useful for any problem where your underlying data cannot give you exact answers. Some business use cases include deriving probable answers for the following needs:

Bank fraud

Count the number of suspicious indicators related to an account and its transactions to determine in real-time the probability of fraud of an incoming transaction.

Ad campaign scope

Given the user segments an ad is targeting, what is the approximate number of people who will see the ad?

Online sales conversion rate

By comparing user cohorts and their interest in adjacent items, how many possible customers who log in to the website will finally end up purchasing something in the same user session? In multiple sessions?

HyperLogLog data and data modeling

As with all Aerospike data types, your own values define the underlying HyperLogLog data. You need to model your data on values that have some intrinsic relationship so that you can derive counts of membership in individual data sets or the union or intersection of multiple datasets. In colloquial words, you must “compare apples to apples but not apples to oranges”.

Continuing the example of user segmentation in online ad campaigns, you might have records representing user segments, each with a HyperLogLog bin to represent the membership in the segment. With the data returned by batch reading the bins of multiple segments, you can ask the server for the count of the members in an intersection of multiple segments. For example:

  • All the people who love basketball. This is one segment, represented in an HLL bin of one record.
  • All the people who like the Golden State Warriors, another segment.
  • All the people who also like hats as a fashion accessory.

The meaning of the HLL bins is specific to the use case of identifying users as parts of audience segments, and counting those segments and intersections and unions between them for ad campaigns.

As a baseline for comparison, you can compare between records with HyperLogLog bins representing the same kind of data set specific to your use case. At a minimum, you need to define two HyperLogLog data sets so that their relationships can be explored. The exact meaning of the data is up to you.

  • Continuing the example of bank fraud in the use cases described above, you have records that you are certain show fraud. With the data returned by HyperLogLog, your application can find the probability that other records match the pattern of the identified records.
  • Continuing the example of online sales conversion rate in the use cases described above, the following need to be defined:
    • Date/time of login to the website
    • Date/time of purchase

What the HyperLogLog data type returns to your application

The HyperLogLog returns the following information to your application:

  • The estimated size of a set.
  • The estimated cardinality of the union of multiple sets.
  • The estimated similarity of multiple sets.
  • The estimated cardinality of the intersection of multiple sets.
  • The estimated union of multiple sets. This estimate is returned as a HyperLogLog data type.

Calculating the size of the returned data

Because the HyperlogLog data type is for working with large data sets, the data it returns can also be large. You need to be aware of the storage cost of a HyperLogLog bin. For small sets a data type other than HyperLogLog might suffice, but for large data sets the unchanging storage size is extremely advantageous.

  • Each HLL contains 11 bytes of metadata and an array of 2n_index_bits registers.

  • Each register contains 6 bits of hll_val and n_minhash_bits bits of minhash_val. The size of the registers is rounded up to the nearest byte.

sizeof(HLL) = 11 + roundUpToByte(2n_index_bits × (6 + n_minhash_bits))

For general guidelines on bin overheads, see Linux Capacity Planning.

Error Bounds

OperationError typeError formulaNotes
refresh_count
get_count
get_union_count		Relative1.042n_index_bits\frac{1.04}{\sqrt{2^{n\_index\_bits}}}Increasing bits exponentially reduces
relative error. For example, 4 bits → 26%,
10 bits → 3.25%, 16 bits → 0.41%.
get_similarityAbsoluten_minhash_bits≥log⁡2(6e⋅t)n\_minhash\_bits \geq \log_2\left(\frac{6}{e \cdot t}\right)

n_index_bits≥log⁡2(e−2)n\_index\_bits \geq \log_2(e^{-2})		Select bits to meet target error e,
and tune parameters based on
desired accuracy and similarity
threshold.
get_intersect_countAbsolute or
Relative		12n_minhash_bits\frac{1}{\sqrt{2^{n\_minhash\_bits}}}Use enough minhash bits for
reliable intersections:
- Stable if n_minhash_bits > 0
- Unstable if n_minhash_bits = 0

Performance

SymbolDescription
CCost of memcpy (added to all modifies).
ENumber of entries passed to the operation.
KNumber of HLLs being operated on.
MNumber of minhash bits.
NNumber of index bits.
RCost of storage read (applies to any transaction - only once per transaction).
SSize of a HLL in bytes (M + 1) × 2N
WCost of writing to storage (applies to any modify transaction - only once per transaction).
OperationHyperLogLog (n_minhash_bits = 0)HyperMinHash (n_minhash_bits > 0)
initSS
addEE
set_unionK × SK × S
refresh_countSS
foldK × SK × S
get_countSS
get_unionK × SK × S
get_union_countK × SK × S
get_intersect_countK! × S
0 ≤ K ≤ 2		K × S + S
get_similarityK! × S
0 ≤ K ≤ 2		K × S + S
describe11

Operations

HyperLogLog relies on the following APIs the clients applications use:

NameValueDescription
create_only0x01Disallow updating an existing value of this bin.
update_only0x02Disallow creation of a new HLL bin.
no_fail0x04Allow a set of operations to proceed if an individual operation would fail due to a policy violation.
allow_fold0X08Allow the resulting set to be the minimum of provided n_index_bits. For intersect_counts and similarity, allow the usage of less precise HLL algorithms when n_minhash_bits of all participating sets do not match.

create_only is valid only on init, add, and set_union. refresh_count and fold accept no flags at all, so any flag sent with those two operations is an error.

Modify operations

add

create_only no_fail

Adds values to HLL set. If HLL bin does not exist, use n_index_bits to create HLL bin.

add(policy, bin_name, items, n_index_bits)

Adds values to HLL set. If HLL bin does not exist, use n_index_bits and n_minhash_bits to create HLL bin.

add_mh(policy, bin_name, items, n_index_bits, n_minhash_bits)

Adds values to HLL set. The HLL bin must already exist.

update(policy, bin_name, items)
Arguments
NameTypeDescription
policyHLL policy

HLL modify policy.

bin_namestring

Name of bin.

itemslist

Elements to add to the sketch.

n_index_bitsinteger

Number of index bits. Must be between 4 and 16 inclusive.

n_minhash_bitsinteger

Number of minhash bits. Must be between 4 and 51 inclusive.

Returns
integer
Expression form

hll_add, hll_add_mh, hll_update

Examples
Add members to an HLL

Add user IDs to an audience-segment HLL. If the bin does not yet exist it is created with 10 index bits. The return value is the estimated number of elements that caused the internal count to change (new unique members). Adding the same user ID again does not increase the count.

Code sample 
// visitors does not exist yet
import com.aerospike.client.sdk.HllConfig;


List<String> users = List.of("user-1001", "user-1002", "user-1003");


try (RecordStream rs = session.upsert(key)
    .bin("visitors").hllAdd(users, HllConfig.of(10))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    long added = rec.getLong("visitors");
    // added == 3
}
// visitors: user-1001, user-1002, user-1003, with 10 index bits

fold 

fold(bin_name, n_index_bits)
Description

Folds the HLL bin to the specified n_index_bits.

Fails if existing HLL has n_minhash_bits set to non-zero.

Arguments
NameTypeDescription
bin_namestring

Name of bin.

n_index_bitsinteger

Number of index bits. Must be between 4 and 16 inclusive.

Returns
none
Examples
Fold to fewer index bits

Reduce the precision of an HLL bin from its current index bit count down to a lower value. This shrinks storage at the cost of wider error bounds. Folding is useful when combining HLLs that were created with different index bit counts — fold the higher one down before calling set_union. Folding is irreversible and fails if the HLL has minhash bits set.

Code sample 
// visitors: user-1001, user-1002, user-1003, with 12 index bits


try (RecordStream rs = session.upsert(key)
    .bin("visitors").hllFold(8)
    .execute()) {
    Record rec = rs.next().recordOrThrow();
}
// visitors: user-1001, user-1002, user-1003, with 8 index bits

init

create_only update_only no_fail

Initializes or resets a standard HyperLogLog.

init(policy, bin_name, n_index_bits)

Initializes or resets a HyperLogLog with minhash information (see HyperMinHash) bits to improve accuracy of intersection and similarity estimates.

init(policy, bin_name, n_index_bits, n_minhash_bits)
Arguments
NameTypeDescription
policyHLL policy

HLL modify policy.

bin_namestring

Name of bin.

n_index_bitsinteger

Number of index bits. It must be between 4 and 16 inclusive.

n_minhash_bitsinteger

Number of minhash bits. It must be between 4 and 51 inclusive, and the sum of the index and minhash bits must not exceed 64.

Returns
none
Examples
Initialize an HLL bin

Create an HLL bin on a record that represents an ad-campaign audience segment. Use 10 index bits for roughly 3% relative error on cardinality estimates. After initialization the bin is empty (count 0) and ready to receive members via add.

Code sample 
// visitors does not exist yet
import com.aerospike.client.sdk.HllConfig;


try (RecordStream rs = session.upsert(key)
    .bin("visitors").hllInit(HllConfig.of(10))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
}
// visitors: an empty HLL with 10 index bits

refresh_count 

refresh_count(bin_name)
Description

Stores the current count estimate in the HLL bin and returns it. For relative error see Error Bounds.

Arguments
NameTypeDescription
bin_namestring

Name of bin.

Returns
integer
Examples
Refresh the stored count

refresh_count returns the current cardinality estimate, the same value get_count returns, and stores it in the HLL so later reads of the count do not recompute it.

Code sample 
// visitors: user-1001, user-1002, user-1003, with 10 index bits


try (RecordStream rs = session.upsert(key)
    .bin("visitors").hllRefreshCount()
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    long count = rec.getLong("visitors");
    // count == 3
}

set_union

create_only update_only no_fail allow_fold 
set_union(policy, bin_name, hll_list)
Description

Sets union of specified list of HLLs with HLL bin.

Arguments
NameTypeDescription
policyHLL policy

HLL modify policy.

bin_namestring

Name of bin.

hll_listlist

List of HLL objects.

Returns
none
Examples
Merge audience segments

Merge one or more external HLL values into a bin. A common pattern is to read the raw HLL bytes from another record (for example a different audience segment) and merge them into the current record’s HLL. After set_union the bin contains every member from all contributing HLLs, and get_count returns the estimated cardinality of the combined set.

Code sample 
// visitors on key: user-1001, user-1002, user-1003
// visitors on otherKey: user-1003, user-1004, user-1005


// Read the HLL from a second segment record
Value.HLLValue otherHll;
try (RecordStream rs = session.query(otherKey)
    .bin("visitors").get()
    .execute()) {
    otherHll = rs.next().recordOrThrow().getHLLValue("visitors");
}


// Merge it into the current record's HLL
try (RecordStream rs = session.upsert(key)
    .bin("visitors").hllSetUnion(List.of(otherHll))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
}
// visitors on key: user-1001 through user-1005

Read operations

describe 

describe(bin_name)
Description

List containing the HLL bin’s configured n_index_bits and n_minhash_bits.

Arguments
NameTypeDescription
bin_namestring

Name of bin.

Returns
list
Expression form

hll_describe

Examples
Inspect HLL configuration

Returns a two-element list: [n_index_bits, n_minhash_bits]. Use this to verify an HLL’s precision settings before performing operations like fold or set_union that require matching configurations.

Code sample 
// visitors: user-1001, user-1002, user-1003, with 10 index bits


try (RecordStream rs = session.query(key)
    .bin("visitors").hllDescribe()
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    List<?> desc = rec.getList("visitors");
    // desc == [10, 0]
}

get_count 

get_count(bin_name)
Description

Estimate of the number of unique entries in the HLL set. For relative error see Error Bounds.

Arguments
NameTypeDescription
bin_namestring

Name of bin.

Returns
integer
Expression form

hll_get_count

Examples
Estimate audience size

After adding user IDs with add, read the estimated cardinality. The relative error depends on n_index_bits — for example, 10 bits gives roughly 3.25% relative error. get_count always returns the current estimate, including right after an add; it does not need a refresh_count first.

Code sample 
// visitors: user-1001, user-1002, user-1003, with 10 index bits


try (RecordStream rs = session.query(key)
    .bin("visitors").hllGetCount()
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    long estimated = rec.getLong("visitors");
    // estimated == 3
}

get_intersect_count 

get_intersect_count(bin_name, hll_list)
Description

Estimate of the number of elements that would be contained by the intersection of these HLL objects and the HLL bin. For relative error see Error Bounds.

Arguments
NameTypeDescription
bin_namestring

Name of bin containing an HLL value.

hll_listlist

List of HLL objects. If HLL minhash bits are 0, maximum 2 objects in list, otherwise may be greater than 2.

Returns
integer
Expression form

hll_get_intersect_count

Examples
Estimate audience overlap

Given two audience-segment records — “basketball fans” and “Warriors fans” — estimate how many users appear in both. Read the raw HLL bytes from the second record and pass them to get_intersect_count on the first. The result is the estimated cardinality of the intersection. When n_minhash_bits is 0, the list may contain at most 2 HLL objects.

Code sample 
// visitors on basketballKey: user-1001, user-1002, user-1003
// visitors on warriorsKey: user-1003, user-1004, user-1005


// Read the Warriors-fans HLL
Value.HLLValue warriorsHll;
try (RecordStream rs = session.query(warriorsKey)
    .bin("visitors").get()
    .execute()) {
    warriorsHll = rs.next().recordOrThrow().getHLLValue("visitors");
}


// Estimate overlap with basketball-fans HLL
try (RecordStream rs = session.query(basketballKey)
    .bin("visitors").hllGetIntersectCount(List.of(warriorsHll))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    long overlap = rec.getLong("visitors");
    // overlap == 1
}

get_similarity 

get_similarity(bin_name, hll_list)
Description

Estimate of the similarity (or Jaccard Index) of these HLL objects and the HLL bin. For absolute error see Error Bounds.

Arguments
NameTypeDescription
bin_namestring

Name of bin containing an HLL value.

hll_listlist

List of HLL objects. If HLL minhash bits are 0, maximum 2 objects in the list, otherwise may be greater than 2.

Returns
float
Expression form

hll_get_similarity

Examples
Measure audience similarity

The Jaccard similarity index is |A ∩ B| / |A ∪ B|, ranging from 0 (disjoint) to 1 (identical). Use get_similarity to estimate how much two audience segments overlap relative to their combined size. Higher accuracy requires non-zero n_minhash_bits at initialization time — see Error Bounds.

Code sample 
// visitors on key: user-1001, user-1002, user-1003
// visitors on otherKey: user-1003, user-1004, user-1005


Value.HLLValue otherHll;
try (RecordStream rs = session.query(otherKey)
    .bin("visitors").get()
    .execute()) {
    otherHll = rs.next().recordOrThrow().getHLLValue("visitors");
}


try (RecordStream rs = session.query(key)
    .bin("visitors").hllGetSimilarity(List.of(otherHll))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    double similarity = rec.getDouble("visitors");
    // similarity == 0.2
}

get_union 

get_union(bin_name, hll_list)
Description

Returns an HLL object that is the union of all specified HLL objects in the hll_list list with the HLL bin.

Arguments
NameTypeDescription
bin_namestring

Name of bin.

hll_listlist

List of HLL objects.

Returns
HLL
Expression form

hll_get_union

Examples
Read-only union of audience segments

Unlike set_union, get_union does not modify the bin. It returns a new HLL value representing the union of the bin and the provided HLL list. The returned bytes can be used client-side — for example, passed to another record’s set_union, or used locally with get_union_count in the same operate call.

Code sample 
// visitors on key: user-1001, user-1002, user-1003
// visitors on otherKey: user-1003, user-1004, user-1005


Value.HLLValue otherHll;
try (RecordStream rs = session.query(otherKey)
    .bin("visitors").get()
    .execute()) {
    otherHll = rs.next().recordOrThrow().getHLLValue("visitors");
}


try (RecordStream rs = session.query(key)
    .bin("visitors").hllGetUnion(List.of(otherHll))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    Value.HLLValue unionHll = rec.getHLLValue("visitors");
    // unionHll: an HLL of user-1001 through user-1005
}

get_union_count 

get_union_count(bin_name, hll_list)
Description

Estimate of the number of elements that would be contained by the union of these HLL objects and the HLL bin. For relative error see Error Bounds.

Arguments
NameTypeDescription
bin_namestring

Name of bin.

hll_listlist

List of HLL objects.

Returns
integer
Expression form

hll_get_union_count

Examples
Estimate combined reach

Given two audience-segment HLLs — for example “basketball fans” and “hat enthusiasts” — estimate the total number of distinct users across both segments. This is the estimated cardinality of the union, useful for ad-campaign reach projections. The bin itself is not modified.

Code sample 
// visitors on key: user-1001, user-1002, user-1003
// visitors on otherKey: user-1003, user-1004, user-1005


Value.HLLValue otherHll;
try (RecordStream rs = session.query(otherKey)
    .bin("visitors").get()
    .execute()) {
    otherHll = rs.next().recordOrThrow().getHLLValue("visitors");
}


try (RecordStream rs = session.query(key)
    .bin("visitors").hllGetUnionCount(List.of(otherHll))
    .execute()) {
    Record rec = rs.next().recordOrThrow();
    long totalReach = rec.getLong("visitors");
    // totalReach == 5
}