联合多维布鲁姆过滤器查询算法

分析了现有多维布鲁姆过滤器查询算法(MDBF)工作原理,提出了一种改进的两步表示和查询的联合多维布鲁姆过滤器(CMDBF)查询算法.CMDBF新增一个用于表示元素整体的联合布鲁姆过滤器CBF,CMDBF中元素表示和查找分两步进行.将MDBF的各属性的表示和查询作为第一步,第二步联合元素所有属性域,利用CBF完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,CMDBF能够支持多维集合元素的简洁表示和查询,相比MDBF查询误判率降低明显.     

基于移动指针的数据流冗余消除算法

针对数据流的动态特性,提出了一种基于移动指针的数据流冗余消除算法—SKIP Bloom filter,其核心思想是通过动态指针和双Bloom filter来区分历史数据映射与当前数据映射,从而有效提升了算法的性能和准确度。理论证明,它具有O(n)的时间复杂度与O(1-(1-1/(2 m))w-k)k的假阳性误判率。实验结果表明,算法在实际网络环境中与已有算法相比,准确度提高了2-12倍。     

面向大数据处理的高精度多维计数布鲁姆过滤器

分析了现有多维布鲁姆过滤器查询算法的工作原理和特点,针对大数据处理特点提出了一种基于双射函数的高精度多维计数布鲁姆过滤器(AMD-CBF)查询算法.AMD-CBF中元素表示和查找分两步进行,第1步将元素各属性哈希映射到各自对应的高精度计数布鲁姆过滤器(A-CBF)中;第2步将元素的所有属性通过双射函数转换为一个值来表示元素整体信息,然后将这个值哈希映射到联合计数布鲁姆过滤器中(C-CBF),完成元素整体的表示和查询确认.理论分析和仿真实验结果表明,AMD-CBF能够支持多维集合元素的高效表示和查询及删除,相比同类研究查询假阳性降低明显,查询精度大幅度提高.     

数据库优化策略分析

从范式优化、索引优化和查询优化三个方面对数据库的优化设计方法进行分析探讨。在逻辑设计阶段,要按照范式优化的具体要求来设计数据库逻辑结构,比较其优劣从而选择更好的方案;在数据库物理设计阶段,在有关属性或属性的组合上建立索引时要根据索引优化中的具体要求来进行,使数据库物理结构得以优化;在数据库查询阶段,优化数据查询语句,以提高SQL语句的执行效率。     

一种基于密度网格索引的k-最近邻查询算法

基于位置的服务的迅速发展对服务响应的效率提升和成本控制提出了更高的要求,本文提出了一种基于密度网格索引的k-最近邻查询算法,该算法首先利用矩形的几何特点获取一系列候选搜索半径,随后根据移动对象的密度分布情况选择适当的候选搜索半径进行距离过滤,尽量减少不必要的内存索引单元和磁盘索引单元的访问.实验表明,实现了本文算法的密度网格索引在k-最近邻查询的查询效率上与ST²B-tree不相上下,而查询的I/O代价与其他索引结构相比有明显的优势.     

一种基于语义相似度的P2P数据查询方法

目前P2P网络中数据查询在语义方面的研究较少,而基于DHT的数据检索只支持准确查询,导致查询准确率不高,但是好的索引项的建立会给查询带来很大的方便。本文结合了RDF和Word Net在语义方面的特点提出了一种新的简易RDF概念列表来表示文档,并通过计算语义相似度来决定输出结果的P2P数据查询方法。仿真实验证明本文方法可以较好的提高查询成功率。     

有向图上k步可达查询处理

给定一个有向图,一个k步可达查询u→?kv用来回答在该图中是否存在一条从顶点u到顶点v且长度不大于k的有向路径。k步可达查询是一种基本的图操作并在过去十年间被广泛地研究。已有的k步可达查询算法仍存在许多弊端,例如不可达查询效率低,索引规模大和索引构建时间长等。本文针对上述问题提出了2种优化方法,分别是基于互逆拓扑序号以及基于等价顶点的图压缩方法.前者提高了不可达查询的效率,后者减少了索引规模和索引构建时间。实验结果表明,本文提出的方法可以有效地处理k步可达查询,并支持大规模数据的处理。     

基于Kudu的大数据平台实时业务处理能力提升方案

针对目前Hadoop大数据平台实时业务处理能力较差的难点，研究了国际最先进的Kudu列存储作为HDFS块存储的有效补充的理论，阐述了利用Kudu和Spark提供的主键索引和内存加速，有效解决大数据平台无法支持实时入库、增量更新和SQL关联查询等业务痛点的技术实现方法。实验效果证明了方法对提升大数据平台实时业务处理能力的作用。     

超对等网络中的轮廓查询优化

轮廓查询是近年来信息服务领域的一个研究重点和热点.现有的三阶段算法TPAOSS (Three-Phase Algorithm for Optimizing Skyline Scalar)至少存在如下两个缺陷:(1)在TPAOSS算法的第3阶段中,当网络节点上的对象个数较多时,Bloom filter的长度将呈指数级增长,从而严重影响获取子空间重复值的效率以及占用内存空间的大小;(2)TPAOSS算法只考虑预处理阶段的时间代价,而没有考虑各网络节点进行局部或全局子空间轮廓查询计算的效率.为此,提出一种适合超对等网络(Super-Peer Architecture,SPA)的子空间轮廓查询方法EPSSQDN (Efficient Processing of Subspace Skyline Queries in Distributed Networks).EPSSQDN算法有效解决了TPAOSS算法的的两个主要性能问题,并且显著提高了SPA网络中的子空间轮廓查询处理的效率.此外,为了能够进一步降低子空间上轮廓查询的时间开销以及网络节点间的数据传输量,我们给出新颖且有效的优化策略.实验结果表明,EPSSQDN算法比TPAOSS算法更能够缩短SPA网络中子空间轮廓查询的时间开销.     

