一种基于bloom-filters的半连接查询优化算法

以传输费用最小为目的,提出一种新的查询优化算法。该算法以连接属性为关键字,利用半连接关系建立bloom-filters,在半连接关系间相互传送bloom-filters,从而缩减大部分不参与连接的元组,最终形成了计算结果表。通过站点间传送计算结果表来缩减连接关系,半连接的准确性比估算连接结果高,半连接查询优化算法能较准确地做出下一步的连接;新的查询优化算法能有效地得到连接操作的执行计划,从而减少了传输费用。

Comparing Set Reconciliation Methods Based on Bloom Filters and Their Variants

Set reconciliation between two nodes is widely used in network applications. The basic idea is that each member of a node pair has an object set and seeks to deliver its unique objects to the other member. The Standard Bloom Filter （SBF） and its variants, such as the Invertible Bloom Filter （IBF）, are effective approaches to solving the set reconciliation problem. The SBF-based method requires each node to represent its objects using an SBF, which is exchanged with the other node. A receiving node queries the received SBF against its local objects to identify the unique objects. Finally, each node exchanges its unique objects with the other node in the node pair. For the IBF- based method, each node represents its objects using an IBF, which is then exchanged. A receiving node subtracts the received IBF from its local IBF so as to decode the different objects between the two sets. Intuitively, it would seem that the IBF-based method, with only one round of communication, entails less communication overhead than the SBF-based method, which incurs two rounds of communication. Our research results, however, indicate that neither of these two methods has an absolute advantages over the others. In this paper, we aim to provide an in-depth understanding of the two methods, by evaluating and comparing their communication overhead. We find that the best method depends on parameter settings. We demonstrate that the SBF-based method outperforms the IBF-based method in most cases. But when the number of different objects in the two sets is below a certain threshold, the IBF-based method outperforms the SBF-based method.

Hot Data Identification with Multiple Bloom Filters： Block-Level Decision vs I/O Request-Level Decision

Hot data identification is crucial for many applications though few investigations have examined the subject. All existing studies focus almost exclusively on frequency. However, effectively identifying hot data requires equally considering recency and frequency. Moreover, previous studies make hot data decisions at the data block level. Such a fine-grained decision fits particularly well for flash-based storage because its random access achieves performance comparable with its sequential access. However, hard disk drives （HDDs） have a significant performance disparity between sequential and random access. Therefore, unlike flash-based storage, exploiting asymmetric HDD access performance requires making a coarse-grained decision. This paper proposes a novel hot data identification scheme adopting multiple bloom filters to efficiently characterize recency as well as frequency. Consequently, it not only consumes 50% less memory and up to 58% less computational overhead, but also lowers false identification rates up to 65% compared with a state-of-the-art scheme. Moreover, we apply the scheme to a next generation HDD technology, i.e., Shingled Magnetic Recording （SMR）, to verify its effectiveness. For this, we design a new hot data identification based SMR drive with a coarse-grained decision. The experiments demonstrate the importance and benefits of accurate hot data identification, thereby improving the proposed SMR drive performance by up to 42%.

BloomRouter:A Framework for Dissemination of Compressed XML Stream

As our best knowledge, in the Publish/Subscribe application environment, few research work has been done on the dissemination and routing of compressed XML （extended markup language） data. A high-speed compressed XML data routing and dissemination framework BloomRouter is proposed. In BloomRouter, a Bloom Filter based prefilte ring mechanism is used to filter out compressed XML elements that users do not care; after that an interval tree dis seminator forwards target elements to the corresponding end users by matching the incomming compressed XML elements with indexed users＇ query regions. Based on this framework, we can efficiently filter/query the compressed incoming XML data, and then route the query result to the corresponding subseriber.

L-priorities Bloom Filter: A New Member of the Bloom Filter Family

A Bloom filter is a space-efficient data structure used for concisely representing a set as well as membership queries at the expense of introducing false positive. In this paper, we propose the L-priorities Bloom filter （LPBF） as a new member of the Bloom filter （BF） family, it uses a limited multidimensional bit space matrix to replace the bit vector of standard bloom filters in order to support different priorities for the elements of a set. We demonstrate the time and space complexity, especially the false positive rate of LPBF. Furthermore, we also present a detailed practical evaluation of the false positive rate achieved by LPBF. The results show that LPBF performs better than standard BFs with respect to false positive rate.

基于BLOOM FILTER过滤算法的重复数据删除技术的研究与改进

随着企业数据信息量的不断地增加,海量数据信息的存储和不断备份给企业的存储空间带来了巨大的存储压力。该文深入研究重复数据删除技术,并针对目前重复数据删除技术中存在的数据丢失及性能低等问题以及BLOOM FILTER算法流程和重复数据删除策略的分析和研究,提出了一种重复数据删除技术优化模型。测试分析表明,该优化模型实现了高效和安全的重复数据删除功能,节省了企业内部存储空问的存储成本开销。

The Impact of Check Bits on the Performance of Bloom Filter

