[發明專利]用于特征搜索的系統、裝置和方法

有效

• 申請號: 201510218447.0
• 申請日: 2015-02-25
• 公開（公告）號: CN104866537B
• 公開（公告）日: 2019-09-10
• 發明（設計）人: 孔祥重
• 申請（專利權）人: 英特爾公司
• 主分類號: G06F16/903
• 分類號: G06F16/903
• 代理公司: 上海專利商標事務所有限公司 31100
• 代理人: 錢慰民

1.一種裝置，包括：

多個向量部分距離計算電路，所述多個向量部分距離計算電路中的每一個用于為搜索空間中的向量集合計算部分總和以及累積距離；

最小值排序網絡，用于根據所述累積距離對來自搜索空間中的向量的選定的位集合進行排序，并指示所述選定的位集合的最小值以及所述最小值是否是唯一；

全局控制電路，用于接收最小值排序網絡的輸出，并控制多個向量局部距離計算電路的操作的多個方面，其中所述多個向量局部距離計算電路和所述最小值排序網絡。

2.根據權利要求1所述的裝置，其中每個向量部分距離計算電路包括：

多個數據元素計算器電路；

壓縮器樹電路，用于添加多個數據元素計算器電路的每個結果；以及

局部控制電路，用于輸出根據所述累積距離的位的較小的窗口。

3.根據權利要求1-2中任一項所述的裝置，其中最小值排序網絡包括：

多個0等級比較節點，用于從鄰近向量部分距離計算電路接收部分總和與有效位，并輸出有效位、精確位、地址以及總和，其中所述0等級比較節點用于：

對接收的鄰近有效位進行邏輯OR運算，以提供輸出有效位，

對接收的鄰近有效位進行異或運算，以提供具有鄰近總和比較的可能差的總和的輸出的輸出精確位，以生成輸出精確位，其中精確位用于指示兩個輸入之間的差是否大于可編程閾值；以及

多個k等級比較節點，用于從鄰近比較節點接收部分總和、有效位、地址和精確位，并輸出有效位、精確位、地址以及總和，所接收的總和的比較結果用于從傳入精確信號中選擇，所選的精確節點與在該節點處計算的精確信號的邏輯與運算用于產生指示所述輸出總和是否唯一的輸出精確信號。

4.根據權利要求3所述的裝置，其中全局控制電路包括：

OR樹，用于接收和對來自多個局部控制電路的多個消除位進行OR運算；

全局掩碼，用于向全局控制邏輯指示：全局指針需要為將包含下一個最近鄰的該組向量跳回到何處；

選擇器，從以一遞增的之前全局指針選擇全局指針，并從耦合到全局掩碼的優先級編碼器選擇輸出。

5.根據權利要求1-4中任一項所述的裝置，其中每個維度的位尺寸、維度和引用的數量是可編程的。

6.根據權利要求2-5中任一項所述的裝置，其中多個數據元素計算器電路中的每一個是絕對差電路的總和。

7.根據權利要求2-5中任一項所述的裝置，其中多個數據元素計算器電路中的每一個是平方電路的總和。

8.根據權利要求2-5中任一項所述的裝置，其中多個數據元素計算器電路中的每一個是8位到16位的可重新配置的電路。

9.根據權利要求2-5中任一項所述的裝置，其中多個數據元素計算器電路中的每一個是點積電路。

10.根據權利要求1-9中任一項所述的裝置，其中全局控制電路使用全局指針協調將累積距離中的多個位發送到排序網絡的活動，所述全局指針被廣播到所有向量，向所有向量廣播用于迭代依賴的部分距離計算的控制信號，并且跟蹤當發現最近鄰時從搜索空間消除向量的諸個迭代。

11.根據權利要求10所述的裝置，其中控制信號將被存儲在由全局指針引用的可編程查找表中。

12.根據權利要求2-11中任一項所述的裝置，其中每個向量部分距離計算電路中的所述局部控制電路和距離累加器用于即使從搜索空間將狀態消除之后仍維持所述狀態，并且當發現下一個最近鄰時，局部控制能夠將向量重新插入到搜索空間中，并重新使用任何先前計算直到先前消除的點。

13.一種方法，包括：

執行以下操作的連續迭代：

為關于查詢向量的多個向量計算部分距離；

累積計算的距離；

從最高有效位開始到最低有效位排序那些累積距離。

14.根據權利要求13所述的方法，其中每個連續迭代提高從最高有效位到最低有效位的計算的部分距離的精度。

15.根據權利要求13-14中任一項所述的方法，其中從最高有效位開始到最低有效位排序那些累積距離以低精度的距離開始，并且僅余下向量前進到下一迭代，以改善用于確定最近鄰的較低位精度。