学习索引结构的一些案例——Jeff Dean在SystemML会议上发布的论文(下)

摘要: 原文： https://www.arxiv-vanity.com/papers/1712.01208/ 视频：https://www.youtube.com/watch?v=PWv4ROEvqmk 本文是Google的Fellow，Jeff Dean，把机器学习应用到系统设计的论文，原文发布在SystemML会议上，我做了翻译。

上一篇请参见：学习索引结构的一些案例——Jeff Dean在SystemML会议上发布的论文(中)

4. 点索引

除了范围索引之外，点查找的Hash Map在DBMS中起着类似或更重要的作用。 从概念上讲，Hash Map使用Hash函数来确定性地将键映射到数组内的随机位置（参见图[9 ]，只有4位开销，但速度降低3-7倍。

图9：传统Hash图与学习Hash图

类似于B树，机器学习模型可能会提供解决方案。 例如，如果我们可以学习一个将每个键唯一映射到数组内的唯一位置的模型，我们可以避免冲突（参见图[9] （b））。 尽管将模型学习为散列函数的想法并不新鲜，但现有工作主要集中在学习更好的散列函数以将对象从较高维空间映射到较低维空间以进行相似性搜索（即类似的对象具有相似的散列- 值） [55,57,32 ] 。 据我们所知，怎么通过学习产生更有效的点索引结构的模型，还没有被探索过。 虽然第一眼看起来似乎不可能使用机器学习模型来加速Hash Map，但如果内存空间是一个重大问题，它实际上可能是一种选择。 正如我们的实验所显示的，传统技术想达到高利用率（每个记录的小开销浪费空间小于20％）非常难以实现，而且会导致显着的性能损失。 相比之下，学习模型能够根据数据分布实现更高的利用率。 此外，还有可能将模型卸载到GPU / TPU，这可能会减轻通过散列函数执行模型的额外成本。

4.1 Hash模型索引

令人惊讶的是，学习键(Key)的CDF分布是一种潜在的得到更好散列函数的办法。 然而，与范围索引相比，我们并不打算将记录紧凑或按严格排序顺序存储。 相反，我们可以通过Hash Map的目标大小M来缩放CDF，并使用h(K) = F(K) * M ，其中的Key K作为我们的Hash函数。 如果模型F完美地学习了CDF，则不存在冲突。 此外，学习得到Hash函数与实际的Hash Map实现不冲突，并且可以与链表或任何其他方法结合使用。

对于模型体系结构，我们可以再次利用上一节中的递归模型体系结构。 很明显，和以前一样，在索引大小和性能之间存在一个折衷，这受到模型架构和数据集的影响。

请注意，Hash模型索引的插入操作与正常Hash表的插入方式相同：使用h(k)对密钥进行Hash处理，并将项插入返回的位置。 如果该位置已被采用，则用普通Hash Map的实现确定如何处理冲突。 这意味着，只要插入数据的特征与现有数据类似，散列函数就会保持其效率。 但是，如果数据分布发生变化，则可能需要按照前面所述重新训练模型。 再次，这超出了本文的范围。

4.2 结果

图10：模型vs随机Hash Map

为了测试使用机器学习模型的Hash索引的可行性，我们徒手实现了基于链表的Hash Map; 记录(Value)直接存储在Hash表中，并且只有在冲突的情况下记录才会附加到链表。 没有冲突，最多只会发生一次缓存未命中。 只有在几个键(Key)映射到相同位置的情况下，可能会发生额外的缓存未命中。 我们选择该设计，因为它可以实现最佳查找性能。 例如，我们还测试了商业级密集Hash图,，使用桶策略和就地溢出（即，Hash Map被分成桶以最小化开销，并在桶满时使用就地溢出[ 2 ] ） 。 虽然使用这种技术可以实现更小的内存占用，但我们发现它比链表方式慢两倍。 此外，在8 ％或更多的内存利用率下，密集的Hash-map在性能上进一步降低。 当然，许多进一步的（正交）优化是可能的，并且我们绝不会声称这是Hash Map的最大内存或CPU高效实现。 相反，我们的目标是展示学习Hash函数的一般潜力。

