Part 2: Privacy-aware data structure - Introduction to HyperLogLog

Workshop: Social Media, Data Analysis, & Cartograpy, WS 2022/23

Alexander Dunkel, Madalina Gugulica, Institute of Cartography, TU Dresden

This is the second notebook in a series of four notebooks:

  1. Introduction to Social Media data, jupyter and python spatial visualizations
  2. Introduction to privacy issues with Social Media data and possible solutions for cartographers
  3. Specific visualization techniques example: TagMaps clustering
  4. Specific data analysis: Topic Classification

Open these notebooks through the file explorer on the left side.

Introduction: Privacy & Social Media

HLL in summary
  • HyperLogLog is used for estimation of the number of distinct items in a set (this is called cardinality estimation)
  • By providing only aproximate counts (with 3 to 5% inaccuracy), the overall data footprint and computing costs can be reduced significantly, providing benefits for both privacy and performance
  • A set with 1 Billion elements takes up only 1.5 kilobytes of memory
  • HyperLogLog Sets offer similar functionality as regular sets, such as:
    • lossless union
    • intersection
    • exclusion
Background about HLL Research
In recent years, user privacy has become an increasingly important consideration. Particularly when working with VGI and Social Media data, analysts need to compromise between flexibility of analyses and increasing vulnerability of collected (raw) data.

There exist many possible solutions to this problem. One approach is data minimization. In a paper, we have specifically looked at options to prevent collection of original data at all, in the context of spatial data, using a data abstraction format called HyperLogLog.

Dunkel, A., Löchner, M., & Burghardt, D. (2020).

Privacy-aware visualization of volunteered geographic information (VGI) to analyze spatial activity:
A benchmark implementation.
ISPRS International Journal of Geo-Information. DOI / PDF

Beyond privacy, HyperLogLog (HLL) is a modern and fast algorithm with many advantages, which is why it is used by (e.g.) Google, Facebook and Apple to make sense of increasing data collections.


  • Many different HLL implementations exist
  • There is a python library available
  • The library is quite slow in comparison to the Postgres HLL implementation
  • we're using python-hll for demonstration purposes herein
  • the website contains more examples that show how to use Postgres for HLL calculation in python.

Introduction to HLL sets

HyperLogLog Details
  • A HyperLogLog (HLL) Set is used for counting distinct elements in the set.
  • For HLL to work, it is necessary to first hash items
  • here, we are using MurmurHash3
  • the hash function guarantees a predictably distribution of characters in the string,
  • which is required for the probabilistic estimation of count of items

Lets first see the regular approach of creating a set in python
and counting the unique items in the set:

Regular set approach in python

In [2]:
user1 = 'foo'
user2 = 'bar'
# note the duplicate entries for user2
users = {user1, user2, user2, user2}
usercount = len(users)

HLL approach

In [3]:
from python_hll.hll import HLL
import mmh3

user1_hash = mmh3.hash(user1)
user2_hash = mmh3.hash(user2)

hll = HLL(11, 5) # log2m=11, regwidth=5


usercount = hll.cardinality()

log2m=11, regwidth=5 ? These values define some of the characteristics of the HLL set, which affect (e.g.) how accurate the HLL set will be. A default register width of 5 (regwidth = 5), with a log2m of 11 allows adding a maximum number of \begin{align}1.6x10^{12}= 1600000000000\end{align}

items to a single set (with a margin of cardinality error of ±2.30%)

HLL has two modes of operations that increase accuracy for small sets

  • Explicit
  • and Sparse

Repeat the process above with explicit mode turned off:

In [4]:
hll = HLL(11, 5, 0, 1) # log2m=11, regwidth=5, explicit=off, sparse=auto)

usercount = hll.cardinality()

Union of two sets

At any point, we can update a hll set with new items
(which is why HLL works well in streaming contexts):

In [5]:
user3 = 'baz'
user3_hash = mmh3.hash(user3)
usercount = hll.cardinality()

.. but separate HLL sets may be created independently,
to be only merged finally for cardinality estimation:

In [6]:
hll_params = (11, 5, 0, 1)

hll1 = HLL(*hll_params)
hll2 = HLL(*hll_params)
hll3 = HLL(*hll_params)


hll1.union(hll2) # modifies hll1 to contain the union

usercount = hll1.cardinality()

Counting Examples: 2-Components

What is counted entirely depends on the application context.

