基于布鲁姆过滤器距离的集合变动定量评估算法

布鲁姆过滤器(Bloom filter)对数据集合采用一个位串表示并能有效支持元素的哈希查找,是一种精简的信息表示方案,广泛应用于数据库、网络和分布式系统中.本文研究布鲁姆过滤器的序列分析方法,通过定义布鲁姆过滤器距离,用概率统计方法分析动态数据集合元素增加和删除的变化对布鲁姆过滤器的影响,提出了基于计数式布鲁姆过滤器距离的集合变动定量评估算法.理论分析和仿真实验表明,该评估算法评估准确率高达90%以上.     

面向缺失数据的布鲁姆近似成员查询算法

随着网络的发展，越来越多的场景需要在不完整数据下进行近似成员查询，传统成员查询的布鲁姆过滤器不能满足上述要求。提出面向缺失数据的布鲁姆近似查询算法，先对高维不完整数据的缺失部分进行预填充，通过PCA算法，将高维数据转换到低维数据，使用局部敏感哈希函数与标准哈希函数结合的方式将低维数据存储到布鲁姆过滤器中。使用两个真实数据集验证了所提算法的功能，所提面向缺失数据的布鲁姆近似查询算法，能有效地解决存在缺失数据的近似成员查询问题。     

计数布鲁姆过滤器代数运算

文中探讨计数布鲁姆过滤器的代数运算和集合运算的一致性关系,研究使用计数布鲁姆过滤器代数运算进行集合成员查询的性能.理论分析和实验结果表明,计数布鲁姆过滤器的并、交、补、减、异或运算产生的新过滤器依然保持计数布鲁姆过滤器的特征,支持元素的删除操作,不会出现假阴性,能用于集合并集、交集、补集、差集及对称差的成员查询;当使用两个原始的计数布鲁姆过滤器查询补集、差集及对称差元素时,会存在部分本来属于补集、差集或对称差的元素被判为不属于补集、差集或对称差的问题,而使用计数布鲁姆过滤器代数运算后的过滤器进行补集、差集及对称差成员查询,则不存在上述问题,空间效率能提高一倍,时间效率亦能显著地得到改善.计数布鲁姆过滤器代数运算的使用有利于进一步扩展计数布鲁姆过滤器的应用范围.譬如计数布鲁姆过滤器减运算可用作一种新的集合调和方法,用于分布式系统中大型文件的分发.     

一种面向覆盖查询的布鲁姆过滤器设计

在分布式系统中,覆盖查询对于保持文件的完整性以及数据的一致性有重要作用。虽然布鲁姆过滤器可以支持快速的元素从属查询,但是布鲁姆过滤器只能存储和表示离散的数据集合。为此,用前缀集合表示范围规则,并提出一个前缀编码的转化函数,将每一个前缀码转化为唯一对应的二进制串。为了支持覆盖查询,将计数布鲁姆过滤器与一组链表相结合,设计一个BFrange系统来存储包含规则标识以及具体存储元素的二元组。通过BFrange进行覆盖查询,使查询时间与存储的规则个数无关,复杂度仅为O(1)。仿真实验结果验证了BFrange能实现高效和准确的覆盖查询。     

布鲁姆过滤器查询算法

从理论和应用两方面系统地综述了布鲁姆过滤器查询算法迄今为止的主要研究成果,分析了目前布鲁姆过滤器查询算法的研究现状,最后展望了布鲁姆过滤器查询算法未来可能的研究方向.     

一种基于树形结构的布鲁姆过滤器

本文提出一种基于多层次结构的树形布鲁姆过滤器TBF。多层次结构是近年来布鲁姆过滤器及相关数据结构研究的热点。这一结构使得多层次的存储方式得以实现,减轻了片上存储的负担,而且也加快了片上查找的速度。TBF是针对BloomingTree算法存在的缺陷所改进的一种更高效的算法,它能够在低于CBF的空间需求的条件下实现与CBF相同的功能。实验证明:与BloomingTree算法相比,TBF能够有效地解决BloomingTree算法在逻辑索引时的错误问题,而且比BloomingTree算法时间上更加高效:在层数不变假阳性相同条件下,查询时间平均提高13.4%;在假阳性不变层数相同条件下,插入时间平均提高17.9%,删除时间平均提高12%。     

双布鲁姆过滤器法查询集合成员

