學習索引結構的一些案例——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個字節(十億 = $^9$$ bit ， 位數 = $ * 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

構建存在索引的另一種方法是作為二元分類任務。 也就是說，我們想要學習一個模型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是每個角色的嵌入尺寸。）

在分類問題的初始化設置中，我們選擇一個閾值τ并且接受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 ]，并且使用批處理請求等技術可以分攤調用成本，因此我們不相信調用延遲是一個真正的障礙。

總之，我們已經證明，機器學習模型有可能比最先進的數據庫索引提供顯著的優勢，并且我們相信這個方向將在未來結出美妙研究成果。

參考文章

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

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

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.

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

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.

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

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

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

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.

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.

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.

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

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.

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

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.

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.

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.

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.

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.

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

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.

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.

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

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

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

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.

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.

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

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

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.

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.

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

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

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.

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

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.

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.

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.

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.

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.

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.

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.

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.

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

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

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

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.

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.

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.

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.

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.

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.

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

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.

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

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.

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

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.

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.

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.

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.

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。