Typically, this will result in a 2-component setup with

  • the first component as a reference for the count context, e.g.:
    • coordinates, areas etc. (lat, lng)
    • terms
    • dates or times
    • groups/origins (e.g. different social networks)
  • the second component as the HLL set, for counting different metrics, e.g.
    • Post Count (PC)
    • User Count (UC)
    • User Days (PUC)

YFCC100M Example: Monitoring of Worldwide User Days

A User Day refers to a common metric used in visual analytics.

Each user is counted once per day.

This is commonly done by concatentation of a unique user identifier and the unique day of activity, e.g.:

userdays_set = set()
userday_sample = "96117893@N05" + "2012-04-14"
> 1

We have create an example processing pipeline for counting user days world wide, using the Flickr YFCC100M dataset, which contains about 50 Million georeferenced photos uploaded by Flickr users with a Creative Commons License.

The full processing pipeline can be viewed in a separate collection of notebooks.

In the following, we will use the HLL data to replicate these visuals.

We'll use python methods stored and loaded from modules.

Data collection granularity

There's a difference between collecting and visualizing data.

During data collection, information can be stored with a higher
information granularity, to allow some flexibility for
tuning visualizations.

In the YFCC100M Example, we "collect" data at a GeoHash granularity of 5
(about 3 km "snapping distance" for coordinates).

During data visualization, these coordinates and HLL sets are aggregated
further to a worldwide grid of 100x100 km bins.

Have a look at the data structure at data collection time.

In [7]:
from pathlib import Path

OUTPUT = Path.cwd() / "out"
TMP = Path.cwd() / "tmp"
In [8]:
%load_ext autoreload
%autoreload 2
In [9]:
import sys

module_path = str(Path.cwd().parents[0] / "py")
if module_path not in sys.path:
from modules import tools

Load the full benchmark dataset.

In [10]:
filename = "yfcc_latlng.csv"
yfcc_input_csv_path = TMP / filename
if not yfcc_input_csv_path.exists():
    sample_url = tools.get_sample_url()
    yfcc_csv_url = f'{sample_url}/download?path=%2F&files={filename}'
    tools.get_stream_file(url=yfcc_csv_url, path=yfcc_input_csv_path)

Load csv data to pandas dataframe.

In [11]:
import pandas as pd
dtypes = {'latitude': float, 'longitude': float}
df = pd.read_csv(
    yfcc_input_csv_path, dtype=dtypes, encoding='utf-8')
CPU times: user 293 ms, sys: 74.6 ms, total: 368 ms
Wall time: 563 ms

The dataset contains a total number of 451,949 distinct coordinates,
at a GeoHash precision of 5 (~2500 Meters snapping distance.)

In [12]:
latitude longitude date_hll
0 -89.978027 -142.756348 \x138b40c722
1 -89.978027 -85.847168 \x138b40c722
2 -89.978027 -83.518066 \x138b40c722
3 -89.978027 -50.910645 \x138b40c722
4 -89.978027 -49.855957 \x138b40c722

Calculate a single HLL cardinality (first row):

In [13]:
sample_hll_set = df.loc[0, "date_hll"]
In [14]:
from python_hll.util import NumberUtil
hex_string = sample_hll_set[2:]
hll = HLL.from_bytes(NumberUtil.from_hex(hex_string, 0, len(hex_string)))
In [15]:

The two components of the structure are highlighted below.

In [16]:
    base_cols=["latitude", "longitude"],
  latitude longitude date_hll
0 -89.978027 -142.756348 \x138b40c722
1 -89.978027 -85.847168 \x138b40c722
2 -89.978027 -83.518066 \x138b40c722
3 -89.978027 -50.910645 \x138b40c722
4 -89.978027 -49.855957 \x138b40c722

The color refers to the two components:

1 - The (spatial) context for HLL sets (called the 'base' in lbsn structure)
2 - The HLL set (called the 'overlay')

Data visualization granularity

  • there're many ways to visualize data
  • typically, visualizations will present
    information at a information granularity
    that is suited for the specific application
  • To aggregate information from HLL data,
    individual HLL sets need to be merged
    (a union operation)
  • For the YFCC100M Example, the process
    to union HLL sets is shown here
  • We're going to load and visualize this
    aggregate data below
