Optimal Hashing in External Memory-猫眼课题宝

DOI：

10.4230/lipics.icalp.2018.39

发表时间：

2018-05

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Alex Conway;Martín Farach-Colton;Philip Shilane

哈希表是无处不在的字典数据结构。但是，标准哈希表实现并不能很好地转化为外部内存模型，因为它们不纳入插入的局部性。 Iacono和Patracsu建立了外部哈希表的更新/查询权衡曲线：在$ o（\ lambda/b）中执行插入的哈希表，$（\ lambda/b）$ amortized iOS需要$ \ omega（\ log_ \ log_ \ lambda n）其中$ n $是可以存储在数据结构中的项目数量，$ b $是内存传输的大小， $ m $是内存的大小，$ \ lambda $是调谐参数。他们提供了一个散布的数据结构，可满足$ \ lambda $的曲线，即$ \ omega（\ log \ log \ log \ log m + \ log_m n）$。他们称为\ defn {ip hash表}的数据结构很复杂，据我们所知，尚未实现。在本文中，我们提出了一个新的，更简单的最佳外部内存哈希表，\ defn {数组hash table}（boa）。 BOA基于尺寸级别的LSM，这是一个经过良好研究的数据结构，几乎同样容易实现。 BOA对于$ \ lambda $的窄范围非常最佳。但是，BOA的简单性使它们可以轻松地修改以实现以下结果：\ begin {initizize} \ item是一个新的外部内存数据结构，\ defn {bund of trees hash table}（bot），与性能匹配IP哈希表格的同时保留了BOA的一些简单性。 \ item \ defn {cache-oblivious bundle of树哈希表}（Cobot），第一个符合缓存的哈希表。此数据结构与$ \ lambda $相同的机器人和IP哈希表的最佳性匹配。 \ end {inatizize}

Hash tables are a ubiquitous class of dictionary data structures. However, standard hash table implementations do not translate well into the external memory model, because they do not incorporate locality for insertions. Iacono and Patracsu established an update/query tradeoff curve for external hash tables: a hash table that performs insertions in $O(\lambda/B)$ amortized IOs requires $\Omega(\log_\lambda N)$ expected IOs for queries, where $N$ is the number of items that can be stored in the data structure, $B$ is the size of a memory transfer, $M$ is the size of memory, and $\lambda$ is a tuning parameter. They provide a hashing data structure that meets this curve for $\lambda$ that is $\Omega(\log\log M + \log_M N)$. Their data structure, which we call an \defn{IP hash table}, is complicated and, to the best of our knowledge, has not been implemented. In this paper, we present a new and much simpler optimal external memory hash table, the \defn{Bundle of Arrays Hash Table} (BOA). BOAs are based on size-tiered LSMs, a well-studied data structure, and are almost as easy to implement. The BOA is optimal for a narrower range of $\lambda$. However, the simplicity of BOAs allows them to be readily modified to achieve the following results: \begin{itemize} \item A new external memory data structure, the \defn{Bundle of Trees Hash Table} (BOT), that matches the performance of the IP hash table, while retaining some of the simplicity of the BOAs. \item The \defn{cache-oblivious Bundle of Trees Hash Table} (COBOT), the first cache-oblivious hash table. This data structure matches the optimality of BOTs and IP hash tables over the same range of $\lambda$. \end{itemize}

Optimal Hashing in External Memory

文献摘要

被引文献

相似文献