Applications of a Splitting Trick
Applications of a Splitting Trick
复制标题
分裂技巧的应用
DOI：
10.1007/978-3-642-02927-1_30
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Michael Rink
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Michael Rink
我们研究了一种简单的方法在为一组键构建基于哈希的数据结构时规避“完全随机假设”的应用。一般的方法是通过拆分哈希函数将sin“拆分”为Si“碎片”。在一个碎片i上，使用一种生成完全随机性的方法或数据结构，该方法或数据结构使用的空间大于|Si|。在某些情况下，该数据结构可以在片段的构造之间“共享”，这将导致更紧密的整体空间界限。该方法是在布谷鸟哈希及其变体的背景下引入的，但它似乎具有更广泛的适用性。为了展示它的力量和一些微妙之处，我们研究了三种新的应用，改进了以前的结构：(i)全随机on的空间效率模拟（继Pagh和Pagh（2003/08）和Dietzfelbinger和Woelfel（2003）的工作）；（ii）按照西格尔（1989/2004）的风格构建高度独立的函数；（iii） Buhrman、Miltersen、Radhakrishnan和Venkatesh（2000/02）以及Pagh和Pagh（2002）研究的单探针方案。
We study applications of a simple method for circumventing the “full randomness assumption” when building a hashing-based data structure for a setSof keys. The general approach is to “split”Sinto “pieces”Si, by a splitting hash function. On a pieceSi, a method or data structure for generating full randomness is used that uses more space than |Si|. Under certain circumstances, this data structure can be “shared” among the constructions for the piecesSi, which leads to a tighter overall space bound. The method was introduced in the context of cuckoo hashing and its variants, but it seems to have wider applicability. To demonstrate its power and some subtleties, we study three new applications, improving previous constructions: (i) Space-efficient simulation of full randomness onS(following work by Pagh and Pagh (2003/08) and Dietzfelbinger and Woelfel (2003)); (ii) Construction of highly independent functions in the style of Siegel (1989/2004); (iii) One-probe schemes as in work by Buhrman, Miltersen, Radhakrishnan, and Venkatesh (2000/02) and Pagh and Pagh (2002).
登录
查看更多内容
单探针搜索
影响因子：
--
作者：
Anna Pagh;R. Pagh
通讯作者：
R. Pagh
DOI：
10.1007/3-540-45322-9
发表时间：
2001-12
期刊：
--
影响因子：
--
作者：
Juraj Hromkovic
通讯作者：
Juraj Hromkovic
使用提取器存储信息
DOI：
10.1016/s0020-0190(02)00206-5
发表时间：
2002
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
A. Ta
通讯作者：
A. Ta
具有简单哈希函数的几乎随机图
DOI：
10.1145/780542.780634
发表时间：
2003
期刊：
ACM Trans. Algorithms
影响因子：
--
作者：
Martin Dietzfelbinger;Philipp Woelfel
通讯作者：
Philipp Woelfel
通用类快速高性能哈希函数、时空权衡及其应用
DOI：
10.1109/sfcs.1989.63450
发表时间：
1989
期刊：
30th Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
A. Siegel
通讯作者：
A. Siegel