探讨双布鲁姆过滤器查询法查询集合并集、交集、补集、差集或对称差成员的性能问题。理论分析和实验结果表明,双布鲁姆过滤器查询法能够较好地支持集合并集、交集、补集、差集及对称差的成员查询问题,其中双布鲁姆过滤器并集及交集查询不会产生假阴性,仅有少量假阳性的存在,而双布鲁姆过滤器补集、差集及对称差查询则除存在少量假阳性外,还存在少量假阴性。     

基于混淆布鲁姆过滤器的云外包隐私集合比较协议

针对基于混淆布鲁姆过滤器的隐私集合比较（PSI）协议中存在参与方信息获取不对等及协议不能有效应用于云环境等问题,将混淆布鲁姆过滤器算法与代理不经意传输协议相结合,提出了一种基于混淆布鲁姆过滤器和代理不经意传输的云外包隐私集合比较协议。首先,该算法通过引入混淆布鲁姆过滤器的概念,解决了传统标准布鲁姆过滤器产生误判的问题,进而达到高效存储和传输大数据的目的;其次,采用代理不经意传输协议,能够将复杂耗时的计算外包给云代理服务器,使得云租户不需实时在线、仅需进行少量计算;最后,在云外包隐私集合比较过程中,云租户间无需交互,能够公平地得到集合比较结果。理论分析和性能对比表明,该算法的通信复杂度和计算复杂度是线性的,并且协议是安全和有效的。     

基于布鲁姆过滤器的计算机动态取证技术研究

静态取证时效性不足,动态取证则可获得更为真实、实时的证据。动态取证最关键的是证据识别。证据识别本质上是对网络数据流进行分类,以判断其行为是合法还是非法。布鲁姆过滤器采用一个位串表示数据集合并有效支持元素的哈希查询,从而被广泛应用于包分类算法中。首先对标准布鲁姆过滤器算法进行分析,并对算法存在的缺陷进行改进。在此基础上,设计一个基于布鲁姆过滤器的分布式计算机动态取证系统,并采取安全有效措施对证据进行传送。实验表明:该系统能对网络攻击行为进行动态地检测,且检测准确率高、误判率低。     

布隆过滤器研究综述

布隆过滤器（BF）是一种基于哈希策略的二进制向量数据结构,凭借分摊哈希碰撞的思想、存在单向误判性的特点以及极小常数查询时间复杂度,常用于表示集合元素并作为进行集合元素查询操作的“加速器”。作为计算机工程中解决集合元素查询问题最好的数学工具,BF在网络工程、存储系统、数据库、文件系统、分布式系统等领域得到了广泛的应用和发展。近几年来,为了适用于各种硬件环境和应用场景,BF出现了大量基于改变结构、优化算法等思想的变种方案。随着大数据时代的发展,对BF自身特点和操作逻辑进行改进已经成为现有集合元素查询研究的一个重要方向。     

On‐demand transmission model for remote visualization using image‐based rendering

Interactive distributed visualization is an emerging technology with numerous applications. However, many of the present approaches to interactive distributed visualization have limited performance because they are based on the traditional polygonal processing graphics pipeline. In contrast, image‐based rendering uses multiple images of the scene instead of a three‐dimensional geometrical representation, and so has the key advantage that the final output is independent of the scene complexity and depends on the desired final image resolution. Furthermore, the discrete nature of the light field dataset maps well to a hybrid solution, which can overcome the identified drawbacks. In this paper, we propose an on‐demand solution for efficiently transmitting visualization data to remote users/clients. This is achieved through sending selected parts of the dataset based on the current client viewpoint, and is done instead of downloading a complete replica of the light field dataset to each client, or remotely sending a single rendered view back from a central server to the user each time the user updates their viewing parameters. The on‐demand approach shows stable performance as the number of clients increases because the load on the server and the network traffic are reduced. Furthermore, detailed performance studies show that the proposed scheme outperforms the current solution in terms of interactivity measured in frames per second. Copyright © 2012 John Wiley & Sons, Ltd.     

一种工业分布式实时数据库系统的设计与实现