作为本实验的基准，我们使用Hash Map实现和随机Hash函数，该函数只使用两次乘法，3次移位和3次异或，这比加密Hash函数快得多。 作为我们的模型散列函数，我们在第二阶段使用了与前一节中的100k模型相同的2阶段RMI模型，没有任何隐藏层。 我们没有尝试任何其他模型，因为我们特别关注快速查找速度。

我们使用了与前一节相同的三个int数据集，并且对于所有实验，我们改变了可用插槽的数量，从75 ％到125 ％数据数量。 也就是说， 75 ％的Hash表中的插槽比数据记录少25 ％ 。 强制槽数量小于数据数量，可减少Hash表中的空位，但会增加链接列表的长度。

结果如图[10] 的平均查找时间，空槽数量（GB单位）以及可用槽位总数的百分比和空间j节约的改进。 请注意，与上一节相比，我们确实包含了数据大小 。 主要原因是，为了启用1次缓存未命中查找，数据本身必须包含在Hash Map中，而在上一节中，我们只计算了除排序数组本身之外的额外索引开销。

从图中可以看出，模型Hash函数的索引总体上具有相似的性能，同时更好地利用内存。 例如，如果有100 ％的插槽数（即Hash表中的插槽数与数据大小相匹配），随机Hash总会经历大约35 ％的冲突（理论值为33.3 ％）并浪费1.5G B的主存，而学习索引的散列函数更好地分散了密钥空间，因此能够将未使用的内存空间减少到高达80 ％ ，具体取决于数据集。

显然，当我们增加Hash表的大小以增加25 ％的插槽时，节省量不会很大，因为Hash表也可以更好地分散键(Key)。 令人惊讶的是，如果我们将空间减少到键的数量的75 ％ ，由于仍然起作用的生日悖论，学习的Hash图仍然具有优势。 我们也做过更小尺寸的实验，观察到大约50 ％的大小插槽数在随机和学习Hash函数之间没有明显差异。 但是，将Hash Map大小减少为仅包含数据大小的一半时隙，链表变长，查找时间也会变长。

4.3 替代方法和未来工作

除了使用CDF作为更好的散列函数外，还可以开发其他类型的模型。 虽然不在本文的范围内，但我们在某种程度上探讨了共同优化数据放置和查找数据的功能。 然而，在许多情况下，事实证明，混合模型专家模式们对于许多数据集的表现最好。

此外，也可以像混合索引一样将Hash-map与模型更紧密地结合起来。 也就是说，我们可以学习模型的几个阶段，并用简单的随机Hash函数替换性能较差的模型（即那些产生比随机Hash更多冲突的模型）。 这样，最坏的情况下的性能将与随机Hash相似。 但是，如果数据具有可以学习的模式，则可以实现更高的内存利用率。

5. 存在索引

图11： Bloom filter作为分类问题

DBMS的最后一种通用索引类型是存在索引，最重要的是Bloom-Filters，它是一种空间高效的概率数据结构，用于测试某个元素是否为集合的成员。 它们通常用于确定低温存储中是否存在键(Key)。 例如，BigTable使用它们来确定一个密钥是否包含在SSTable [ 18 ]中 。

在内部，Bloom filter使用大小为m的位数组和k个哈希函数，每个函数将一个关键字映射到m个数组位置中的一个（参见图[12]。

虽然Bloom filter非常节省空间，但它们仍可占用大量内存。 例如，想达到具有0.1 ％的假阳性率（FPR）的100M记录，需要比记录大约多14 倍的位。 因此，对于十亿个记录，大约需要大约1.76 Gigabyte个字节(十亿 = $$10^9$$ bit ， 位数 = $$14 * 10^9$$ bit ≈ 1.76GB Byte )。 对于0.01 ％的FPR，我们需要≈2.23 Gigabyte。 有几次尝试来提高Bloom filters的效率[ 43 ] ，但一般的开销依然存在。

