Modernes Hashing:Platz- und zeiteffiziente Suchstrukturen und Simulation von Zufälligkeit mit dem Mehrfunktionen-Paradigma
Final Report Abstract
(1) Auf der Basis des Mehrfunktionenparadigmas können äußerst platzeffiziente Datenstrukturen zur Darstellung von Funktionen erstellt werden ("retrieval"). Die Konstruktion verwendet überraschende Verbindungen zum Verhalten von zufälligen dünn besetzten Matrizen. Solche Datenstrukturen wurden theoretisch konstruiert; ihr praktisches Verhalten wurde experimentell untersucht, wobei sich die Laufzeit für die Erstellung als Flaschenhals erweist. (2) Als Ergebnis einer längeren Entwicklung konnte ausgehend von den "retrieval"-Ergebnissen, i. W. gleichzeitig mit anderen Forschern in Deutschland und den USA und unabhängig von ihnen, eine der offenen Fragen über Schwellwerte ("thresholds") für das Funktionieren des Mehrfunktionenparadigmas bei der Verwendung von einer festen Anzahl von Hashfunktionen geklärt werden. Interessant ist der dabei verwendete Zusammenhang zwischen zufälligen XORSAT-Formeln und Hashing. (3) Mit dem "split-and-share"-Ansatz lassen sich viele Konstruktionen, die voraussetzen, dass rein zufällige Hashfunktionen (oder sogar Folgen von solchen Funktionen) gegeben sind, auf rein algorithmische Konstruktionen zurückführen. Dies wurde unter dem Stichwort "applications of a splitting trick" für einige komplexe Anwendungen wie approximative Wörterbücher oder Simulation von Zufälligkeit durchgeführt; der Ansatz ist auf alle in diesem Projekt untersuchten hashingbasierten Verfahren anwendbar, so dass hier grundsätzlich die Annahme der gegebenen vollen Zufälligkeit verzichtbar ist. (4) Als "Hash, displace, and compress" wurde eine Methode vorgestellt, die extrem platzeffiziente Konstruktionen für perfekte Hashfunktionen zulässt, also Funktionen, die eine gegebene Menge injektiv in einen kaum größeren Wertebereich abbilden und die in konstanter Zeit auswertbar sind. (5) Es wurde bewiesen, dass einfache universelle Hashklassen wie die universelle multiplikative Klasse und ähnliche Klassen schlecht mit Cuckoo-Hashing zusammen funktionieren, sogar mit hoher Wahrscheinlichkeit zum Crash der Anwendung führen können, selbst wenn die betrachteten Schlüsselmengen in einem gewissen Sinn zufällig sind. Dies widerspricht einer in anderen Konstruktionen wie Linearem Sondieren u. ä. beobachteten Erfahrungstatsache, dass nämlich schwache Klassen zusammen mit einigermaßen zufälligen Schlüsseln immer zu gutem Verhalten führen. (6) Den Gegenpol zu diesen negativen Ergebnissen bilden in der Ausführung nicht wesentlich teurere Hashklassen, die sogar für Cuckoo-Hashing mit "stash" geeignet sind. Diese Klassen haben viele weitere sehr interessante Eigenschaften; eine sehr lange Reihe von Konstruktionen für Zufallsgraphen und Zufallshypergraphen bleiben verwendbar, wenn man die rein zufälligen Kanten durch solche ersetzt, die mit Hilfe dieser Hashfunktionen generiert werden. (7) Von praktischer Relevanz sind die Untersuchungen zur Kombination von Cuckoo-Hashing, also dem Mehrfunktionenparadigma, und dem Speichern von Daten in Seiten. Es ergeben sich extrem platzeffiziente Datenstrukturen mit mittleren Zugriffskosten sehr wenig über einem "page fault". Insbesondere im Experiment erweist sich der Ansatz als äußerst robust. (8) Überraschende Antworten ergaben sich auf die Frage, ob es positive Effekte hat, wenn man bei der Anwendung des Mehrfunktionenparadigmas unterschiedliche Grade, d. h. Funktionenanzahl bei unterschiedlichen Schlüsseln zulässt. Für einige Anwendungen (Existenz perfekter Matchings) sollten die Grade möglichst gleich sein, für andere wieder (leicht konstruierbare Matchings) ist es von Vorteil, unterschiedliche Grade zu verwenden ("mixed hypergraphs"). (9) Basierend auf Erfahrungen mit hashingbasierten Graphstrukturen wurde wurde eine neue "greedy" Heuristik für das Auffinden von Matchings in Zufallsgraphen entwickelt, die eine bekannte Schwäche vergleichbarer Verfahren vermeidet. (10) In vielen Bereichen des Projektes wurden Methoden des "Algorithm Engineering" benutzt, um Algorithmen zu implementieren und in Iterationen über Experimente zu verbessern.
Publications
- Succinct data structures for retrieval and approximate membership (Extended Abstract). In: Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I. Lecture Notes in Computer Science,
Vol. 5125. 2008, pp. 385-396.
Martin Dietzfelbinger, Rasmus Pagh
(See online at https://dx.doi.org/10.1007/978-3-540-70575-8_32) - Applications of a splitting trick. In: Automata, Languages and Programming - 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I. Lecture Notes in Computer Science, Vol. 5555. 2009, pp. 354-365.
Martin Dietzfelbinger, Michael Rink
(See online at https://dx.doi.org/10.1007/978-3-642-02927-1_30) - Experimental variations of a theoretically good retrieval data structure. In: Algorithms - ESA 2009 - 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, Lecture Notes in Computer Science, Vol. 5757. 2009, pp. 742-751.
Martin Aumüller, Martin Dietzfelbinger, Michael Rink
(See online at https://dx.doi.org/10.1007/978-3-642-04128-0_66) - Hash, displace, and compress. In: Algorithms - ESA 2009 - 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, Lecture Notes in Computer Science, Vol. 5757. 2009, pp. 682-693.
Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger
(See online at https://dx.doi.org/10.1007/978-3-642-04128-0_61) - On risks of using cuckoo hashing with simple universal hash classes. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009, pp. 795-804.
Martin Dietzfelbinger, Ulf Schellbach
(See online at https://dx.doi.org/10.1137/1.9781611973068.87) - Perfect hashing for state spaces in BDD representation. In: KI 2009: Advances in Artificial Intelligence - 32nd Annual German Conf. on AI, Paderborn, Germany, Sept. 15-18, 2009. Proceedings, Springer, Lecture Notes in Computer Science, Vol. 5803. 2009, pp. 33-40.
Martin Dietzfelbinger, Stefan Edelkamp
(See online at https://dx.doi.org/10.1007/978-3-642-04617-9_5) - Weaknesses of cuckoo hashing with a simple universal hash class: The case of large universes. In: SOFSEM 2009: Theory and Practice of Computer Science: 35th Conf. on Current Trends in Theory and Practice of Computer Science, Špindlerův Mlýn, Czech Republic, January 24-30, 2009. Proceedings, Springer, Lecture Notes in Computer Science, Vol. 5404. 2009, pp. 217-228.
Martin Dietzfelbinger, Ulf Schellbach
(See online at https://dx.doi.org/10.1007/978-3-540-95891-8_22) - Tight thresholds for cuckoo hashing via XORSAT. In: Automata, Languages and Programming: 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I. Springer, Lecture Notes in Computer Science, Vol. 6198. 2010, pp. 213--225.
M. Dietzfelbinger, A. Goerdt, M. Mitzenmacher, A. Montanari, R. Pagh, M. Rink
(See online at https://dx.doi.org/10.1007/978-3-642-14165-2_19) - Cuckoo hashing with pages. In: Algorithms – ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings. Springer, Lecture Notes in Computer Science, Vol. 6942. 2011, pp. 615-627.
Martin Dietzfelbinger, Michael Mitzenmacher, Michael Rink
(See online at https://dx.doi.org/10.1007/978-3-642-23719-5_52) - A more reliable greedy heuristic for maximum matchings in sparse random graphs. In: Experimental Algorithms - 11th International Symposium, SEA 2012, Bordeaux, France, June 7-9, 2012. Proceedings. Springer. Lecture Notes in Computer Science, Vol. 7276. 2012, pp. 148-159.
Martin Dietzfelbinger, Hendrik Peilke, Michael Rink
(See online at https://dx.doi.org/10.1007/978-3-642-30850-5_14) - Towards optimal degree-distributions for left-perfect matchings in random bipartite graphs. Theory of Computing Systems, Vol. 56. 2015, Issue 4, pp 593–611. (= Lecture Notes in Computer Science, Vol. 7353. 2012, pp. 99-111)
Martin Dietzfelbinger, Michael Rink
(See online at https://dx.doi.org/10.1007/s00224-014-9577-1) - Mixed hypergraphs for linear-time construction of denser hashing-based data structures. In: SOFSEM 2013: Theory and Practice of Computer Science Proc. 39th SOFSEM, Springer, Lecture Notes in Computer Science, Vol. 7741. 2013, pp. 356-368.
Michael Rink
(See online at https://dx.doi.org/10.1007/978-3-642-35843-2_31) - Explicit and efficient hash families suffice for cuckoo hashing with a stash. Algorithmica, Vol. 70. 2014, Issue 3, pp 428–456.
(= Lecture Notes in Computer Science, Vol. 7501. 2012, pp 108-120)
Martin Aumüller, Martin Dietzfelbinger, Philipp Woelfel
(See online at https://doi.org/10.1007/s00453-013-9840-x)
