基于三维分档布鲁姆过滤器的Top-k查询算法

• 作者: 寇爱军 王政辉 邹志文 陈继明 鞠时光
• 来源期刊: 江苏大学学报（自然科学版）
• 学科: 航空航天
• 关键词: 过滤器 查询 索引 聚合 访问 误判率 Top-k
• 年，卷（期）: 2012,（5）
• 页码范围: 555-560
• 分类号: V423/443
• 字数: 5456字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-7775.2012.05.012

摘要

针对NRA算法和BPA算法查询效率不高、重复访问数据的问题,提出了一种基于三维分档布鲁姆过滤器表(TF)的Top-k查询算法(TKBFP).该算法使用TF对数据进行处理,以较低的误判率获得较高的访问效率并降低了内存消耗,利用最优位置索引策略,避免重复访问数据对象.对TKBFP算法进行了严格的语义定义,推导出每一维BF中需要的哈希函数个数；以自主开发的Java程序为仿真平台,对TKBFP算法进行了试验,并对算法执行效率和存储性能进行评价.试验结果表明,该算法能够避免重复访问数据对象,并能以较低的误判率实现大规模数据的高效查询处理.与NRA和BPA相比,当属性列表超过4个时,开销明显降低,适合面向大规模数据的查询处理应用.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	鞠时光	江苏大学计算机科学与通信工程学院	159	1685	21.0	34.0
2	陈继明	江苏大学计算机科学与通信工程学院	23	45	3.0	6.0
3	邹志文	江苏大学计算机科学与通信工程学院	29	264	7.0	16.0
4	寇爱军	江苏大学计算机科学与通信工程学院	2	4	1.0	2.0
5	王政辉	江苏大学计算机科学与通信工程学院	2	5	1.0	2.0