然而，如果存在一些结构特性来确定什么是内部或外部的，用于学习，那么就可以构建更有效的表示。 有趣的是，对于数据库系统的存在索引，延迟和空间要求通常与我们之前看到的两种完全不同。 考虑到访问低温存储（例如磁盘甚至磁带）的高延迟，我们可以承担更复杂的模型，而主要目标是最小化索引的空间和误报的数量。

下面我们概述使用学习模型建立生存指数的两种潜在方法。

图12：具有学习散列函数的Bloom filter

5.1 学习索引版Bloom filter

虽然范围和点索引都知道键的分布，但存在索引需要学习将键和其他所有内容分开的函数。 换言之，针对点索引的良好hash函数是密钥间几乎没有碰撞的散列函数，而Bloom filter的良好hash函数将是键(Key)间有很多冲突同时 非键(Non-Key)间也发生大量冲突的良好散列函数，但很少有键(Key)和非键(Non-Key)之间的冲突。 我们在下面考虑如何学习这样一个函数f以及如何将它合并到一个存在索引中。

传统上，存在指标不会猜测键(Key)的分布，也不会猜测键(Key)与非键(Non-Key)有什么不同。 例如，如果我们的数据库包含0≤x<n的所有整数x ，则可以通过计算f(x) ≡1 [0≤x<n]来在恒定时间内计算存在索引，并且几乎没有存储器占用空间。 在考虑用于训练ML(Machine Learning)目的的数据分布时，我们必须考虑非键(Non-Key)的数据集 - 这可以是随机生成的键(Key)，基于先前对存在索引的查询日志，或者由机器学习模型生成[ 26]。 虽然Bloom filter保证任何一组查询的假阳性率（FPR）为一个特定值和假阴性率（FNR）为零，我们也遵循这样的概念，即我们希望为具体的实际查询提供特定的FPR，并保持FNR为0。

5.1.1 Bloom filters作为分类问题

构建存在索引的另一种方法是作为二元分类任务。 也就是说，我们想要学习一个模型f，它可以预测一个查询x是一个键(Key)还是非键(Non-Key)。 为此，我们用这样的数据$$D = { (x_i,y_i = 1) | x_i ∈ K } ∪ {(x_i,yi) = 0)|x_i ∈ U}$$， 来训练一个神经网络。 由于这是一个二元分类任务，我们的神经网络使用 sigmoid 激活函数来产生一个概率，并通过训练以最小化对数损失，

如前所述，可以选择f来匹配被索引的数据类型。 我们通常考虑递归神经网络（RNN）或卷积神经网络（CNN），因为它们已被反复证明是有效的字符串建模方式[ 54,29 ] 。

给定一个训练好的模型f ，我们如何使它成为一个有效率的存在索引？f (x) 的输出可以解释为x是我们数据库中的一个键的概率; 我们必须选择一个阈值τ，高于此阈值我们将假定键(Key)存在于我们的数据库中。 由于Bloom filter通常针对特定的FPR进行调整，因此我们可以将τ放在为在索引的查询数据集内，来动态实现所需的FPR。 与Bloom filter不同，我们的模型可能同时具有非零FPR和FNR; 事实上，随着FPR的下降，FNR将会上升。 为了保持存在索引不存在假阴性的约束，我们创建了一个溢出Bloom filter。 也就是说，我们考虑$K^- _τ= { x∈K | f (x)< τ }$是f的假阴性集合，并为这个键子集创建一个Bloom filters。 然后我们可以运行我们的存在索引，如图[11]存在; 否则，检查溢出Bloom filter。

