基于堆疊乘積量化的最近鄰檢索.pdf

1、近年來，大數(shù)據(jù)、人工智能和物聯(lián)網(wǎng)技術(shù)得到飛速的發(fā)展，圖像、視頻等高維數(shù)據(jù)正呈現(xiàn)爆炸性增長。在這些海量的高維數(shù)據(jù)中查找目標(biāo)數(shù)據(jù)也隨之變得耗時(shí)和低效。為了解決上述問題，近似最近鄰的概念及各種算法被陸續(xù)提出，并成為圖像檢索、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等多種應(yīng)用中的一類基本算法。其中的乘積量化算法(PQ)具備內(nèi)存消耗低，查詢效率高等優(yōu)點(diǎn)，被證明是解決高維空間近似最近鄰查找的最有效算法之一。
　　基于經(jīng)典乘積量化算法的不足，近年來不少學(xué)者對(duì)乘積量化

2、算法進(jìn)行了優(yōu)化改進(jìn)，由于乘積量化算法中存在向量子空間中特征點(diǎn)分布不均勻的問題，優(yōu)化的乘積量化算法(OPQ)被提出來，用于優(yōu)化空間特征點(diǎn)的重新分配。由于對(duì)特征向量進(jìn)行簡單劃分，會(huì)導(dǎo)致子向量間的相互獨(dú)立，有學(xué)者提出了加法量化算法(AQ)以解決這個(gè)問題。為解決特征向量在進(jìn)行量化時(shí)，存在量化誤差較大的問題，堆疊量化算法(SQ)通過迭代地對(duì)誤差進(jìn)行量化，以進(jìn)一步降低量化誤差。
　　本文中，我們提出了一種新的量化算法來做近似最近鄰查找:堆疊乘

3、積量化算法。這種量化算法融合了堆疊量化算法的量化誤差低和乘積量化算法內(nèi)存消耗低的優(yōu)點(diǎn)。該算法的核心思想為:第一步將高維的特征向量劃分成維度相同的低維子特征向量，在每個(gè)子向量空間中進(jìn)行k-means聚類量化;第二步將特征向量與量化后對(duì)應(yīng)的編碼單詞做差得到對(duì)應(yīng)的誤差向量;第三步把誤差向量看成特征向量，以此進(jìn)行劃分子向量、子向量分別量化、求誤差向量的操作;迭代第三步直到達(dá)到終止條件，從而產(chǎn)生一組從粗糙到精細(xì)的分層子碼本。對(duì)分層子碼本進(jìn)行笛卡兒