为了满足企业中大型联合控制系统(如千万吨炼油和百万吨乙烯ODS系统、大型SCADA系统核心数据库、大型电力信息系统SIS等大型应用)对实时数据和历史数据查询的点数规模需求,设计了一种分布式实时数据库系统。该系统通过分布式通讯平台,确保了多台实时数据服务器可以分布式部署在各种复杂的网络环境;基于哈希表的数据点分配,确保了实时数据库运行时能快速转换数据点的逻辑位置到物理位置;分布式文件存储系统确保了实时数据库系统可以连续保存多年的工艺数据,而不必担心数据存储的可靠性、存储空间耗尽等问题。     

并行分布式计算机系统与网络的内在联系分析

分布处理结构在计算机内部从单处理器到多处理器发展，以后逐步向多机系统和计算机网络系统发展，但此时计算机网络的分布处理能力已经有一些重要的本质性变化和发展，具有不同的结构特点和应用环境，文章对并行分布式计算机系统与网络的内在联系进行了详细分析和探讨。     

分布式实时嵌入式中间件的调度体系

在实时CORBA1.2的基础上扩展了一种分布式调度体系,这种调度体系可以获取全局信息,从而本地调度器可以获得更加准确的调度信息.这里只讨论本地调度器使用截止期调度策略的情况,因此这种调度器可以使得分布式任务在截止期之前完成的可能性增大.如果本地调度器使用其他的调度算法,可以在这种体系中给出相应的机制来提供更准确的调度信息.文中主要描述了这种调度体系的设计与实现.     

Distributed programming languages: design and implementation

Considerable discussion has appeared in recent literature about ‘distributed programming’. One area of discussion concerns the design of programming languages which support distributed algorithms. This paper examines the important issues in programming language design for distributed computing, and presents an example of a language philosophy which supports program development for a distributed environment. It also discusses experiences with the STARMOD distributed programming language.     

Message delay and DisCSP search algorithms

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been recently shown in experimental studies of asynchronous backtracking algorithms (Bejar et al., Artif. Intell., 161:117–148, 2005; Silaghi and Faltings, Artif. Intell., 161:25–54, 2005). To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the non-concurrent number of steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. Two families of distributed search algorithms on DisCSPs are investigated. Algorithms that run a single search process, and multiple search processes algorithms. The two families of algorithms are described and associated with existing algorithms. The performance of three representative algorithms of these two families is measured on randomly generated instances of DisCSPs with delayed messages. The delay of messages is found to have a strong negative effect on single search process algorithms, whether synchronous or asynchronous. Multi search process algorithms, on the other hand, are affected very lightly by message delay.     

A modified genetic algorithm for distributed scheduling problems

Genetic algorithms (GAs) have been widely applied to the scheduling and sequencing problems due to its applicability to different domains and the capability in obtaining near-optimal results. Many investigated GAs are mainly concentrated on the traditional single factory or single job-shop scheduling problems. However, with the increasing popularity of distributed, or globalized production, the previously used GAs are required to be further explored in order to deal with the newly emerged distributed scheduling problems. In this paper, a modified GA is presented, which is capable of solving traditional scheduling problems as well as distributed scheduling problems. Various scheduling objectives can be achieved including minimizing makespan, cost and weighted multiple criteria. The proposed algorithm has been evaluated with satisfactory results through several classical scheduling benchmarks. Furthermore, the capability of the modified GA was also tested for handling the distributed scheduling problems.     

分布式追踪技术综述

随着分布式软件系统在各个行业的广泛应用,如何提升系统运维效率,保障其服务的可靠与稳定,得到了学术界与工业界的关注.分布式软件系统其规模庞大、结构复杂、持续更新且大量服务请求并发执行的特点,给分布式软件系统的运维任务带来了严峻的挑战.传统的以组件/节点/进程/线程为中心的系统监控与追踪方法难以支持分布式软件的故障诊断、性能调优、系统理解等运维任务.分布式追踪技术识别并提取出分布式软件系统因处理单个服务请求所产生的因果相关的事件,以服务请求为中心对分布式软件系统的行为进行精准、细粒度地刻画,对提高分布式软件系统的运维效率有重要意义.对分布式追踪技术的研究与应用进行了综述,从追踪数据获取、请求事件提取、因果关系判断及请求路径表示这四个方面总结了分布式追踪技术的现状;同时以基于请求执行路径的故障诊断和性能分析为例,讨论了学术界对分布式追踪技术的应用研究;最后,对分布式追踪技术的数据读写依赖问题、通用性问题和评价问题进行了探讨并对未来的研究方向进行了展望.