Modernes Hashing:Platz- und zeiteffiziente Suchstrukturen und Simulation von Zufälligkeit mit dem Mehrfunktionen-Paradigma

现代哈希：空间和时间高效的搜索结构以及多功能范式的随机性模拟

• 批准号: 60576965
• 负责人: Professor Dr. Martin Dietzfelbinger
• 金额: --
• 依托单位: Fachgebiet Komplexitätstheorie und Effiziente Algorithmen
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2007
• 资助国家: 德国
• 起止时间: 2006-12-31 至 2013-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/60576965?language=en
• 关键词: Modernes; Hashing; Platz; und; zeiteffiziente

Das „ two-choice paradigm" oder „ balanced allocation paradigm" („Mehrfunktionen- Paradigma") ist in verschiedenen algorithmischen Zusammenhängen von grundlegender Bedeutung: Jedem Namen („Schlüssel") aus einem Namensbereich („Universum'') wird eine kleine Anzahl leicht zu berechnender zufälliger Indizes („Hashfunktions-Werte") in einem Indexbereich zugeordnet. Der Ansatz wird u.a. dazu benutzt, um mit geringem Speicherplatzbedarf und konstanter Zugriffszeit fundamentale Datenstrukturen („Wörterbuch", „Bloom-Filter", „Minimale Perfekte Hashfunktion") zu implementieren. Ziele des Forschungsvorhabens sind: (1) Die Analysemethoden sollen verfeinert und methodisch erweitert werden, um die Wirkungsweise des Mehrfunktionen-Paradigmas noch genauer zu verstehen und um zu möglichst optimal platzeffizienten Strukturen zu gelangen. (2) Für einige Anwendungen des Mehrfunktionen- Paradigmas wird idealisierend angenommen, dass zufällige Hashfunktionen kostenlos gegeben sind. Die Implikationen, Anwendungsmöglichkeiten und Grenzen eines neuen Ansatzes („split-and-share"), der diese Zufälligkeit algorithmisch bereitstellt, sollen theoretisch und experimentell untersucht werden. (3) Das Zusammenwirken von einfachen, effizient auswertbaren Hashfunktionen mit dem Mehrfunktionen- Paradigma soll im Detail untersucht werden.

如“两种选择范式”、“均衡分配范式”（“Mehrfunktionen- paradigm”）、ist in verschiedenenalgorithmischen Zusammenhängen von grundlegender Bedeutung: Jedem Namen（“schl<s:1> ssel”）、aueinem namenbereich（“Universum”）、eine kleine Anzahl leichzuberhnender zufälliger Indizes（“hashfunktionswerte”）in einem Indexbereich zugeordnet。Der Ansatz and a.a dazu benutzt, um mit geringem Speicherplatzbedarf and konstanter Zugriffszeit fundamentale datenstruckturen（“Wörterbuch”，“Bloom-Filter”，“Minimale Perfekte hashfunkfunction”）的实现。(1)模具分析方法、验证方法和方法，以及模具分析方法、模型分析方法、模型分析方法、模型分析方法、模型分析方法、模型分析方法和模型分析方法。(2) [j] [j] [j] [j] [j] [j] [j]。Die Implikationen, Anwendungsmöglichkeiten and Grenzen eines neuen Ansatzes（“分拆与分享”），der disese Zufälligkeit algorithmisch bereitstellt, sollen theory and experiment in untersucht werden。(3)基于数据分析的高效数据分析方法——基于细节分析的数据分析方法。

项目成果

Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash

• DOI: 10.1007/s00453-013-9840-x
• 发表时间: 2012-04
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Martin Aumüller;Martin Dietzfelbinger;Philipp Woelfel

Applications of a Splitting Trick

分裂技巧的应用

• DOI: 10.1007/978-3-642-02927-1_30
• 发表时间: 2009
• 作者: Martin Dietzfelbinger;Michael Rink
• 通讯作者: Michael Rink

Experimental Variations of a Theoretically Good Retrieval Data Structure

理论上良好的检索数据结构的实验变体

• DOI: 10.1007/978-3-642-04128-0_66
• 发表时间: 2009
• 作者: Martin Aumüller;Martin Dietzfelbinger;Michael Rink
• 通讯作者: Michael Rink

Cuckoo Hashing with Pages

布谷鸟哈希与页面

• DOI: 10.1007/978-3-642-23719-5_52
• 发表时间: 2011
• 期刊: ArXiv
• 作者: Martin Dietzfelbinger;Michael Mitzenmacher;Michael Rink
• 通讯作者: Michael Rink

Tight Thresholds for Cuckoo Hashing via XORSAT

• DOI: 10.1007/978-3-642-14165-2_19
• 发表时间: 2009-12
• 期刊: ArXiv
• 作者: Martin Dietzfelbinger;A. Goerdt;M. Mitzenmacher;A. Montanari;R. Pagh;Michael Rink