[發(fā)明專利]存儲器中高效多步搜索

在審

• 申請?zhí)枺?/td>: 202010423479.5
• 申請日: 2020-05-19
• 公開（公告）號: CN111966722A
• 公開（公告）日: 2020-11-20
• 發(fā)明（設(shè)計）人: A·奧凱里博
• 申請（專利權(quán)）人: GSI科技公司
• 主分類號: G06F16/2458
• 分類號: G06F16/2458
• 代理公司: 永新專利商標(biāo)代理有限公司 72002
• 代理人: 劉文燦

用于執(zhí)行級聯(lián)搜索的系統(tǒng)包括關(guān)聯(lián)存儲器陣列、控制器、相似性搜索處理器和精確匹配處理器。關(guān)聯(lián)存儲器陣列存儲有存儲在關(guān)聯(lián)存儲器陣列的至少一列中的多個多部分?jǐn)?shù)據(jù)矢量。每個矢量在該列中具有彼此對齊的第一部分和第二部分?？刂破骺刂脐P(guān)聯(lián)存儲器陣列對第一部分執(zhí)行相似性查詢的相似性搜索，并對第二部分執(zhí)行精確查詢的精確搜索。相似性匹配處理器生成包括與每個相似性匹配的列對齊的匹配比特指示的匹配行。匹配行指示哪些列具有與相似性查詢匹配的第一部分。精確匹配處理器從相似性匹配的列當(dāng)中輸出具有匹配精確查詢的第二部分的精確匹配列。

相關(guān)申請的交叉引用

本申請要求享有于2019年5月19日提交的美國臨時專利申請62/849,913的優(yōu)先權(quán)和利益，其通過引用方式并入本文。

技術(shù)領(lǐng)域

本發(fā)明總體上涉及搜索，并且涉及用于搜索數(shù)據(jù)和元數(shù)據(jù)的高效方法。

背景技術(shù)

隨著互聯(lián)網(wǎng)的出現(xiàn)以及諸如Google、Bing和Duck Duck Go之類的搜索引擎的發(fā)展，術(shù)語“搜索”已經(jīng)變得無處不在。這些互聯(lián)網(wǎng)搜索引擎采用基于文本的查詢，并將其與網(wǎng)站內(nèi)容和元數(shù)據(jù)進行比較，并且根據(jù)其自身的排名系統(tǒng)返回匹配項。這種關(guān)鍵詞搜索也稱為精確搜索。

盡管精確搜索可能是最常見的搜索類型，但它不是計算機執(zhí)行的唯一搜索類型。網(wǎng)絡(luò)管理員擔(dān)心黑客會破壞其通信和計算機網(wǎng)絡(luò)。黑客可能試圖通過網(wǎng)絡(luò)上設(shè)備或應(yīng)用中的漏洞將惡意代碼注入網(wǎng)絡(luò)。通過將注入的代碼與已知的入侵類型進行比較，他們可以識別出此類惡意有效載荷并將其從網(wǎng)絡(luò)中刪除。化學(xué)家可能希望將新開發(fā)的分子與其他已知分子進行比較，以試圖理解它們?nèi)绾畏磻?yīng)或溶解。這種類型的搜索被稱為相似性搜索，并且可以基于人工智能(AI)方法。相似性搜索度量可以比較查詢分子指紋中存在的特征和候選分子指紋中存在的特征。這樣的度量的示例是Tanimoto、Hamming、L1、L2或Jaccard搜索?；瘜W(xué)經(jīng)常使用Tanimoto度量來量化分子指紋之間的相似性。

現(xiàn)在參考圖1，其示出了被分成兩部分的多部分矢量1，所述兩部分為第一部分2和第二部分3。多部分矢量可以包括一個以上類型的數(shù)據(jù)，因此在網(wǎng)絡(luò)管理員示例中，第一部分2可以是包括尋址和傳輸信息的報頭，并且第二部分3可以是包括文件或其他數(shù)據(jù)的有效載荷。在化學(xué)示例中，第一部分2可以包括分子指紋，并且第二部分3可以包括與分子指紋相關(guān)聯(lián)的元數(shù)據(jù)或元數(shù)據(jù)指針。第一部分2可以具有與第二部分3相同或不同的尺寸。

給定這樣的多部分矢量，搜索者可以利用迭代搜索，所述迭代搜索可以使用多部分矢量的部分之一的初始搜索來形成目標(biāo)組。然后可以隨后使用多部分矢量的第二部分來搜索該目標(biāo)組本身。這種迭代搜索稱為多階段搜索或級聯(lián)搜索，其中搜索i將其結(jié)果給搜索i+1，并且是一項常見且眾所周知的任務(wù)。級聯(lián)搜索可以在先前的網(wǎng)絡(luò)和化學(xué)示例中被利用，然而，所利用的搜索類型以及搜索的部分可能不同。相似性搜索可能針對已知的惡意代碼或入侵類型。隨后，網(wǎng)絡(luò)管理員可以針對此類黑客的已知源地址對第二部分3執(zhí)行精確搜索，所述第二部分3在這種情況下可以是包含地址信息的報頭。在化學(xué)示例中，可以使用對包括分子指紋的第一部分2的相似性搜索來發(fā)現(xiàn)一組分子；然后，可以對第二部分2中的元數(shù)據(jù)或從第二部分2中的元數(shù)據(jù)指針?biāo)甘镜脑粗袡z索的元數(shù)據(jù)執(zhí)行對相似性搜索結(jié)果的后續(xù)的精確搜索，例如關(guān)鍵詞搜索。

應(yīng)當(dāng)理解，在網(wǎng)絡(luò)管理員示例中，初始相似性搜索是對第二部分3執(zhí)行的，但是在化學(xué)示例中，相似性搜索是對第一部分2執(zhí)行的。

現(xiàn)在參考圖2和圖3。圖2示出了級聯(lián)搜索系統(tǒng)19，其包括相似性搜索器8、相似性搜索數(shù)據(jù)庫10、搜索結(jié)果數(shù)據(jù)庫12、精確搜索器9、精確搜索數(shù)據(jù)檢索器17、檢索數(shù)據(jù)數(shù)據(jù)庫(retrieved data database)15、搜索結(jié)果數(shù)據(jù)庫12和精確搜索結(jié)果數(shù)據(jù)庫18；圖3示出了作為多階段搜索的第二階段執(zhí)行的精確搜索的步驟。