In [17]:
from modules import yfcc
In [18]:
filename = "yfcc_all_est_benchmark.csv"
yfcc_benchmark_csv_path = TMP / filename
if not yfcc_benchmark_csv_path.exists():
    yfcc_csv_url = f'{sample_url}/download?path=%2F&files={filename}'
        url=yfcc_csv_url, path=yfcc_benchmark_csv_path)
In [19]:
grid = yfcc.grid_agg_fromcsv(
    columns=["xbin", "ybin", "userdays_hll"])
In [20]:
geometry userdays_hll
xbin ybin
-18040096 79952 POLYGON ((-18040096.000 79952.000, -17940096.0... \x138b400ae459a171e19bc2a242a841b322
-17640096 -2020048 POLYGON ((-17640096.000 -2020048.000, -1754009... \x138b4008220f4115a12a212ac131a432a1370141e247...
-17540096 -1720048 POLYGON ((-17540096.000 -1720048.000, -1744009... \x138b407221
-2020048 POLYGON ((-17540096.000 -2020048.000, -1744009... \x138b400661170230e138634b624c216d8174217fe38a...
-2120048 POLYGON ((-17540096.000 -2120048.000, -1744009... \x138b40c301
In [21]:
    geometry userdays_hll
xbin ybin    
-18040096 79952 POLYGON ((-18040096 79952, -17940096 79952, -17940096 -20048, -18040096 -20048, -18040096 79952)) \x138b400ae459a171e19bc2a
-17640096 -2020048 POLYGON ((-17640096 -2020048, -17540096 -2020048, -17540096 -2120048, -17640096 -2120048, -17640096 -2020048)) \x138b4008220f4115a12a212
-17540096 -1720048 POLYGON ((-17540096 -1720048, -17440096 -1720048, -17440096 -1820048, -17540096 -1820048, -17540096 -1720048)) \x138b407221
-2020048 POLYGON ((-17540096 -2020048, -17440096 -2020048, -17440096 -2120048, -17540096 -2120048, -17540096 -2020048)) \x138b400661170230e138634
-2120048 POLYGON ((-17540096 -2120048, -17440096 -2120048, -17440096 -2220048, -17540096 -2220048, -17540096 -2120048)) \x138b40c301

Calculate the cardinality for all bins and store in extra column:

In [22]:
def hll_from_byte(hll_set: str):
    """Return HLL set from binary representation"""
    hex_string = hll_set[2:]
    return HLL.from_bytes(
            hex_string, 0, len(hex_string)))
In [52]:
def cardinality_from_hll(hll_set, total, ix=[0]):
    """Turn binary hll into HLL set and return cardinality"""
    ix[0] += 1
    loaded = ix[0]
    hll = hll_from_byte(hll_set)
    if (loaded % 100 == 0):
            total, loaded)
    return hll.cardinality() - 1

Calculate cardinality for all bins.

In [57]:
mask = grid["userdays_hll"].notna()
grid["userdays_est"] = 0
total = len(grid[mask].index)
grid.loc[mask, 'userdays_est'] = grid[mask].apply(
        lambda x: cardinality_from_hll(
           x["userdays_hll"], total),
Processed 14000 of 12589 (111%)..
CPU times: user 4min 2s, sys: 324 ms, total: 4min 2s
Wall time: 4min 2s

From now on, disable warnings:

In [58]:
import warnings 

Have a look at the cardinality below.

In [59]:
geometry userdays_hll userdays_est
xbin ybin
-18040096 79952 POLYGON ((-18040096.000 79952.000, -17940096.0... \x138b400ae459a171e19bc2a242a841b322 7
-17640096 -2020048 POLYGON ((-17640096.000 -2020048.000, -1754009... \x138b4008220f4115a12a212ac131a432a1370141e247... 68
-17540096 -1720048 POLYGON ((-17540096.000 -1720048.000, -1744009... \x138b407221 1
-2020048 POLYGON ((-17540096.000 -2020048.000, -1744009... \x138b400661170230e138634b624c216d8174217fe38a... 11
-2120048 POLYGON ((-17540096.000 -2120048.000, -1744009... \x138b40c301 1

Visualize the grid, using prepared methods

Temporary fix to prevent proj-path warning:

In [60]:
import sys, os
os.environ["PROJ_LIB"] = str(Path(sys.executable).parents[1] / 'share' / 'proj')

Activate the bokeh holoviews extension.

In [61]:
from modules import grid as yfcc_grid
import holoviews as hv