Ein Blog

Posts mit Tag "probabilistisch"

Postgres kann Indizes mit Bloom-Filter.

Use-Case:

In the case of an index access method, it allows fast exclusion of non-matching tuples via signatures whose size is determined at index creation. […] This type of index is most useful when a table has many attributes and queries test arbitrary combinations of them. A traditional btree index is faster than a bloom index, but it can require many btree indexes to support all possible queries where one needs only a single bloom index. Note however that bloom indexes only support equality queries, whereas btree indexes can also perform inequality and range searches.

Datenstrukturdienstag hatten wir schon lange nicht mehr. DafĂĽr mal etwas neueres: Der XOR-Filter (das Paper dazu).

Abstract:

The Bloom filter provides fast approximate set membership while using little memory. Engineers often use these filters to avoid slow operations such as disk or network accesses. As an alternative, a cuckoo filter may need less space than a Bloom filter and it is faster. Chazelle et al. proposed a generalization of the Bloom filter called the Bloomier filter. Dietzfelbinger and Pagh described a variation on the Bloomier filter that can be used effectively for approximate membership queries. It has never been tested empirically, to our knowledge. We review an efficient implementation of their approach, which we call the xor filter. We find that xor filters can be faster than Bloom and cuckoo filters while using less memory. We further show that a more compact version of xor filters (xor+) can use even less space than highly compact alternatives (e.g., Golomb-compressed sequences) while providing speeds competitive with Bloom filters.

Datenstrukturdienstag: Letzte Woche: Zählen, wie oft bestimmte Elemente vorkamen. Diese Woche: Zählen, wie viele Elemente in einer Menge enthalten sind.

Verwenden kann man dafĂĽr HyperLogLog (ja, wieder probabilistisch).

Anwendungsfall: Ihr habt eine Menge, zu der ständig neue Elemente hinzukommen. Ihr braucht euch nicht jedes Element merken. Aber es kann sein, dass ein Element, das eigentlich schon drin ist, noch mal hinzugefügt werden soll. Ihr wollt dieses Element nicht doppelt zählen (Fachbegriff Count-Distinct-Problem).

Konkret wollt ihr vielleicht die Anzahl der Aufrufe eines Videos zählen und nimmt dabei die ID des Users, der es angesehen hat, als Kriterium. Schaut sich die Person es noch mal an, wollt ihr sie nicht noch mal zählen. HLL hat dabei einen sehr langsam wachsenden Speicherbedarf (ursprünglich log(log(n)), daher der Name) und kann in O(1) Elemente hinzufügen.

In der Praxis muss man das natürlich nicht selber bauen. Redis hat das built-in[hinweis]. Und für jede Sprache gibt’s das sicherlich auch als Library.

HLL wird natürlich bei den “ganz großen” verwendet (Reddit hat hier berichtet, wie sie ihre Views zählten; habe gehört, dass sie es mittlerweile nicht mehr so machen). Diese Datenstruktur ist auch der Grund, warum Video-Views oder Upvote-Counts meistens nicht die genaue Zahl wiederspiegeln. HLL hat eine Fehlerrate von ~2%.

Es gibt von HLL noch weitere Abwandlungen, z. B. HLL++.

Datenstrukturdienstag: Dieses Mal gibt es wieder eine probabilistische Datenstruktur: Count–min-Sketch. Damit kann man (probabilistisch) schätzen, wie oft ein Element vorgekommen ist, z. B. wenn man einen Datenstrom hat und vorbeigehende Dinge zählt.

Datenstrukturdienstag: Letzte Woche gab’s den Bloom-Filter, diese Woche muss man dann wohl den Cuckoo-Filter erwähnen.

Großer Unterschied (IMHO): Man kann auch Einträge wieder löschen.

Datenstrukturdienstag: Eine meiner lieblings-Strukturen, der Bloom-Filter.

Eine wichtige Eigenschaft eines Bloom-Filters ist die False-Positive-Rate. Das ist die Wahrscheinlichkeit für False-Positives. Zu dieser Wahrscheinlichkeit gab es 30 Jahre später noch eine neue Formel, da die ursprüngliche wohl fehlerhaft war. Hier ist ein Writeup dazu[hinweis]. Hier ist noch ein Paper dazu.

Was man in der Praxis fĂĽr Probleme mit einem Bloom-Filter haben kann, hat Cloudflare mal aufgeschrieben.