这种设置是有效的，因为学习模型相对于数据的大小可以相当小。 此外，由于Bloom filter随着键(Key)集合的大小线性缩放，溢出Bloom filter将按照FNR进行缩放。 也就是说，即使我们的假阴性率为50％，我们也会将 Bloom filter的大小减半 （不包括模型大小）。 我们将通过实验发现，这种组合在降低存在索引的内存占用方面是有效的。 最后，学习模型计算可以受益于像GPU和TPU这样的机器学习加速器，而传统的Bloom filter往往严重依赖于存储器系统的随机访问延迟。

图13：了解的Bloom filter可以在大范围的误报率下改善内存占用。 （这里W是RNN宽度， E是每个角色的嵌入尺寸。）

5.1.2 带Hash模型的Bloom filter

在分类问题的初始化设置中，我们选择一个阈值τ并且接受f (x) ≥τ的预测将具有非零FPR，并且具有f (x)<τ的预测将具有非零FNR。 这与Bloom filter中Hash函数的典型观点相矛盾，因为没有槽时应该具有非零的FNR。 我们可以使用f作为这种散列函数，通过使用它来映射到大小为m的位数组。因为如上所述， f将查询映射到范围[0,1] ，所以我们可以假设函数d对该空间进行离散化。 例如，我们可以通过$d(p) = \lfloor mp\rfloor$来最简单地定义d 。 因此，我们可以使用d(f(x))作为散列函数，就像Bloom filter中的其他函数一样。 这具有以下优点： f被训练成将大部分键(Key)映射到比特位置的较高范围以及将非键(Non-Key)映射到较低范围的比特位置。

5.2结果

