计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2007年
4期
597-607
,共11页
谢鲲%闵应骅%张大方%谢高岗%文吉刚
謝鯤%閔應驊%張大方%謝高崗%文吉剛
사곤%민응화%장대방%사고강%문길강
分档布鲁姆过滤器%计算机网络%分布式计算%分布式消息系统%集合元素查询
分檔佈魯姆過濾器%計算機網絡%分佈式計算%分佈式消息繫統%集閤元素查詢
분당포로모과려기%계산궤망락%분포식계산%분포식소식계통%집합원소사순
布鲁姆过滤器是一种能够简洁地表示集合并支持集合查询的数据结构,广泛应用于数据库、网络和分布式系统中.针对现有的布鲁姆过滤器没有考虑查询失效代价这一缺陷,文中提出一种新的代价敏感的分档布鲁姆过滤器查询算法.它将元素根据不同的查询代价分为不同的子集,通过考查每档子集最低查询失效率的关系,建立由每档子集合最低查询失效假阳性概率表示的集合最低查询失效总代价目标函数,使用类目标函数梯度遗传算法获得每档的最优Hash函数个数ki,完成集合到向量的映射与查找.仿真实验结果表明,使用新结构的查询算法和标准布鲁姆过滤器算法相比,所用的查询计算时间基本相同,因为区分对待集合元素,查询失效总代价仅为标准算法的27%.
佈魯姆過濾器是一種能夠簡潔地錶示集閤併支持集閤查詢的數據結構,廣汎應用于數據庫、網絡和分佈式繫統中.針對現有的佈魯姆過濾器沒有攷慮查詢失效代價這一缺陷,文中提齣一種新的代價敏感的分檔佈魯姆過濾器查詢算法.它將元素根據不同的查詢代價分為不同的子集,通過攷查每檔子集最低查詢失效率的關繫,建立由每檔子集閤最低查詢失效假暘性概率錶示的集閤最低查詢失效總代價目標函數,使用類目標函數梯度遺傳算法穫得每檔的最優Hash函數箇數ki,完成集閤到嚮量的映射與查找.倣真實驗結果錶明,使用新結構的查詢算法和標準佈魯姆過濾器算法相比,所用的查詢計算時間基本相同,因為區分對待集閤元素,查詢失效總代價僅為標準算法的27%.
포로모과려기시일충능구간길지표시집합병지지집합사순적수거결구,엄범응용우수거고、망락화분포식계통중.침대현유적포로모과려기몰유고필사순실효대개저일결함,문중제출일충신적대개민감적분당포로모과려기사순산법.타장원소근거불동적사순대개분위불동적자집,통과고사매당자집최저사순실효솔적관계,건립유매당자집합최저사순실효가양성개솔표시적집합최저사순실효총대개목표함수,사용류목표함수제도유전산법획득매당적최우Hash함수개수ki,완성집합도향량적영사여사조.방진실험결과표명,사용신결구적사순산법화표준포로모과려기산법상비,소용적사순계산시간기본상동,인위구분대대집합원소,사순실효총대개부위표준산법적27%.