基于多维计数型布鲁姆过滤器的大流检测机制

高速网络环境中,实时、准确地提取大流量对于网络安全和网络管理具有重要意义。该文针对传统的流量测量方法受计算资源和存储资源的限制,提出了一种基于多维计数型布鲁姆过滤器(Multi-Dimensional Counting Bloom Fliter, MDCBF)的大流检测机制。它将1维的计数型布鲁姆过滤器(Counting Bloom Fliter, CBF)结构,扩展到支持多维业务流表示、查询和统计计数的MDCBF结构。基于Apriori原理,通过对MDCBF实施重正化,实现了用户自定义的大流检测。并能自适应地配置CBF参数,允许测量误差控制在预定义的范围内。基于计算机产生的模拟数据和实际互联网数据进行了仿真实验,结果显示:该方法既能获得较小的测量误差,又能获得较高的空间利用率。     

布鲁姆过滤器代数运算探讨

 本文探讨布鲁姆过滤器的代数运算和集合查询的关系,定义布鲁姆过滤器的"并","交","异或","补","差"代数运算,从理论和实验两方面分析布鲁姆过滤器的代数运算和集合代数运算并集,交集,异或集,补集,差集的元素查询关系.理论分析和实验结果表明,布鲁姆过滤器的"并","交"运算能够支持集合并集交集的元素查询,这一结论可以简化利用布鲁姆过滤器进行的系统设计.     

Compressed Bloom filters

A Bloom filter is a simple space-efficient randomized data structure for representing a set in order to support membership queries. Although Bloom filters allow false positives, for many applications the space savings outweigh this drawback when the probability of an error is sufficiently low. We introduce compressed Bloom filters, which improve performance when the Bloom filter is passed as a message, and its transmission size is a limiting factor. For example, Bloom filters have been suggested as a means for sharing Web cache information. In this setting, proxies do not share the exact contents of their caches, but instead periodically broadcast Bloom filters representing their caches. By using compressed Bloom filters, proxies can reduce the number of bits broadcast, the false positive probability, and/or the amount of computation per lookup. The cost is the processing time for compression and decompression, which can use simple arithmetic coding, and more memory use at the proxies, which utilize the larger uncompressed form of the Bloom filter.     

一种基于查询事件的域名服务器日志模型

提出了一种基于查询事件的日志模型,采用查询/应答日志匹配的方法完整的记录了一次查询事件,利用内存数据结构提高了海量数据写入的I/O效率;在日志分析过程中对日志文件建立二维哈希索引,利用布隆过滤器减少磁盘I/O次数,提高了分析效率.     

拆分型Bloom Filter

Bloom Filter对数据集合采用一个位串表示并能有效支持集合元素的哈希查找操作.在对Bloom Filter及其改进型进行综述性分析研究并探讨它们的实用性之后,本文提出了使用位矩阵表示数据集合的拆分型Bloom Filter并对其作了分析比较研究,以允许集合元素不断增加的分布式系统应用模型为例,证明它能缓解增长问题并能有效节省全局的集合表示空间需求量.     

An Efficient PAB‐Based Query Indexing for Processing Continuous Queries on Moving Objects

Existing methods to process continuous range queries are not scalable. In particular, as the number of continuous range queries on a large number of moving objects becomes larger, their performance degrades significantly. We propose a novel query indexing method called the projected attribute bit (PAB)‐based query index. We project a two‐dimensional continuous range query on each axis to get two one‐dimensional bit lists. Since the queries are transformed to bit lists and query evaluation is performed by bit operations, the storage cost of indexing and query evaluation time are reduced significantly. Through various experiments, we show that our method outperforms the containment‐encoded squares‐based indexing method, which is one of the most recently proposed methods.     

A method to protect Cuckoo filters from soft errors

Soft errors that corrupt the value of bits stored in registers or memories are a major issue for modern electronic systems. To ensure that they do not cause failures, error detection and correction codes are commonly used to protect memories. When memories are used for a specific application, sometimes it is possible to optimize the protection based on the knowledge of the application. One example is the memories used in network devices for packet processing. In particular, the protection of approximate membership check structures such as Bloom filters has been recently studied showing that it is possible to optimize the protection. Cuckoo filters are an alternative to Bloom filters for approximate membership check that has been recently proposed. Cuckoo filters are interesting as they are competitive in terms of memory usage for low false positive rates and also support the removal of elements. In this paper, the protection of Cuckoo filters against soft errors is studied showing that it can be enhanced by exploiting its structure and using the knowledge of the effects on an error in a Cuckoo filter.     

基于深度布隆过滤器的NDN网络三级名字查找方法

为提高命名数据网络(Name Data Networking, NDN)路由过程中内容名字查找的效率,该文提出一种基于深度布隆过滤器的3级名字查找方法。该方法使用长短记忆神经网络(Long Short Term Memory, LSTM)与标准布隆过滤器相结合的方法优化名字查找过程;采用3级结构优化内容名字在内容存储器(Content Store, CS)、待定请求表(Pending Interest Table, PIT)中的精确查找过程,提高查找精度并降低内存消耗。从理论上分析了3级名字查找方法的假阳性率,并通过实验验证了该方法能够有效节省内存、降低查找过程的假阳性。