Zu Testzwecken bei der Einführung neuer Produkte stellte sich die Aufgabe, aus den produktiven Daten eines Netzbetreibers genau diejenigen heraus zu filtern, welche bestimmte Nummern enthalten. Sie bekommen also sagen wir 2.000 Telefonnummern und sollen jetzt etwa aus allen Datensätzen, die von der Hardware eines Netzbetreibers geliefert werden, genau diejenigen finden, in denen eine dieser Telefonnummern vorkommt. Dabei werden pro Tag mehrere Dutzend Millionen Datensätze geliefert.

Wie man aus Milliarden komplex kodierter Datensätze die wenigen relevanten effizient finden kann
Diese Datensätze sind binär kodiert, besitzen verschiedene Arten und Längen und enthalten Telefonnummern an verschiedenen Stellen. Eine vollständige Dekodierung jedes einzelnen Datensatzes zur Ermittlung der vorkommenden Telefonnummern und folgender Abgleich gegen die Liste wäre daher viel zu aufwendig gewesen.

Daher wurde ein zweistufiges Verfahren benutzt: es wurde zuerst entschieden, ob ein Datensatz überhaupt eine der fraglichen Nummern enthalten kann. Danach wurden die noch in Frage kommenden Datensätze dekodiert und untersucht. Dazu wurde eine Variante eines Bloom-Filters implementiert. Bloom-Filter sind eine probabilistische Datenstruktur, welche zu einer Menge von Werten und einer Anfrage entweder sagt "Kann in der Menge vorkommen" oder "Kommt definitiv nicht in der Menge vor".

Dies wurde kombiniert mit einer Modifikation des Horspool-Algorithmus, um die notwendigen Rechnungen für das Durchsuchen grosser Datenmengen zu optimieren. Dabei wurde ausgenutzt, dass Telefonnummern - und damit die zu suchenden Muster - eine maximale Länge haben.

Das Ergebnis ist eine Liste von Datensätzen, in denen eine der Telefonummern vorkommen kann. Diese Liste wurde exakt dekodiert und jeder Datensatz überprüft. Durch dieses Vorgehen wurde eine "quasi"-lineare Laufzeit - also eine Laufzeit unabhängig von der Anzahl der zu suchenden Telefonnummern - auf der Menge der zu durchsuchenden Daten erreicht und die Laufzeit im Vergleich zum "naiven" Vorgehen um einen Faktor 1.000 bis 10.000 reduziert.