[發(fā)明專利]元素從概率數(shù)據(jù)結(jié)構(gòu)的刪除

有效

• 申請?zhí)枺?/td>: 201680051926.0
• 申請日: 2016-09-09
• 公開（公告）號: CN108027826B
• 公開（公告）日: 2022-05-17
• 發(fā)明（設(shè)計(jì)）人: G·A·魯賓;G·B·羅斯
• 申請（專利權(quán)）人: 亞馬遜科技有限公司
• 主分類號: G06F16/9035
• 分類號: G06F16/9035
• 代理公司: 廣州嘉權(quán)專利商標(biāo)事務(wù)所有限公司 44205
• 代理人: 鄭勇

一種計(jì)算機(jī)系統(tǒng)接收將條目從概率數(shù)據(jù)結(jié)構(gòu)移除的請求。響應(yīng)于所述請求，所述計(jì)算機(jī)系統(tǒng)查詢所述概率數(shù)據(jù)結(jié)構(gòu)以確定所述概率數(shù)據(jù)結(jié)構(gòu)內(nèi)所述條目的當(dāng)前迭代值。所述當(dāng)前迭代值指示所述條目的狀態(tài)，使得第一狀態(tài)對應(yīng)于所述條目是集合的成員并且第二狀態(tài)對應(yīng)于使所述條目從所述集合缺失。由于所述當(dāng)前迭代值表示所述條目是所述集合的成員，所述計(jì)算機(jī)系統(tǒng)使所述當(dāng)前迭代值增量以生成對應(yīng)于使所述條目從所述集合缺失的新的迭代值。所述計(jì)算機(jī)系統(tǒng)使用所述新的迭代值和所述條目來生成然后被添加至所述概率數(shù)據(jù)結(jié)構(gòu)的新的輸出值。

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

本申請出于所有目的以引用的方式并入2015年9月9日提交的題為“DELETION OFELEMENTS FROM A PROBABILISTIC DATA STRUCTURE”(代理人案號0097749-543US0)的序列號為14/849,481的美國專利申請，2015年9月9日提交的、題為“VERIFICATION OF DATA SETCOMPONENTS USING DIGITALLY SIGNED PROBABILISTIC DATA STRUCTURES”(代理人案號0097749-545US0)的序列號為14/849,488的美國專利申請和2015年9月9日提交的、題為“SIGNATURE VERIFICATION FOR DATA SET COMPONENTS USING PROBABILISTIC DATASTRUCTURES”(代理人案號0097749-588US0)的序列號為14/849,493的美國專利申請的全部公開內(nèi)容。

背景技術(shù)

布隆過濾器(Bloom filter)和其他概率數(shù)據(jù)結(jié)構(gòu)經(jīng)常用來快速地和緊密地確定某一元素是否是元素集合的一部分。例如，數(shù)據(jù)庫的管理員可將數(shù)據(jù)條目添加至布隆過濾器中，所述布隆過濾器然后可用來通過識別數(shù)據(jù)庫條目是否可能在數(shù)據(jù)庫內(nèi)或確切地不在數(shù)據(jù)庫內(nèi)來支持?jǐn)?shù)據(jù)庫查詢。由于添加至布隆過濾器的條目以所產(chǎn)生的值僅將布隆過濾器內(nèi)的位從零觸發(fā)至一的方式被散列化，布隆過濾器具有存儲器高效的固有優(yōu)點(diǎn)。然而，一旦已經(jīng)將條目添加至布隆過濾器，條目就不可被移除，因?yàn)槭共悸∵^濾器位從一改變至零可影響布隆過濾器內(nèi)的其他條目，從而犧牲布隆過濾器的完整性。使用針對每個布隆過濾器片段具有n位計(jì)數(shù)器的計(jì)數(shù)型過濾器可用來將條目從布隆過濾器移除，但也犧牲了存儲器效率，因?yàn)椴悸∵^濾器的每個片段現(xiàn)可包括許多更多的位值，從而增加布隆過濾器的大小。

附圖說明

將參考附圖描述根據(jù)本公開的各個實(shí)施例，在附圖中：

圖1示出可實(shí)現(xiàn)各個實(shí)施例的環(huán)境的說明性實(shí)例；

圖2示出根據(jù)至少一個實(shí)施例的執(zhí)行迭代查詢來確定條目是否存在于布隆過濾器內(nèi)的環(huán)境的說明性實(shí)例；

圖3示出根據(jù)至少一個實(shí)施例的覆蓋數(shù)據(jù)庫屬性和值的鍵值對的條目的布隆過濾器被數(shù)字地簽名的環(huán)境的說明性實(shí)例；

圖4示出根據(jù)至少一個實(shí)施例的將數(shù)據(jù)庫屬性和值的鍵值對的數(shù)字簽名添加至布隆過濾器的環(huán)境的說明性實(shí)例；

圖5示出根據(jù)至少一個實(shí)施例的用于至少部分地基于新的條目的當(dāng)前迭代將條目添加至布隆過濾器的過程的說明性實(shí)例；

圖6示出根據(jù)至少一個實(shí)施例的用于至少部分地基于條目的當(dāng)前迭代將條目從布隆過濾器移除的過程的說明性實(shí)例；

圖7示出根據(jù)至少一個實(shí)施例的用于執(zhí)行二分搜索來識別布隆過濾器內(nèi)條目的當(dāng)前迭代的過程的說明性實(shí)例；

圖8示出根據(jù)至少一個實(shí)施例的用于向布隆過濾器添加數(shù)據(jù)庫鍵值對并且響應(yīng)于對數(shù)據(jù)庫記錄簽名的請求來對布隆過濾器數(shù)字地簽名的過程的說明性實(shí)例；

圖9示出根據(jù)至少一個實(shí)施例的用于響應(yīng)于對數(shù)據(jù)庫記錄簽名的請求來向布隆過濾器添加數(shù)據(jù)庫鍵值對的數(shù)字簽名的過程的說明性實(shí)例；并且

圖10示出可實(shí)現(xiàn)各個實(shí)施例的環(huán)境的說明性實(shí)例。

具體實(shí)施方式