User:Optimalsloth/sandbox

In computer science, static functions, also known as retrieval data structures, is a dictionary-like data type composed of a collection of (key, value) pairs that allows the following operations:

• Construction from a collection of (key, value) pairs
• Retrieve the value associated with the given key or anything if the key is not contained in the collection
• Update the value associated with a key (optional)

In contrast to a dictionary, static functions do not allow operations like lookup, insertion, deletion or iteration. Therefore, such a data structure does not need to store the keys at all and may use less space than would be needed for a simple list of the key value pairs. This makes them interesting in situations where the associated data is small (e.g. few bits) because we can save a lot by reducing the space used by keys.

Furthermore, compared to AMQ-filters (like the Bloom filter), a static function is not probabilistic and always gives a correct answer for contained keys.

As a simple example suppose $n$ names annotated with either male or female are given. A static function built from this database can reproduce the associated tag for all names contained in the original set and a random one for other names. The size of this static function can be made to be only $(1+\epsilon )n$ bits for a small $\epsilon$ which is obviously much less than any other pair based representation.

Examples

Trivialbeispiel: Liste (oder auch Hashtabelle) mit allen Keys und Values. Braucht viel Speicherplatz, weil die Keys mit abgespeichert werden müssen. Im Falle der Liste sind dann auch noch die Queries langsam. Generell hat eine Liste ja auch mehr Funktionen als wir brauchen -- Anfragen wie "Ist Key x in der Datenstruktur" interessieren uns gar nicht. Wir wollen nur auswerten und erlauben ja sogar, dass bei nicht-vorhandenen Keys Blödsinn zurückgegeben wird.

XOR-Based

(siehe "Ribbon filter: practically smaller than Bloom and Xor", Abschnitt 2). Kann auf verschiedene Arten konstruiert werden, zum Beispiel indem man lineare Gleichungssysteme löst. Das Paper beschreibt eine effiziente Möglichkeit, diese Gleichungssysteme aufzubauen und zu lösen, aber da würde ich vielleicht nur kurz die Idee (Werte im LGS hauptsächlich auf der Diagonalen) erwähnen und nicht das komplette Paper lesen/erklären. Ich persönlich finde das XOR-basierte retrieval den interessantesten Abschnitt.

Perfect Hash Functions

(Verlinken zum entsprechenden Wikipedia-Artikel). Man baut die PHF auf und speichert dann in einem Array an der Position vom Hash-Funktionswert die Daten. Mit einer Minimum Perfect Hash Function hat man dann (besonders bei großen abzurufenden Elementen) kaum Overhead. Es ist hier sogar möglich, die Values dynamisch zu ändern, aber die möglichen Keys sind weiterhin statisch.

Applications

Approximate membership

(ähnlich bloom filter) - Benutze das Element als Key und einen kurzen Hash als Value. Für einen Query muss man die static function auswerten und vergleichen, ob der Hash der gleiche ist. Die Länge des Hash steuert die false-positive-rate.

Perfect Hash Functions

Das wird jetzt ein bisschen rekursiv, weil es bei den Beispielen zur Konstruktion auch schon dran stand, aber man kann static functions dazu benutzen, PHF zu bauen. Stell dir zum Beispiel eine cuckoo hashtabelle vor, in die schon alle Elemente eingefügt sind. Jedes Element darf an 2 verschiedenen Positionen sitzen und an jeder Position darf nur ein Element sitzen. Um jetzt eine PHF dieser Elemente zu generieren, müssen wir uns pro Element nur noch speichern, welche seiner beiden Positionen es denn am Ende genommen hat. Also eine 1-bit static function.

See also

• Perfect hash function