科创中国

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

原文链接：万方

• 作者：

  邹志文,寇爱军,鞠时光,陈继明,王政辉

• 摘要：

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

• 关键词：

  过滤器 查询 索引 聚合 访问 误判率 Top-κ filter query index aggregate access false positive rate Top-κ

• 作者单位：

  江苏大学计算机科学与通信工程学院,江苏镇江212013

• 基金项目：

  国家自然科学基金资助项目（60773049）;江苏省研究生科研创新计划项目（CX07B_125z）;江苏省教育厅自然科学基金资助项目（11KJB520003）;江苏大学高级专业人才科研基金资助项目（09JDG035）

• 来源期刊：

  江苏大学学报(自然科学版)

• 年，卷(期)：

  201233005