Bloom filter(BF)is a space-and-time efficient probabilistic technique that helps answermembership queries.However,BF faces several issues.The problems with traditional BF are generally two.Firstly,a large number of false positives can return wrong content when the data is queried.Secondly,the large size of BF is a bottleneck in the speed of querying and thus uses large memory.In order to solve the above two issues,in this article,we propose the check bits concept.From the implementation perspective,in the check bits approach,before saving the content value in the BF,we obtain the binary representation of the content value.Then,we take some bits of the content value,we call these the check bits.These bits are stored in a separate array such that they point to the same location as the BF.Finally,the content value(data)is stored in the BF based on the hash function values.Before retrieval of data from BF,the reverse process of the steps ensures that even if the same hash functions output has been generated for the content,the check bits make sure that the retrieval does not depend on the hash output alone.This thus helps in the reduction of false positives.In the experimental evaluation,we are able to reduce more than 50%of false positives.In our proposed approach,the false positives can still occur,however,false positives can only occur if the hash functions and check bits generate the same value for a particular content.The chances of such scenarios are less,therefore,we get a reduction of approximately more than 50%false positives in all cases.We believe that the proposed approach adds to the state of the art and opens new directions as such.

Cross-Domain Data Traceability Mechanism Based on Blockchain

With the application and development of blockchain technology,many problems faced by blockchain traceability are gradually exposed.Such as cross-chain information collaboration,data separation and storage,multisystem,multi-security domain collaboration,etc.To solve these problems,it is proposed to construct trust domains based on federated chains.The public chain is used as the authorization chain to build a cross-domain data traceability mechanism applicable to multi-domain collaboration.First,the architecture of the blockchain cross-domain model is designed.Combined with the data access strategy and the decision mechanism,the open and transparent judgment of cross-domain permission and cross-domain identity authentication is realized.And the public chain consensus node election mechanism is realized based on PageRank.Then,according to the characteristics of a nonsingle chain structure in the process of data flow,a data retrievalmechanism based on a Bloom filter is designed,and the cross-domain traceability algorithm is given.Finally,the safety and effectiveness of the traceability mechanism are verified by security evaluation and performance analysis.

基于并行BP神经网络的路由查找算法

结合Bloom-filter算法和并行反向传播神经网络,提出了一种新的基于并行神经网络的路由查找算法(BFBP)。该算法满足路由查找的需求,只需学习路由条目的网络ID,且易于扩展到IPv6地址查询。研究结果表明,相比于己有的神经网络路由查找方法,该算法需要学习的条目数平均减少了520倍,提高了学习效率,为神经网络应用于路由查找创造了有利条件。

Implementation and Validation of the Optimized Deduplication Strategy in Federated Cloud Environment

Cloud computing technology is the culmination of technical advancements in computer networks,hardware and software capabilities that collectively gave rise to computing as a utility.It offers a plethora of utilities to its clients worldwide in a very cost-effective way and this feature is enticing users/companies to migrate their infrastructure to cloud platform.Swayed by its gigantic capacity and easy access clients are uploading replicated data on cloud resulting in an unnecessary crunch of storage in datacenters.Many data compression techniques came to rescue but none could serve the purpose for the capacity as large as a cloud,hence,researches were made to de-duplicate the data and harvest the space from exiting storage capacity which was going in vain due to duplicacy of data.For providing better cloud services through scalable provisioning of resources,interoperability has brought many Cloud Service Providers(CSPs)under one umbrella and termed it as Cloud Federation.Many policies have been devised for private and public cloud deployment models for searching/eradicating replicated copies using hashing techniques.Whereas the exploration for duplicate copies is not restricted to any one type of CSP but to a set of public or private CSPs contributing to the federation.It was found that even in advanced deduplication techniques for federated clouds,due to the different nature of CSPs,a single file is stored at private as well as public group in the same cloud federation which can be handled if an optimized deduplication strategy be rendered for addressing this issue.Therefore,this study has been aimed to further optimize a deduplication strategy for federated cloud environment and suggested a central management agent for the federation.It was perceived that work relevant to this is not existing,hence,in this paper,the concept of federation agent has been implemented and deduplication technique following file level has been used for the accomplishment of this approach.

A Trusted and Privacy-Preserving Carpooling Matching Scheme in Vehicular Networks

With the rapid development of intelligent transportation, carpooling with the help of Vehicular Networks plays an important role in improving transportation efficiency and solving environmental problems. However, attackers usually launch attacks and cause privacy leakage of carpooling users. In addition, the trust issue between unfamiliar vehicles and passengers reduces the efficiency of carpooling. To address these issues, this paper introduced a trusted and privacy-preserving carpooling matching scheme in Vehicular Networks (TPCM). TPCM scheme introduced travel preferences during carpooling matching, according to the passengers’ individual travel preferences needs, which adopted the privacy set intersection technology based on the Bloom filter to match the passengers with the vehicles to achieve the purpose of protecting privacy and meeting the individual needs of passengers simultaneously. TPCM scheme adopted a multi-faceted trust management model, which calculated the trust value of different travel preferences of vehicle based on passengers’ carpooling feedback to evaluate the vehicle’s trustworthiness from multi-faceted when carpooling matching. Moreover, a series of experiments were conducted to verify the effectiveness and robustness of the proposed scheme. The results show that the proposed scheme has high accuracy, lower computational and communication costs when compared with the existing carpooling schemes.