为了通过实验测试这个想法，我们探索了存在索引在追踪黑名单钓 鱼网址方面的应用。 我们将Google透明度报告中的数据视为我们密切关注的一组键(Key)。 该数据集由1.7M个唯一的URL组成。 我们使用的阴性(也就是不在数据集里面的）网址，其中包含随机（有效）网址和列入白名单的网址，这些网址可能会被误认为是钓 鱼网页。 我们训练一个character-level的RNN（特别是GRU [ 19 ] ）来预测URL属于哪一组。

具有期望1％FPR的常规Bloom filter需要2.04MB。 我们考虑一个16维GRU，每个角色(character)都有32维嵌入; 这个模型的大小是0.0259MB。 我们发现，如果我们想强制执行1％的FPR，TNR是49％。 如上所述，我们的Bloom filter的大小与FNR(51％)一致。 因此，我们发现我们的模型+溢出Bloom filter使用了1.07MB，大小减少了47％。 如果我们想强制执行0.1％的FPR，我们的FNR为71％，这使Bloom Filter的总大小从3.06MB降至2.2MB，减少了28％的内存。 我们观察图[13中的]这种一般关系。 有趣的是，我们看到不同的尺寸模型如何在不同的精度和内存之间取得平衡。

显然，我们的模型越精确，Bloom filter尺寸的节省就越好。 其中一个有趣的特性是我们的模型没有理由需要使用与Bloom filter相同的功能。 例如，已经有重要的研究在使用ML来预测一个网页是否是一个钓 鱼页面[ 10,13 ] 。 其他功能，如WHOIS数据或IP信息可以纳入模型，提高准确性，减少Bloom filter的大小，并保持没有误报的属性。

6. 相关工作

学习索引的思想建立在机器学习和索引技术的广泛研究之上。 以下，我们重点介绍最重要的相关领域。

B树和变体：在过去的几十年中，已经提出了各种不同的索引结构[ 28 ] 。

然而，所有这些方法都与学习索引的思想是正交的，因为他们都没有从数据的分布中学习，以实现更紧凑的指数表示或性能收益。 与此同时，正如我们的混合索引，可以将现有的硬件觉察索引策略与学习模型更紧密地结合起来，以获得进一步的性能提升。

由于B +树消耗大量内存，所以在压缩索引方面也有很多工作，如前缀/后缀截断，字典压缩，键(Key)规范化[ 28,25,45] ）。 有趣的是，一些现有的压缩技术与我们的方法相辅相成，可以帮助进一步提高效率。 例如，字典压缩可以看作是一种嵌入形式（即将一个字符串表示为一个唯一的整数）。

可能与本文最相关的是A-树 [ 24 ]提出在B树页面内使用插值搜索。 然而，学习索引更进一步，并建议使用学习模型替换整个索引结构。

最后，像Hippo [ 60 ]这样的稀疏索引都存储有关值范围的信息，但又不利用数据分布的基础属性。

更好的Hash函数：类似于基于树的索引结构的工作，在散列图和散列函数方面有很多工作[ 40,57,56,48]明确映射到哈希映射内的有限插糟集合的目标。

Bloom-Filters：最后，我们的存在索引直接建立在Bloom-Filters的现有工作上[ 22,11 ] 。 然后，我们的工作通过提出一个bloom-filter增强分类模型或者使用模型作为特殊的散列函数，来对问题采取不同的观察方式，这里的优化目标与我们为Hash Map创建的散列模型完全不同。

简洁数据结构：在学习索引和简洁数据结构之间存在着一个有趣的联系，特别是诸如小波树的排序选择字典[ 31,30 ] 。 然而，许多简洁的数据结构集中于H0熵（即，对索引中的每个元素进行编码所需的位数），而学习的索引尝试学习基础数据分布以预测每个元素的位置。 因此，学习的索引可能实现更高的压缩率，因为H0熵可能以较慢的操作为代价。 此外，对于每个用例，通常都必须仔细构造简洁的数据结构，而学习的索引通过机器学习“自动化”这一过程。 然而，简洁数据结构可能为进一步研究学习指标提供了一个框架。

CDF建模：我们的范围和点索引模型都与累积分布函数（CDF）的模型密切相关。 CDF计算是个非平庸的问题，并且已经在机器学习社区[ 41 ] 。 然而，大多数研究集中在对概率分布函数（PDF）进行建模，留下许多关于如何有效建模CDF的开放式问题。

专家混合体：我们的RM-I体系结构跟随了一系列有关为数据子集建立专家的研究[ 42 ] 。 正如我们在我们的配置中看到的那样，它很好地让我们能够解耦模型大小和模型计算，从而实现更复杂的模型，让这些模型的执行起来没那么昂贵。

7 结论和未来工作

我们表明，学习索引可以通过利用索引数据的分布特性来提供明显的好处。 这为许多有趣的研究问题打开了大门。

多维索引：可以说，学习索引理念最令人兴奋的研究方向是将其扩展到多维索引结构。 模型，特别是神经网络，非常擅长捕捉复杂的高维关系。理想情况下，这个模型能够估计任何属性组合过滤的所有记录的位置。

超越索引：学习算法也许令人惊讶的是，CDF模型也有加速排序和join的潜力，而不仅仅是索引。 例如，加速排序的基本思想是使用现有的CDF模型F将记录大致按排序顺序排列，然后修正几乎完美排序的数据，例如使用插入排序。

GPU / TPU 最后，正如在本文中多次提到的那样，GPU / TPU将使学习索引的思想更加可行。 同时，GPU / TPU也有其最大的挑战，最重要的是高调用延迟。 虽然可以合理地假设，由于前面所示的异常压缩比，所有已学习的索引可能适用于GPU / TPU，但仍需要2-3微秒才能对其进行任何操作。 同时，机器学习加速器与CPU的集成越来越好[ 6,4 ]，并且使用批处理请求等技术可以分摊调用成本，因此我们不相信调用延迟是一个真正的障碍。

总之，我们已经证明，机器学习模型有可能比最先进的数据库索引提供显着的优势，并且我们相信这个方向将在未来结出美妙研究成果。

参考文章

1. Google’s sparsehash. https://github.com/sparsehash/sparsehash-c11.

2. Google’s sparsehash documentation. https://github.com/sparsehash/sparsehash/blob/master/src/sparsehash/sparse_hash_map.

3. An in-depth look at googles first tensor processing unit (tpu). https://cloud.google.com/blog/big-data/2017/05/an-in-depth-look-at-googles-first-tensor-proc essing-unit-tpu.

4. Intel Xeon Phi. https://www.intel.com/content/www/us/en/products/processors/xeon-phi/xeon-phi-processors.html.

5. Moore Law is Dead but GPU will get 1000X faster by 2025. https://www.nextbigfuture.com/2017/06/moore-law-is-dead-but-gpu-will-get-1000x-faster-by-2025.html.

6. NVIDIA NVLink High-Speed Interconnect. http://www.nvidia.com/object/nvlink.html.

7. NVIDIA TESLA V100. https://www.nvidia.com/en-us/data-center/tesla-v100/.

8. Trying to speed up binary search. http://databasearchitects.blogspot.com/2015/09/trying-to-speed-up-binary-search.html.

9. M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M.Isard, et al. Tensorflow: A system for large-scale machine learning. In OSDI, volume 16, pages 265–283, 2016.

10. S. Abu-Nimeh, D. Nappa, X. Wang, and S. Nair. A comparison of machine learning techniques for phishing detection. In Proceedings of the anti-phishing working groups 2nd annual eCrime researchers summit, pages 60–69. ACM, 2007.

11. K. Alexiou, D. Kossmann, and P.-A. Larson. Adaptive range filters for cold data: Avoiding trips to siberia. Proc. VLDB Endow., 6(14):1714–1725, Sept. 2013.

12. M. Athanassoulis and A. A i l a m a k i. BF-tree: Approximate Tree Indexing. In VLDB, pages 1881–1892, 2014.

13. R. B. Basnet, S. Mukkamala, and A. H. Sung. Detection of phishing attacks: A machine learning approach. Soft Computing Applications in Industry, 226:373–383, 2008.

14. R. Bayer. Symmetric binary b-trees: Data structure and maintenance algorithms. Acta Inf., 1(4):290–306, Dec. 1972.

15. R. Bayer and E. McCreight. Organization and maintenance of large ordered indices. In Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control, SIGFIDET ’70, pages 107–141, New York, NY, USA, 1970. ACM.

16. M. Böhm, B. Schlegel, P. B. Volk, U. Fischer, D. Habich, and W. Lehner. Efficient in-memory indexing with generalized prefix trees. In Datenbanksysteme für Business, Technologie und Web (BTW), 14. Fachtagung des GI-Fachbereichs ”Datenbanken und Informationssysteme” (DBIS), 2.-4.3.2011 in Kaiserslautern, Germany, pages 227–246, 2011.

17. J. Boyar and K. S. Larsen. Efficient rebalancing of chromatic search trees. Journal of Computer and System Sciences, 49(3):667 – 682, 1994. 30th IEEE Conference on Foundations of Computer Science.

18. F. Chang, J. Dean, S. Ghemawat, W. C. Hsieh, D. A. Wallach, M. Burrows, T. Chandra, A. Fikes, and R. Gruber. Bigtable: A distributed storage system for structured data (awarded best paper!). In 7th Symposium on Operating Systems Design and Implementation (OSDI ’06), November 6-8, Seattle, WA, USA, pages 205–218, 2006.

19. K. Cho, B. van Merrienboer, Ç. Gülçehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Special Interest Group of the ACL, pages 1724–1734, 2014.

20. J. G. Cleary. Compact hash tables using bidirectional linear probing. IEEE Trans. Computers, 33(9):828–834, 1984.

21. A. Crotty, A. Galakatos, K. Dursun, T. Kraska, C. Binnig, U. Çetintemel, and S. Zdonik. An architecture for compiling udf-centric workflows. PVLDB, 8(12):1466–1477,2015.

22. B. Fan, D. G. Andersen, M. Kaminsky, and M. D. Mitzenmacher. Cuckoo filter: Practically better than bloom. In Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT ’14, pages 75–88, New York, NY, USA, 2014. ACM.

23. E. Fredkin. Trie memory. Commun. ACM, 3(9):490–499, Sept. 1960.

24. A. Galakatos, M. Markovitch, C. Binnig, R. Fonseca, and T. Kraska. A-tree: A bounded approximate index structure. under submission, 2017.

25. J. Goldstein, R. Ramakrishnan, and U. Shaft. Compressing Relations and Indexes. In ICDE, pages 370–379, 1998.

26. I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. In Advances in neural information processing systems, pages 2672–2680, 2014.

27. G. Graefe. B-tree indexes, interpolation search, and skew. In Proceedings of the 2Nd International Workshop on Data Management on New Hardware, DaMoN ’06, New York, NY, USA, 2006. ACM.

28. G. Graefe and P. A. Larson. B-tree indexes and CPU caches. In Proceedings 17th International Conference on Data Engineering, pages 349–358, 2001.

29. A. Graves. Generating sequences with recurrent neural networks. arXiv preprint arXiv:1308.0850, 2013.

30. R. Grossi, A. Gupta, and J. S. Vitter. High-order entropy-compressed text indexes. In Proceedings of the F o u r t e e n t h Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, pages 841–850, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics.

31. R. Grossi and G. Ottaviano. The wavelet trie: Maintaining an indexed sequence of strings in compressed space. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS ’12, pages 203–214, New York, NY, USA, 2012. ACM.

32. J. Guo and J. Li. CNN based hashing for image retrieval. CoRR, abs/1509.01354, 2015.

33. G. E. Hinton, O. Vinyals, and J. Dean. Distilling the knowledge in a neural network. CoRR,abs/1503.02531, 2015.

34. J. C. Huang and B. J. Frey. Cumulative distribution networks and the derivative-sum-product algorithm: Models and inference for cumulative distribution functions on graphs. J. Mach. Learn. Res., 12:301–348, Feb. 2011.

35. K. Kaczmarski. B + -Tree Optimized for GPGPU.

36. C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. D. Nguyen, T. Kaldewey, V. W. Lee, S. A. Brandt, and P. Dubey. Fast: Fast architecture sensitive tree search on modern cpus and gpus. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, SIGMOD ’10, pages 339–350, New York, NY, USA, 2010. ACM.

37. T. Kissinger, B. Schlegel, D. Habich, and W. Lehner. Kiss-tree: Smart latch-free in-memory indexing on modern architectures. In Proceedings of the Eighth International Workshop on Data Management on New Hardware, DaMoN ’12, pages 16–23, New York, NY, USA, 2012. ACM.

38. T. J. Lehman and M. J. Carey. A study of index structures for main memory database management systems. In Proceedings of the 12th International Conference on Very Large Data Bases, VLDB ’86, pages 294–303, San Francisco, CA, USA, 1986. Morgan Kaufmann Publishers Inc.

39. V. Leis, A. Kemper, and T. Neumann. The adaptive radix tree: Artful indexing for main-memory databases. In Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013), ICDE ’13, pages 38–49, Washington, DC, USA, 2013. IEEE Computer Society.

