發(fā)布時間：2020-02-07 06:47

【摘要】：近似近鄰查詢是信息檢索領域中的一項重要技術.隨著文本、圖像、視頻等非結構化數(shù)據(jù)規(guī)模的迅速增長,如何對海量高維數(shù)據(jù)進行快速、準確的查詢是處理大規(guī)模數(shù)據(jù)所必須面對的問題.哈希作為近似近鄰查詢的關鍵方法之一,能夠在保持數(shù)據(jù)相似性的條件下對高維數(shù)據(jù)進行大比例壓縮.以往所提出的哈希方法往往都是應對集中式存儲的數(shù)據(jù),因而難以處理分布式存儲的數(shù)據(jù).該文提出了一種基于乘積量化的分布式哈希學習方法SparkPQ,并在Spark分布式計算框架下實現(xiàn)算法.在傳統(tǒng)的乘積量化方法的基礎上,該文首先給出了分布式乘積量化模型的形式化定義.然后,作者設計了一種按行列劃分的分布式矩陣,采用分布式K-Means算法實現(xiàn)模型求解和碼本訓練,利用訓練出的碼本模型對分布式數(shù)據(jù)進行編碼和索引.最終,該文構建了一套完整的近似近鄰查詢系統(tǒng),不僅可以大幅降低存儲和計算開銷,而且在保證高檢索準確率的條件下加速查詢效率.在較大規(guī)模的圖像檢索數(shù)據(jù)集上進行的實驗驗證了方法的正確性和可擴展性.
【圖文】：

成一棧式的生態(tài)系統(tǒng)．圖１是Ｓｐａｒｋ集群系統(tǒng)架構圖．驅動程序（Ｄｒｉｖｅｒ）會和集群的管理器（ＣｌｕｓｔｅｒＭａｎａｇｅｒ）相連接，驅動管理器為集群其他節(jié)點分配資源．在分配完畢以后，驅動程序會將應用程序發(fā)送到各個節(jié)點的執(zhí)行進程（Ｅｘｅｃｕｔｏｒ）．之后驅動程序會調(diào)配任務給各個執(zhí)行進程執(zhí)行任務．圖１Ｓｐａｒｋ集群系統(tǒng)架構圖彈性分布式數(shù)據(jù)集（ＲｅｓｉｌｉｅｎｔＤｉｓｔｒｉｂｕｔｅｄＤａｔａ－ｓｅｔｓ，ＲＤＤ）［１１］是Ｓｐａｒｋ中的分布式內(nèi)存的抽象．相比于ＭａｐＲｅｄｕｃｅ的計算過程，ＲＤＤ可以被緩存在內(nèi)存中，每一次的計算產(chǎn)生的結果都可以保留在內(nèi)存中，從而避免了大量的磁盤讀寫操作，大大節(jié)省了計算時間．在Ｓｐａｒｋ程序中，ＲＤＤ的創(chuàng)建是通過靜態(tài)類ＳｐａｒｋＣｏｎｔｅｘｔ來實現(xiàn)，主要包含有兩種創(chuàng)建來源：一是從指定的文件系統(tǒng)（或指定的數(shù)據(jù)庫）讀取數(shù)據(jù)來創(chuàng)建；二是從內(nèi)存數(shù)據(jù)集合直接生成．不同于ＭａｐＲｅｄｕｃｅ中僅有ｍａｐ和ｒｅｄｕｃｅ兩種操作，ＲＤＤ還支持多種豐富的常用操作，主要分為轉換操作、控制操作和行為操作３類．轉換操作顧名思義，就是將一個ＲＤＤ操作之后轉換為另一個ＲＤＤ，包括ｍａｐ、ｆｌａｔＭａｐ、ｆｉｌｔｅｒ等操作．控制操作主要是將ＲＤＤ緩存到內(nèi)存中或者磁盤上，比如ｃａｃｈｅ、ｐｅｒｓｉｓｔ、ｃｈｅｃｋ－ｐｏｉｎｔ等操作．行為操作主要分為兩類：一類是變成集合或標量的操作；另一類是將ＲＤＤ存儲到外部文件系統(tǒng)或數(shù)據(jù)庫的操作．Ｓｐａｒｋ的所有對ＲＤＤ的操作，只有

圖３ＢｌｏｃｋＭａｔｒｉｘ的劃分方式４．３訓練碼本首先，我們將乘積量化模型的目標函數(shù)進行分布式表示，把式（１）改寫成弗羅貝尼烏斯范數(shù)（Ｆｒｏｂｅｎｉｕｓｎｏｒｍ）的形式：辶ＰＱ＝ｍｉｎＸ－Ｃ１Ｂ１鐤ＣｍＢq縬纐膓牛恚玻疲ǎ玻┢渲校兀劍保�，ｘ２，…，｀P藎�，n劍猓�，ｂ２，…，｀P猓藎睿旅嬤っ魅綰未郵劍ǎ保┩頻嫉絞劍ǎ玻っ鰨篩ヂ薇茨崳謁狗妒畝ㄒ蹇芍粒玻疲健疲欏疲輳幔椋輳玻健疲椋幔椋玻�，而Ｘ－Ｃ１n辯枺茫恚聁縬纐膓牛恚玻疲劍保�，｀P藎睿茫保猓保�，ｂ１２，…，ｂ１｀P藎鉉枺茫恚猓恚�，ｂｍ２，…，ｂｍ｀P輖縬纐模顀牛玻疲劍保保茫保猓保�，ｘ１２－Ｃ１ｂ１２，…，ｘ１ｎ－Ｃ１ｂ１ｃC枺恚保茫恚猓恚�，ｘｍ２－Ｃｍｂｍ２，…，ｘｍｎ－Ｃｍｂｍｎ２Ｆ，故Ｘ－Ｃ１n辯枺茫恚聁縬纐膓牛恚玻疲健疲睿椋劍保椋茫保猓保殮枺茫恚猓韖縬纐模閝牛玻玻虼聳劍ǎ保┛梢愿男次劍ǎ玻け希詵植際降南低持校菔欠植際降卮媧⒃謨滌校癰黿詰愕募撲慵荷希偕璧冢舾黿詰閔洗媧⒌模睿舾鍪藎吹氖菥卣螅鼐涂梢員換殖桑癰魴〉木卣蠼蟹植際醬媧�，即Ｘ�

本文編號：2577111