Albert Weichselbraun

is a Professor of Information Science at the University of Applied of the Grisons.

Data sketching

less than 1 minute read

This article introduces three popular data structures that efficiently handle and summarize large data sets.

  1. Bloom filters are basically sets which answer the question of whether an item is part of the set (i.e. has been seen by the filter) with either (i) “the item is definitely not a part of the set”, or (ii) “the item might be part of the set.

  2. The Count-Min Sketch method is a probabilistic method for counting the number of times items of a certain type have been observed. When queried the structure returns an estimation which is considered an upper bound for the corresponding count.

  3. The HyperLogLog method counts the number of different items seen in a large set of individuals without keeping count of every single individual.

You may also enjoy

Suffix array

1 minute read

The suffix array is a memory-efficient alternative to the suffix tree which provides a sorted list of string indices indicating the string’s suffixes.