40. W. Litwin. Readings in database systems. chapter Linear Hashing: A New Tool for File and Table Addressing., pages 570–581. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.

41. M. Magdon-Ismail and A. F. Atiya. Neural networks for density estimation. In M. J. Kearns, S.A. Solla, and D. A. Cohn, editors, Advances in Neural Information Processing Systems 11, pages 522–528. MIT Press, 1999.

42. D. J. Miller and H. S. Uyar. A mixture of experts classifier with learning based on both labelled and unlabelled data. In Advances in Neural Information Processing Systems 9, NIPS, Denver, CO, USA, December 2-5, 1996, pages 571–577, 1996.

43. M. Mitzenmacher. Compressed bloom filters. In Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, PODC 2001, Newport, Rhode Island, USA, August 26-29, 2001, pages 144–150, 2001.

44. G. Moerkotte. Small Materialized Aggregates: A Light Weight Index Structure for Data Warehousing. In VLDB, pages 476–487, 1998.

45. T. Neumann and G. Weikum. RDF-3X: A RISC-style Engine for RDF. Proc. VLDB Endow., pages 647–659, 2008.

46. OpenStreetMap database ©OpenStreetMap contributors. https://aws.amazon.com/public-datasets/osm.

47. J. Rao and K. A. Ross. Making b+- trees cache conscious in main memory. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, SIGMOD ’00, pages 475–486, New York, NY, USA, 2000. ACM.