High Speed and Low Power Architecture for Network Intrusion Detection System

The tremendous growth in the field of modern communication and network systems places demands on the security. As the network complexity grows, the need for the automated detection and timely alert is required to detect the abnormal activities in the network. To diagnose the system against the malicious signatures, a high speed Network Intrusion Detection System is required against the attacks. In the network security applications, Bloom Filters are the key building block. The packets from the high speed link can be easily processed by Bloom Filter using state- of-art hardware based systems. As Bloom Filter and its variant Counting Bloom Filter suffer from False Positive Rate, Multi Hash Counting Bloom Filter architecture is proposed. The proposed work, constitute parallel signature detection improves the False Positive Rate, but the throughput and hardware complexity suffer. To resolve this, a Multi-Level Ranking Scheme is introduced which deduces the 13% - 16% of the power and increases the throughput to 23% - 30%. This work is best suited for signature detection in high speed network.

Data Location Mechanism in Agent-Based Autonomic Storage Systems

This paper introduces agent-based methodology to build a distributed autonomic storage system infrastructure, and an effectively negotiation mechanism based on agent is applied for data location. We present Availability-based Data Allocation （ADA） algorithm as a data placement strategy to achieve high efficient utilization of storage resources by employing multiple distributed storage resources. We use Bloom filter in each storage device to track the location of data. We present the data lookup strategy that small size of read request is handled directly, and large size of read request is handled by cooperation with storage devices.The performance evaluation shows that the data location mechanism is high available and can work well for heterogeneous autonomic storage systems.

A verifiable essential secret image sharing scheme based on HLRs(VESIS-(t,s,k,n))

In traditional secret image sharing schemes,a secret image is shared among shareholders who have the same position.But if the shareholders have two different positions,essential and non‐essential,it is necessary to use essential secret image sharing schemes.In this article,a verifiable essential secret image sharing scheme based on HLRs is proposed.Shareholder's share consists of two parts.The first part is produced by the shareholders,which prevents the fraud of dealers.The second part is a shadow image that is produced by using HLRs and the first part of share.The verification of the first part of the shares is done for the first time by using multilinear and bilinear maps.Also,for verifying shadow images,Bloom Filters are used for the first time.The proposed scheme is more efficient than similar schemes,and for the first part of the shares,has formal security.

Hardware-based high-performance string lookup with value retrieval using extended Bloom filter

in network packet processing, high-performance string lookup systems are very important. In this article, an extended Bloom filter data structure is introduced to support value retrieval string lookup, and to improve its performance, a weighted extended Bloom filter （WEBF） structure is generalized. The optimal configuration of the WEBF is then derived, and it is shown that it outperforms the traditional Bloom filter. Finally, an application-specific integrated circuit （ASIC）-based technique using WEBF is outlined.

Functional Verification of Signature Detection Architectures for High Speed Network Applications

To meet the future internet traffic challenges, enhancement of hardware architectures related to network security has vital role where software security algorithms are incompatible with high speed in terms of Giga bits per second (Gbps). In this paper, we discuss signature detection technique (SDT) used in network intrusion detection system (NIDS). Design of most commonly used hardware based techniques for signature detection such as finite automata, discrete comparators, Knuth-Morris-Pratt (KMP) algorithm, content addressable memory (CAM) and Bloom filter are discussed. Two novel architectures, XOR based pre computation CAM (XPCAM) and multi stage look up technique (MSLT) Bloom filter architectures are proposed and implemented in third party field programmable gate array (FPGA), and area and power consumptions are compared. 10Gbps network traffic generator (TNTG) is used to test the functionality and ensure the reliability of the proposed architectures. Our approach involves a unique combination of algorithmic and architectural techniques that outperform some of the current techniques in terms of performance, speed and powerefficiency.

Improved Approximate Detection of Duplicates for Data Streams Over Sliding Windows

Detecting duplicates in data streams is an important problem that has a wide range of applications. In general, precisely detecting duplicates in an unbounded data stream is not feasible in most streaming scenarios, and, on the other hand, the elements in data streams are always time sensitive. These make it particular significant approximately detecting duplicates among newly arrived elements of a data stream within a fixed time frame. In this paper, we present a novel data structure, Decaying Bloom Filter （DBF）, as an extension of the Counting Bloom Filter, that effectively removes stale elements as new elements continuously arrive over sliding windows. On the DBF basis we present an efficient algorithm to approximately detect duplicates over sliding windows. Our algorithm may produce false positive errors, but not false negative errors as in many previous results. We analyze the time complexity and detection accuracy, and give a tight upper bound of false positive rate. For a given space G bits and sliding window size W, our algorithm has an amortized time complexity of O（√G/W）. Both analytical and experimental results on synthetic data demonstrate that our algorithm is superior in both execution time and detection accuracy to the previous results.