[發明專利]矩陣數據索引方法及裝置

在審

• 申請號: 201410159202.0
• 申請日: 2014-04-18
• 公開（公告）號: CN105095208A
• 公開（公告）日: 2015-11-25
• 發明（設計）人: 穆亞東;赫彩鳳;范偉
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京同立鈞成知識產權代理有限公司 11205
• 代理人: 劉芳

技術領域

本發明涉及數據處理技術，尤其涉及一種矩陣數據索引方法及裝置。

背景技術

矩陣是一種常見的數據表達形式，廣泛應用于多個領域。但是，矩陣數據往往尺寸較大，直接保存矩陣會占用較大的存儲空間，也不便于對矩陣數據進行索引；當前，針對矩陣的索引，可以有多種不同的算法，其中，在矩陣維度較大時，索引函數的復雜度是一個不可忽略的問題，具體地，對于一個矩陣元素個數為百萬量級，對于一些復雜度高的索引函數，其參數個數也會在百萬量級，存儲大量的索引函數也會耗費大量的存儲空間。

現有技術中，對于矩陣數據的索引，主要是將矩陣數據展開為向量，即將矩陣逐行或逐列拼接，然后采用向量索引技術加以處理。現有的向量索引技術主要包括基于樹的方法，例如：K維樹（k-dtree）方法。但是，采用這種方法，在矩陣維度較高的情況下無法獲取合理的計算復雜度。

另外，現有技術中，對于矩陣元素較多的情況，還采用對矩陣元素欠采樣（under-sampling）的方法，這種方法通過減少參與索引計算的元素個數，降低索引函數的復雜度。但是，采用這種方法會造成有效信息的損失，從而導致索引函數性能下降。

發明內容

本發明實施例提供一種矩陣數據索引方法及裝置，用于解決現有技術矩陣索引方法在矩陣維度較高的情況下無法獲取合理的計算復雜度，以及有效信息損失的問題。

本發明實施例第一方面提供一種矩陣數據索引方法，包括：

獲取目標矩陣，其中，所述目標矩陣包括n×m個元素；

利用雙線性哈希函數，獲取所述目標矩陣對應的二值哈希碼；

根據所述二值哈希碼進行矩陣數據索引。

結合第一方面，在第一方面的第一種可能的實施方式中，所述利用雙線性哈希函數，獲取所述目標矩陣對應的二值哈希碼之前，還包括：

根據所述目標矩陣，獲取預設組高斯隨機變量；

其中，每組所述高斯隨機變量包括：第一高斯隨機變量和第二高斯隨機變量，所述第一高斯隨機變量為n維向量，所述第二高斯隨機變量為m維向量。

結合第一方面的第一種可能的實施方式，在第一方面的第二種可能的實施方式中，所述二值哈希碼包括0和1。

結合第一方面的第二種可能的實施方式，在第一方面的第三種可能的實施方式中，所述雙線性哈希函數為其中，X表示所述目標矩陣，u_k表示所述第一高斯隨機變量，v_k表示所述第二高斯隨機變量，表示所述u_k的轉置向量。

結合第一方面的第二種可能的實施方式，在第一方面的第四種可能的實施方式中，所述利用雙線性哈希函數，獲取所述目標矩陣對應的二值哈希碼之前，還包括：

根據所述目標矩陣，獲取所述目標矩陣的隨機置換函數。

結合第一方面的第四種可能的實施方式，在第一方面的第五種可能的實施方式中，所述雙線性哈希函數為其中，φ(X)表示所述目標矩陣的置換函數，u_k表示所述第一高斯隨機變量，v_k表示所述第二高斯隨機變量，表示所述u_k的轉置向量。

本發明第二方面提供一種矩陣數據索引裝置，包括：

獲取模塊，用于獲取目標矩陣，其中，所述目標矩陣包括n×m個元素；利用雙線性哈希函數，獲取所述目標矩陣對應的二值哈希碼；

索引模塊，用于根據所述二值哈希碼進行矩陣數據索引。

結合第二方面，在第二方面的第一種可能的實施方式中，所述獲取模塊，還用于在利用雙線性哈希函數，獲取所述目標矩陣對應的二值哈希碼之前，根據所述目標矩陣，獲取預設組高斯隨機變量；

其中，每組所述高斯隨機變量包括：第一高斯隨機變量和第二高斯隨機變量，所述第一高斯隨機變量為n維向量，所述第二高斯隨機變量為m維向量。

結合第二方面的第一種可能的實施方式，在第二方面的第二種可能的實施方式中，所述二值哈希碼包括0和1。

結合第二方面的第二種可能的實施方式，在第二方面的第三種可能的實施方式中，所述雙線性哈希函數為其中，X表示所述目標矩陣，u_k表示所述第一高斯隨機變量，v_k表示所述第二高斯隨機變量，表示所述u_k的轉置向量。

結合第二方面的第二種可能的實施方式，在第二方面的第四種可能的實施方式中，所述獲取模塊，還用于在利用雙線性哈希函數，獲取所述目標矩陣對應的二值哈希碼之前，根據所述目標矩陣，獲取所述目標矩陣的隨機置換函數。