48. S. Richter, V. Alvarez, and J. Dittrich. A seven-dimensional analysis of hashing methods and its implications on query processing. Proc. VLDB Endow., 9(3):96–107, Nov. 2015.

49. D. G. Severance and G. M. Lohman. Differential files: Their application to the maintenance of large data bases. In Proceedings of the 1976 ACM SIGMOD International Conference on Management of Data, SIGMOD ’76, pages 43–43, New York, NY, USA, 1976. ACM.

50. A. Shahvarani and H.-A. Jacobsen. A hybrid b+-tree as solution for in-memory indexing on cpu-gpu heterogeneous computing platforms. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD ’16, pages 1523–1538, New York, NY, USA, 2016. ACM.

51. N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton, and J. Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint arXiv:1701.06538, 2017.

52. E. R. Sparks, A. Talwalkar, D. Haas, M. J. Franklin, M. I. Jordan, and T. Kraska. Automating model search for large scale machine learning. In Proceedings of the Sixth ACM Symposium on Cloud Computing, SoCC 2015, Kohala Coast, Hawaii, USA, August 27-29, 2015, pages 368–380, 2015.

53. M. Stonebraker and L. A. Rowe. The Design of POSTGRES. In SIGMOD, pages 340–355, 1986.

54. I. Sutskever, O. Vinyals, and Q. V. Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112, 2014.

