[發明專利]一種基于微型計算平臺的實時響應大媒體近鄰檢索方法

有效

• 申請號: 201810038892.2
• 申請日: 2018-01-16
• 公開（公告）號: CN108256058B
• 公開（公告）日: 2021-05-07
• 發明（設計）人: 王振;孫福振;王雷;李鑫鑫
• 申請（專利權）人: 山東理工大學
• 主分類號: G06F16/43
• 分類號: G06F16/43
• 代理公司: 濟南智圓行方專利代理事務所(普通合伙企業) 37231
• 代理人: 張玉琳

本發明公開了一種基于微型計算平臺的實時響應大媒體近鄰檢索方法，涉及檢索技術領域，技術方案為提出了一種新型的快速生成多媒體二值特征的方法和一種高區分性的后驗證距離表，首先，本文根據數據集的聚類特性生成初始中心點，使得算法能夠快速收斂到最優解。然后，學習滿足序列保持的哈希映射函數，保證所得二值編碼能保持數據點之間的原序列關系。最后，根據數據點的二值編碼建立高區分性的距離表。本發明的有益效果是：解決了在微型計算平臺上實時響應大媒體數據近鄰檢索請求的問題，其對存儲資源以及計算能力的要求較低，并構建了適應于微型計算平臺的近鄰檢索體系。

技術領域

本發明涉及檢索技術領域，特別涉及一種基于微型計算平臺的實時響應大媒體近鄰檢索方法。

背景技術

近年來，多媒體技術的快速發展使得網絡中的共享多媒體數據呈指數形式增長，人們開始關注海量多媒體數據的近鄰檢索問題。

傳統多媒體數據的特征一般為高維浮點型向量，例如SIFT(尺度不變特征變換)特征是128維的浮點型向量，而GIST特征^[2]為320維或640維的浮點型向量。若通過計算并比較浮點型特征向量之間的歐式距離來檢索多媒體近鄰點，其計算復雜度較高，對計算平臺的性能要求較苛刻。再者，將所有浮點型數據一次性全部調入計算平臺的內存中，需要占用大量的存儲資源。上述兩點使得微型計算平臺無法實時響應海量多媒體的近鄰檢索請求。為此，人們提出將高維浮點型向量轉化為緊湊二進制編碼，并根據漢明距離關系檢索多媒體近鄰點。

最早提出利用二值編碼檢索近鄰點的是局部敏感哈希算法，其采用隨機的方式生成滿足局部敏感特性的線性哈希映射函數。但是，算法的訓練過程不依賴于訓練數據集，若要得到令人滿意的近鄰檢索結果，其所生成的二進制編碼應足夠長。

為了保證采用緊湊二值編碼也能獲取較優的近鄰檢索性能，人們開始探索利用機器學習方法，依據訓練數據集，生成滿足特定約束條件的二進制編碼。譜哈希算法^[4]根據數據點之間的相似性構造譜圖，并通過分割相似性譜圖學習數據點的二值編碼。迭代量化哈希算法^[5]將超立方體的頂點作為編碼中心點，并根據數據點與超立方體頂點之間的距離關系生成數據點的二值編碼，但超立方體的頂點是固定不變的，所生成的二值編碼的空間分布自適應能力較差。K均值哈希算法^[6]提出編碼中心點應滿足聚類分布特性，從而保證所生成的二值編碼符合數據集的空間分布特性。

為了能夠在漢明空間內得到較優的近鄰檢索性能，許多哈希算法建立了相似性保持約束條件。二值重建哈希算法^[7]要求最小化數據點對的漢明距離和歐式距離之間的差值，核監督哈希算法^[8]要求數據點在漢明空間和歐式空間內的相似性具有較高的一致性。上述哈希算法中的定義屬于絕對相似性保持約束條件，但近似近鄰檢索任務更加關注數據點之間的相對相似性。三元損失哈希算法^[9]要求三元組之間的相對關系在漢明空間和原空間內是一致的，序列監督哈希算法也基于三元組張量之間的相對關系定義目標函數，頂部排序監督二值編碼算法重點關注近鄰檢索結果中排序較靠前的數據點之間的相對相似性。

多數哈希算法采用隨機梯度下降算法優化原目標函數，但受二值編碼長度以及隨機梯度下降算法本身的局限性，單組二值編碼已無法準確表達數據點之間的近鄰關系。為此，人們探索生成多重二值編碼，從而能夠較好地解決局部優解的問題。Charikar等人提出多重局部敏感哈希算法(MLSH)，其采用隨機的方式，生成數據點的多重二值編碼，并根據平均漢明距離返回近鄰點。K均值局部敏感哈希算法(KLSH)^[13]采用隨機的方式生成多組初始中心點，并利用隨機梯度下降算法優化目標函數學習多組二進制編碼。與KLSH算法單獨生成每組二值編碼的機制不同，聯合倒排索引算法(JII)一次性生成數據點的多個二值編碼中心點，然后依據它們之間的相似性關系對其分組，從而形成多組二值編碼。

發明內容

為了實現上述發明目的，本發明提出了一種基于微型計算平臺的實時響應大媒體近鄰檢索方法。