Skip to content

HyperLogLog

In a conference paper, we have proposed a general conceptual frame for systematically improving privacy-awareness in various visual analytic questions (Löchner et al. 1). In this conceptual frame, using HyperLogLog, a cardinality estimation algorithm (Flajolet et al. 2), is proposed as a key to gradually mitigating privacy risks during various steps of the analytical process.

By solving the count distinct problem, HyperLogLog can be directly applied to key metrics used in LBSN visual analytics such as user count, post count, or user days. However, since HyperLogLog is not, per se, privacy preserving, it must be combined with other approaches and components (Desfontaines et al. 3).

In a subsequent full paper by Dunkel et al. 4, this is demonstrated in detail for one specific type of visualization: A grid based aggregation of typical metrics such as post count, user count or user days. The results can be replicated with several jupyter notebooks provided in supplementary materials.

In the Tutorial & User Guide section here, we demonstrate several additional examples how the LBSN Structure can be applied, and present and discuss several approaches to privacy-aware processing.

Note

This metric-section of the LBSN Structure is in a very early stage of development. Ideally, we hope that this section can be revised frequently to reflect a broader range of application contexts in the future.


  1. M Löchner, A Dunkel, and D Burghardt. Protecting privacy using hyperloglog to process data from location based social networks. Proceedings of the Legal Ethical factorS crowdSourced geOgraphic iNformation, 2019. 

  2. Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Hyperloglog: the analysis of a near-optimal cardinality estimation algorithm. In Discrete Mathematics and Theoretical Computer Science, 137–156. Discrete Mathematics and Theoretical Computer Science, 2007. 

  3. Damien Desfontaines, Andreas Lochbihler, and David A. Basin. Cardinality estimators do not preserve privacy. CoRR, 2018. URL: http://arxiv.org/abs/1808.05879, arXiv:1808.05879

  4. Alexander Dunkel, Marc Löchner, and Dirk Burghardt. Privacy-aware visualization of volunteered geographic information (vgi) to analyze spatial activity: a benchmark implementation. ISPRS International Journal of Geo-Information, 2020. doi:10.3390/ijgi9100607


Last update: April 14, 2021