55. M. Turcanik and M. Javurek. Hash function generation by neural network. In 2016 New Trends in Signal Processing (NTSP), pages 1–5, Oct 2016.

56. J. Wang, W. Liu, S. Kumar, and S. F. Chang. Learning to hash for indexing big data;a survey. Proceedings of the IEEE, 104(1):34–57, Jan 2016.

57. J. Wang, H. T. Shen, J. Song, and J. Ji. Hashing for similarity search: A survey. CoRR, abs/1408.2927, 2014.

58. K. Weinberger, A. Dasgupta, J. Langford, A. Smola, and J. Attenberg. Feature hashing for large scale multitask learning. In Proceedings of the 26th Annual Internatio nal Conference on Machine Learning, ICML ’09, pages 1113–1120, New York, NY, USA, 2009. ACM.

59. Y. Wu, M. Schuster, Z. Chen, Q. V. Le, M. Norouzi, W. Macherey, M. Krikun, Y. Cao, Q. Gao, K. Macherey, et al. Google’s neural machine translation system: Bridging t he gap between human and machine translation. arXiv preprint arXiv:1609.08144, 2016.

60. J. Yu and M. Sarwat. Two Birds, One Stone: A Fast, Yet Lightweight, Indexing Scheme for Modern Database Systems. In VLDB, pages 385–396, 2016.

61. H. Zhang, D. G. Andersen, A. Pavlo, M. Kaminsky, L. Ma, and R. Shen. Reducing the storage overhead of main-memory OLTP databases with hybrid indexes. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 1567–1581, 2016.