[發明專利]參考距離相似性搜索

在審

• 申請號: 202010522234.8
• 申請日: 2020-06-10
• 公開（公告）號: CN112199408A
• 公開（公告）日: 2021-01-08
• 發明（設計）人: D·伊蘭;A·戈特利布
• 申請（專利權）人: GSI科技公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458;G06K9/62
• 代理公司: 永新專利商標代理有限公司 72002
• 代理人: 劉瑜

一種相似性搜索系統包括原始向量的數據庫、箱的層級數據庫以及相似性搜索器。箱的層級數據庫存儲在關聯存儲器陣列中，每個箱由表示至少一個原始向量的階向量標識，并且階向量的維度小于原始向量的維度。相似性搜索器針對至少一個相似的箱在數據庫中進行搜索，這些相似的箱的階向量類似于表示查詢向量的階向量，并且該相似性搜索器提供由箱表示的類似于查詢向量的至少一個原始向量。

相關申請的交叉引用

本申請要求享有于2019年7月8日提交的美國臨時專利申請62/871,212以及于2020年4月1日提交的美國臨時專利申請63/003,314的優先權，這兩者通過引用并入本文。

技術領域

本發明總體上涉及關聯計算，并且具體地涉及使用關聯計算的數據挖掘算法。

背景技術

數據挖掘是發現大型數據集中的模式的計算過程。數據挖掘使用不同的技術來分析數據集。數據挖掘中經常需要的計算是在n維空間中的快速且準確的相似性搜索，其中空間中的存儲在大型數據集中的每個項目都由n個浮點數的向量表示。相似性搜索的目的是迅速地標識數據集中類似于特定的查詢項目的項目，該特定的查詢項目也由n個浮點數的向量表示。

在整個文檔中，包含維度S的L個向量的空間表示為E＝{E1，E2……El}(|E|＝L)，查詢向量表示為Q(其也為維度S的)，并且空間E中的一般向量表示為Ei(0iL)。搜索的目的是查找與Q最相似的(即，距Q的距離最小的)K個向量Ei∈E(KL)的子集。

用于查找與查詢Q最相似的K個項目Ei的集合的最先進的解決方案中的一種是利用距離函數(例如，L2距離、余弦距離、漢明距離等)的K最鄰近搜索算法。

發明內容

根據本發明的實施例，提供了一種相似性搜索系統。該系統包括原始向量的數據庫、箱(bin)的層級數據庫以及相似性搜索器。箱的層級數據庫存儲在關聯存儲器陣列中，每個箱由表示至少一個原始向量的階向量標識，并且階向量的維度小于原始向量的維度。相似性搜索器針對至少一個相似的箱在數據庫中進行搜索，這些相似的箱的階向量類似于表示查詢向量的階向量，并且該相似性搜索器提供由箱表示的類似于查詢向量的至少一個原始向量。

另外地，根據本發明的實施例，層級數據庫的箱存儲在關聯存儲器陣列的列中，并且相似性搜索器對多個列同時操作。

此外，根據本發明的優選實施例，層級數據庫按級別布置，每個級別存儲在關聯存儲器陣列的不同部分中。

此外，根據本發明的優選實施例，系統包括層級數據庫構建器，該層級數據庫構建器用于根據原始向量的數據庫來構建箱的層級數據庫。

另外，根據本發明的優選實施例，層級數據庫構建器包括參考向量定義器、階向量創建器和箱創建器。參考向量定義器以原始向量的維度來定義參考向量的集合。階向量創建器針對每個原始向量計算到每個參考向量的距離，并且創建階向量，該階向量包括按參考向量距原始向量的距離排序的參考向量的ID，并且箱創建器創建由表示至少一個原始向量的階向量標識的箱。

另外地，根據本發明的優選實施例，層級數據庫構建器將表示共享階向量的不同原始向量的階向量聚類到單個箱。

此外，根據本發明的優選實施例，層級數據庫包括至少兩個級別，并且一級別中的箱與較低級別中的箱相關聯。

此外，根據本發明的優選實施例，相似性搜索器在層級數據庫的第一級別中開始搜索，并且繼續搜索在較低級別中的與在第一級別中找到的箱相關聯的箱。