隨著大數(shù)據(jù)和人工智能的高速發(fā)展,針對多媒體數(shù)據(jù)的結(jié)構(gòu)化處理與基于內(nèi)容的檢索受到極大的關(guān)注,面對多媒體數(shù)據(jù)結(jié)構(gòu)化后的海量高維特征向量,如何快速、準(zhǔn)確地檢索是人工智能處理大規(guī)模數(shù)據(jù)所必須解決的問題。最近提出的分層可通航小世界圖HNSW檢索算法在多個公開數(shù)據(jù)集取得了最佳的性能表現(xiàn),但該算法存在內(nèi)存開銷大的問題。而基于量化編碼的檢索算法能夠壓縮數(shù)據(jù)集向量,大幅度降低內(nèi)存占用。將量化編碼和分層可通航小世界圖算法結(jié)合,提出了2種基于量化編碼改進的HNSW算法,分別是使用標(biāo)量量化編碼向量的HNSWSQ算法和使用乘積量化編碼向量的HNSWPQ算法,2種算法使用不同的量化策略存儲原始向量編碼,以降低內(nèi)存開銷,再通過HNSW算法建立索引達到縮短檢索耗時的目的。其中HNSWSQ算法在多個數(shù)據(jù)集上獲得了與HNSW算法相近的查全率和平均檢索耗時,而內(nèi)存開銷大幅降低。實驗結(jié)果表明,HNSWSQ算法在SIFT-1M和GIST-1M數(shù)據(jù)集上的內(nèi)存開銷比HNSW算法分別降低了45.1%和70.4%。 

【文章來源】：計算機工程與科學(xué). 2019,41(04)北大核心

【文章頁數(shù)】：8 頁

【部分圖文】：

圖１ＨＮＳＷ算法查找過程Ｆｉｇｕｒｅ１ＳｅａｒｃｈｐｒｏｃｅｓｓｏｆｔｈｅＨＮＳＷａｌｇｏｒｉｔｈｍ

１２８維，設(shè)置乘積量化的參數(shù)為ｍ＝１６，ｋ＊＝２５６，則每個向量被量化為１６個字節(jié)，相比于原始的１２８＊４＝５１２字節(jié)，理論上內(nèi)存消耗最多降低為原來的１／３２，如圖２所示。ＨＮＳＷＰＱ算法將ＨＮＳＷ算法作為索引算法，采用ＰＱ算法進行向量編碼，由于使用ＰＱ算法對原始向量編碼，需要將ＨＮＳＷ算法插入過程中與近鄰點距離的計算相應(yīng)地修改為ＰＱ的距離計算。Ｆｉｇｕｒｅ２ＡＰＱｑｕａｎｔｉｚａｔｉｏｎｅｘａｍｐｌｅ圖２ＰＱ量化示例圖數(shù)據(jù)集中的向量被編碼后存儲在內(nèi)存中，每個向量根據(jù)子向量最近鄰中心點的編號編碼。李秋珍等：量化編碼的分層可通航小世界圖算法１２６

ＨＮＳＷ算法構(gòu)建索引計算查詢向量與圖中點ｙ的距離時，首先計算查詢向量每個子向量與對應(yīng)分段中心點的距離表，然后根據(jù)ｙ的編碼查表獲得ｄ（ｘ，ｙ）的近似值。圖３是向量維數(shù)ｄ＝１６，乘積量化參數(shù)ｍ＝４，ｋ＊＝８時計算查詢向量ｘ與數(shù)據(jù)集中向量ｙ的距離的例子。Ｆｉｇｕｒｅ３ＡＰＱｄｉｓｔａｎｃｅｃｏｍｐｕｔｉｎｇｅｘａｍｐｌｅ圖３ＰＱ距離計算示例圖Ｆｉｇｕｒｅ４Ａｓｃａｌａｒｑｕａｎｔｉｚａｔｉｏｎｃｏｍｐｕｔｉｎｇｅｘａｍｐｌｅ圖４標(biāo)量量化計算示例圖４．２ＨＮＳＷＳＱ算法標(biāo)量量化（ＳＱ）對向量的每一維量化，分層可通航小世界標(biāo)量量化ＨＮＳＷＳＱ（ＨｉｅｒａｒｃｈｉｃａｌＮａｖｉｇａ－ｂｌｅＳｍａｌｌＷｏｒｌｄＳｃａｌａｒＱｕａｎｔｉｚａｔｉｏｎ）算法采用最大最小量化。對于向量的第ｉ維，通過樣本集訓(xùn)練獲取該維出現(xiàn)的最大值ｖｍａｘ［ｉ］和最小值ｖｍｉｎ［ｉ］，然后將向量ｘ第ｉ維的值量化為（ｘｉ－ｖｍｉｎ［ｉ］）／（ｖｍａｘ［ｉ］），ｉ＝１，…，ｎ，量化后的值編碼存儲，假設(shè)每一維編碼為１個字節(jié)，則進一步處理為：ｆ（ｘｉ）＝φｘｉ－ｖｍｉｎ［ｉ］ｖｍａｘ［ｉ（）］＊２５５（３）其中，φ（ｘ）＝１，ｘ≥１ｘ，０＜ｘ＜１０，ｘ≤烅烄烆０，·表示向下取整。標(biāo)量量化計算示例如圖４所示。從圖４可以看到，對于４維的原始向量，每一維編碼為１個字節(jié)，則編碼后向量長度為４字節(jié)，相比于編碼前的１６


本文編號：3007455