Search

Network measurement provides operators an efficient tool for many network management tasks such as performance diagnosis, traffic engineering and intrusion prevention. However, with the rapid and continuous growth of traffic speed, it needs more computing and memory resources to monitor traffic in per-flow or per-packet granularity. Sample-based measurement systems (e.g., NetFlow, sFlow) have been developed to perform coarse-grained measurement, but they may miss part of records, especially for mice flows, which are important for some network management tasks (e.g., anomaly detection, performance diagnosis). To address these issues, data streaming algorithms such as hash tables and sketches have been introduced to balance the trade-off among accuracy, speed, and memory usage. In this paper, we present a systematic survey of various data structures, algorithms and systems which have been proposed in recent years to perform fine-grained measurement for high-speed networks. We organize these methods and systems from a software-defined perspective. In particular, we abstract fine-grained network measurement into three-layer architecture. We introduce the responsibility of each layer and categorize existing state-of-the-art works into this architecture. Finally, we conclude the paper and discuss the future directions of fine-grained network measurement.

Searchable Encryption (SE) is a popular cryptographic primitive for building ciphertexts retrieval systems with far-reaching applications. However, existing SE schemes generally do not support threshold access control (i.e., data users must collaboratively issue search and decryption operations over encrypted cloud data) in a group-oriented cloud data sharing setting, which is increasingly receiving much attention in the research community. Thus, in this paper, we first propose a Threshold Multi-keyword Search (TMS) scheme for cloud-based group data sharing (referred to as basic TMS scheme) by utilizing Shamir's secret sharing technique, to achieve threshold multi-keyword search, threshold decryption, and short record ciphertext size. Then, we extend this basic TMS to realize threshold result verification and threshold traceability (referred to as enhanced TMS). Furthermore, the enhanced TMS is extended to support public result verification and dynamic operations with the public verifier and improved hash tables, respectively. Our formal security analysis proves that both basic TMS and enhanced TMS are semi-adaptively secure and can resist Chosen-Keyword Attack (CKA). Our theoretical evaluation and empirical experiments demonstrate the potential utility of both schemes.

K-mers are short DNA sequences that are used for genome sequence analysis. Applications that use k-mers include genome assembly and alignment. However, the wider bioinformatic use of these short sequences has challenges related to the massive scale of genomic sequence data. A single human genome assembly has billions of k-mers. As a result, the computational requirements for analyzing k-mer information is enormous, particularly when involving complete genome assemblies. To address these issues, we developed a new indexing data structure based on a hash table tuned for the lookup of short sequence keys. This web application, referred to as KmerKeys, provides performant, rapid query speeds for cloud computation on genome assemblies. We enable fuzzy as well as exact sequence searches of assemblies. To enable robust and speedy performance, the website implements cache-friendly hash tables, memory mapping and massive parallel processing. Our method employs a scalable and efficient data structure that can be used to jointly index and search a large collection of human genome assembly information. One can include variant databases and their associated metadata such as the gnomAD population variant catalogue. This feature enables the incorporation of future genomic information into sequencing analysis. KmerKeys is freely accessible at https://kmerkeys.dgi-stanford.org.

In this article, we consider the following cloud storage security problem: A user outsources his/her data to a cloud and later frequently updates the data by adding new data items and deleting existing ones. When the user requests an existing data item from the cloud, the cloud may claim that there is no such data item. This could happen due to cloud management issues, hardware/software failures, hackers, or economic incentives, such as saving cloud’s operation costs. The ability to confirm the data existence/nonexistence when accessing a data item on the dynamic outsourced cloud storage is referred to as dynamic verifiable data access (DVDA). Existing cloud security research works, including encrypted search and proof of storage (i.e., proof of retrievability and proof of data possession), are not sufficient for addressing dynamic verifiable data access. In this article, we present a solution for the dynamic verifiable data access problem. In order to support data dynamics and verifiability, we enhance a hash authentication tree that is build on top of a hash table with a new semantics. With the enhanced hash authentication tree, the proposed protocol supports adding/deleting data in the outsourced storage while satisfying data access verifiability requirement simultaneously. Our open-source experimental evaluation shows that it only takes less than 0.1 ms to verify a data access on a dataset with 400 items using communication cost around 1.7 KB.

We revisit the problem of building static hash tables on the GPU and present an efficient implementation of bucketed hash tables. By decoupling the probing scheme from the hash table in-memory representation, we offer an implementation where the number of probes and the bucket size are the only factors limiting performance. Our analysis sweeps through the hash table parameter space for two probing schemes: cuckoo and iceberg hashing. We show that a bucketed cuckoo hash table (BCHT) that uses three hash functions outperforms alternative methods that use iceberg hashing and a cuckoo hash table that uses a bucket size of one. At load factors as high as 0.99, BCHT enjoys an average probe count of 1.43 during insertion. Using three hash functions only, positive and negative queries require at most 1.39 and 2.8 average probes per key, respectively.

Packet classification is a critical component in network appliances. Software Defined Networking and cloud computing update the rulesets frequently for flexible policy configuration. Tuple Space Search (TSS), implemented in Open vSwitch (OVS), achieves fast rule updating at the sacrifice of the classification rate. In TSS, each tuple is managed by a hash table and classifying a packet needs to go through all hash tables. Merging tuples can reduce the number of hash tables, but inevitably increases the hash conflicts that may even worsen the classification performance in some cases. No existing algorithm meets the need of both fast packet classification and online rule updating. In this paper, we propose Convolutional Neural Network (CNN)-based Range Partition (CRP) to achieve fast packet classification and online update simultaneously. CRP exploits CNN-based image recognition to quickly partition tuples into range spaces upon the change of ruleset distribution, which reduces hash operations while avoiding rule overlapping caused by hashing many rules to the same location of the hash table. Experimental results demonstrate that CRP achieves 3.2x classification speed and 4.2x update speed on average compared with state-of-the-art algorithms. We also implement CRP in OVS. The throughput of CRP-OVS is 10x that of native OVS.

Searchable encryption has received a significant attention from the research community with various constructions being proposed, each achieving asymptotically optimal complexity for specific metrics (e.g., search, update). Despite their elegance, the recent attacks and deployment efforts have shown that the optimal asymptotic complexity might not always imply practical performance, especially if the application demands a high privacy. In this article, we introduce a novel Dynamic Searchable Symmetric Encryption (DSSE) framework called Incidence Matrix (IM)-DSSE, which achieves a high level of privacy, efficient search/update, and low client storage with actual deployments on real cloud settings. We harness an incidence matrix along with two hash tables to create an encrypted index, on which both search and update operations can be performed effectively with minimal information leakage. This simple set of data structures surprisingly offers a high level of DSSE security while achieving practical performance. Specifically, IM-DSSE achieves forward-privacy, backward-privacy and size-obliviousness simultaneously. We also create several DSSE variants, each offering different trade-offs that are suitable for different cloud applications and infrastructures. We fully implemented our framework and evaluated its performance on a real cloud system (Amazon EC2). We have released IM-DSSE as an open-source library for wide development and adaptation.

Link saturation is a problem in computer networks. We propose a link aggregation solution that is robust and solves this problem. The approach consists of creating a virtual link by combining multiple physical interfaces, summing up their bandwidth. Besides increasing the data transmission throughput, this type of solution enables a fast and clear repair in the case of link unavailability. Since Software-Defined Networking usage is increasing daily in business scenarios, this work demonstrates a way to create link aggregation in such situations. This led to the improvement of services availability, among many advantages. To achieve that, we defined and implemented a system with self-adaptive link aggregation. We study the intra-flow and inter-flow link aggregation. To evaluate the implementation, we created three algorithms under different conditions: Virtual Round-Robin, Traffic Analysis, and Hash Table. We evaluated the three algorithms in real-world and virtual scenarios. We used the Ryu controller and, for packet switching, the OVS (Open vSwitch) and BPFabric. Virtual Round-Robin achieved 95% of fairness and Hash Table provided higher throughput.

Modern microprocessors contain several special function units (SFUs) such as specialized arithmetic units, cryptographic processors, etc. In recent times, applications such as cloud computing, web-based search engines, and network applications are widely used, and place new demands on the microprocessor. Hashing is a key algorithm that is extensively used in such applications. Hashing can reduce the complexity of search and lookup from O( $N$ N ) to O( $N/n$ N / n ), where $n$ n bins are used. Hashing is typically performed in software. Thus, implementing a hardware-based hash unit on a modern microprocessor would potentially increase performance significantly. In this article, we propose a novel hardware hash unit (HU) design for use in modern microprocessors, at the microarchitecture level and at the circuit level. First, we present the design of the HU at the microarchitecture level. We simulate the HU to compare its performance with a software-based hash implementation. We demonstrate a significant speedup (up to 15×) for the HU. Furthermore, the performance scales elegantly with increasing database size and application diversity, without increasing the hardware cost. Second, we present the circuit design of the HU for use in modern microprocessors, using a 45nm technology. Our proposed hardware hash unit is based on the use of a content-addressable memory (CAM) to implement each bin of the hash table. We simulate the HU circuit and compare it with a traditional CAM design. We demonstrate an average power reduction of 5.48× using the HU over the traditional CAM. Also, we show that the HU can operate at a maximum frequency of 1.39 $GHz$ G H z (after accounting for process, voltage and temperature (PVT) variations and accounting for wiring parasitics). Furthermore, we present the delay, power and area trade-offs of the HU design with varying hash table sizes.

Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. Starting from a particular lock-free hash map data structure, named Lock-Free Hash Tries, we focus on solving the problem of memory reclamation without losing the lock-freedom property. To the best of our knowledge, outside garbage collected environments, there is no current implementation of hash maps that is able to reclaim memory in a lock-free manner. To achieve this goal, we propose an approach for memory reclamation specific to Lock-Free Hash Tries that explores the characteristics of its structure in order to achieve efficient memory reclamation with low and well-defined memory bounds. We present and discuss in detail the key algorithms required to easily reproduce our implementation by others. Experimental results show that our approach obtains better results when compared with other state-of-the-art memory reclamation methods and provides a competitive and scalable hash map implementation, if compared to lock-based implementations.

This paper deals with the construction of digital lexicons within the scope of Natural Language Processing. Data Structures called Hash Tables have demonstrated to generate good results for Natural Language Interface for Databases and have data dispersion, response speed and programming simplicity as main features. The storage of the desired information is done by associating a key through the hashing functions that is responsible for distributing the information in this table. The objective of this paper is to present the tool called Visual TaHs that uses a sparse table to a real lexicon (Lexicon of Herbs), improving performance results of several implemented hash functions. Such structure has achieved satisfactory results in terms of speed and storage when compared to conventional databases and can work in various media, such as desktop, Web and mobile.

This paper addresses the Set Orienteering Problem which is a generalization of the Orienteering Problem where the customers are grouped in clusters, and the profit associated with each cluster is collected by visiting at least one of the customers in the respective cluster. The problem consists of finding a tour that maximizes the collected profit but, since the cost of the tour is limited by a threshold, only a subset of clusters can usually be visited. We propose a Biased Random-Key Genetic Algorithm for solving the Set Orienteering Problem in which three local search procedures are applied to improve the fitness of the chromosomes. In addition, we introduced three rules useful to reduce the size of the instances and to speed up the resolution of the problem. Finally, a hashtable is used to quickly retrieve the information that are required several times during the computation. The computational results, carried out on benchmark instances, show that our algorithm is significantly faster than the other algorithms, proposed in the literature, and it provides solutions very close to the best-known ones.

Join is a data-intensive and compute-intensive operation in database systems. As most existing solutions to accelerate the hash join operation on field programmable gate array (FPGA) are focused on N-to-1 join relationships, their performances rapidly decline on N-to-M joins. To resolve this shortcoming, this brief proposes a novel architecture combining hash and sort-merge algorithms for join acceleration. In the build phase, the architecture utilizes a single hash function to build hash tables for two data tables, and the hash collisions are addressed by building ordered linked lists according to their join attributes. In the merge phase, mapped buckets in two hash tables are merged one-to-one to find matching tuples. This architecture lends itself to high parallelism to improve its performance. Experimental results show that the design on a FPGA achieved a high join throughput of 194.0 million tuples per second, which is better than the reported FPGA implementations. Moreover, the architecture is perfectly compatible with both N-to-1 and N-to-M join relationships.

Intelligent vehicular networks converged with software-defined networking provides several flow-based surveillance services to mobile applications on vehicular nodes. But, as the scale of such networks grows exponentially, a substantial delay in processing tremendous flows emerges. The delay can be reduced by accelerating the packet classification methods, which are nowadays exploited in software-defined vehicular networks. Fast packet classification lets firewalls to inspect each incoming packet at wire speed. One of the well-known packet classification methods is the KD-tree algorithm. This paper presents an enhanced version of this algorithm that uses the geometric space to display different fields and increases search speed by recursive decomposition of the search space. Also, the enhanced KD-tree is integrated with a leaf-pushing technique, which enhances the performance of KD-tree search during classification. The proposed algorithm is implemented using a bloom filter data structure and a hash table. Experimental results show that the proposed leaf-pushed KD-tree algorithm improves packet classification speed up to 24 times in comparison with the conventional KD-tree. Moreover, the proposed algorithm can significantly reduce the classification time in comparison with state-of-the-art tree-based algorithms.

In this article, we introduce HashGraph, a new scalable approach for building hash tables that uses concepts taken from sparse graph representations—hence, the name HashGraph. HashGraph introduces a new way to deal with hash-collisions that does not use “open-addressing” or “separate-chaining,” yet it has the benefits of both these approaches. HashGraph currently works for static inputs. Recent progress with dynamic graph data structures suggests that HashGraph might be extendable to dynamic inputs as well. We show that HashGraph can deal with a large number of hash values per entry without loss of performance. Last, we show a new querying algorithm for value lookups. We experimentally compare HashGraph to several state-of-the-art implementations and find that it outperforms them on average 2× when the inputs are unique and by as much as 40× when the input contains duplicates. The implementation of HashGraph in this article is for NVIDIA GPUs. HashGraph can build a hash table at a rate of 2.5 billion keys per second on a NVIDIA GV100 GPU and can query at nearly the same rate.

Hyperspace hashing which is often applied to NoSQL data-bases builds indexes by mapping objects with multiple attributes to a multidimensional space. It can accelerate processing queries of some secondary attributes in addition to just primary keys. In recent years, the rich computing resources of GPU provide opportunities for implementing high-performance HyperSpace Hash. In this study, we construct a fully concurrent dynamic hyperspace hash table for GPU. By using atomic operations instead of locking, we make our approach highly parallel and lock-free. We propose a special concurrency control strategy that ensures wait-free read operations. Our data structure is designed considering GPU specific hardware characteristics. We also propose a warp-level pre-combinations data sharing strategy to obtain high parallel acceleration. Experiments on an Nvidia RTX2080Ti GPU suggest that GHSH performs about 20-100X faster than its counterpart on CPU. Specifically, GHSH performs updates with up to 396 M updates/s and processes search queries with up to 995 M queries/s. Compared to other GPU hashes that cannot conduct queries on non-key attributes, GHSH demonstrates comparable building and retrieval performance.

Modern query engines rely heavily on hash tables for query processing. Overall query performance and memory footprint is often determined by how hash tables and the tuples within them are represented. In this work, we propose three complementary techniques to improve this representation: Domain-Guided Prefix Suppression bit-packs keys and values tightly to reduce hash table record width. Optimistic Splitting decomposes values (and operations on them) into (operations on) frequently- and infrequently-accessed value slices. By removing the infrequently-accessed value slices from the hash table record, it improves cache locality. The Unique Strings Self-aligned Region (USSR) accelerates handling frequently occurring strings, which are widespread in real-world data sets, by creating an on-the-fly dictionary of the most frequent strings. This allows executing many string operations with integer logic and reduces memory pressure. We integrated these techniques into Vectorwise. On the TPC-H benchmark, our approach reduces peak memory consumption by 2-4× and improves performance by up to 1.5×. On a real-world BI workload, we measured a 2× improvement in performance and in micro-benchmarks we observed speedups of up to 25×.

Byte-addressable persistent memory (PM) brings hash tables the potential of low latency, cheap persistence and instant recovery. The recent advent of Intel Optane DC Persistent Memory Modules (DCPMM) further accelerates this trend. Many new hash table designs have been proposed, but most of them were based on emulation and perform sub-optimally on real PM. They were also piecewise and partial solutions that side-stepped many important properties, in particular good scalability, high load factor and instant recovery.

The rapid development of cloud computing technology has spawned many excellent cloud computing platforms. These cloud computing platforms provide an effective solution for the processing of big data, which can be used as the basis for the study of parallel mining algorithms and the application of algorithms. This article uses the FP-Growth algorithm to mine and analyze computer big data. Aiming at the low extraction efficiency of traditional FP-Growth algorithm in large-scale data environment, an improved FP-Growth algorithm is proposed. In addition, in view of the shortcomings of frequent lists of L elements that are often cross-referenced in the FP-tree construction process, an improved algorithm based on hash tables is proposed, which realizes the storage address processing element name key, and then realizes the element name key to storage numbered mapping. This article mainly introduces the optimization of FP-Growth algorithm under the background of cloud computing and computer big data. The experimental results in this paper show that the performance of the improved FP-gtowth algorithm is better than the original algorithm, the traversal time is reduced by 13%, and the mining efficiency is increased by 25%. In addition, the use of this algorithm for data clustering reduces the error rate and optimizes performance becomes better and has better application value.

Data storage is one of the significant cloud services available to the cloud users. Since the magnitude of information outsourced grows extremely high, there is a need of implementing data deduplication technique in the cloud storage space for efficient utilization. The cloud storage space supports all kind of digital data like text, audio, video and image. In the hash-based deduplication system, cryptographic hash value should be calculated for all data irrespective of its type and stored in the memory for future reference. Using these hash value only, duplicate copies can be identified. The problem in this existing scenario is size of the hash table. To find a duplicate copy, all the hash values should be checked in the worst case irrespective of its data type. At the same time, all kind of digital data does not suit with same structure of hash table. In this study we proposed an approach to have multiple hash tables for different digital data. By having dedicated hash table for each digital data type will improve the searching time of duplicate data.

Prime number in growth computer science of number theory and very need to yield an tool which can yield an hardware storey level effectiveness use efficiency and Existing Tools can be used to awaken regular prime number sequence pattern, structure bit-array represent containing subdividing variables method of data aggregate with every data element which have type of equal, and also can be used in moth-balls the yielded number sequence. Prime number very useful to be applied by as bases from algorithm kriptografi key public creation, hash table, best algorithm if applied hence is prime number in order to can minimize collision (collisions) will happen, in determining pattern sequence of prime number which size measure is very big is not an work easy to, so that become problems which must be searched by the way of quickest to yield sequence of prime number which size measure is very big Serial use of prosesor in seeking sequence prime number which size measure is very big less be efficient remember needing of computing time which long enough, so also plural use prosesor in seeking sequence of prime number will concerning to price problem and require software newly. So that by using generator of prime number use structure bit-array expected by difficulty in searching pattern sequence of prime number can be overcome though without using plural processor even if, as well as time complexity minimization can accessed. Execution time savings gained from the research seen from the research data, using the algorithm on the input Atkins 676,999,999. 4235747.00 execution takes seconds. While the algorithm by using an array of input bits 676,999,999. 13955.00 execution takes seconds. So that there is a difference of execution time for 4221792.00 seconds.

Hash tries are a trie-based data structure with nearly ideal characteristics for the implementation of hash maps. In this paper, we present a novel, simple and scalable hash trie map design that fully supports the concurrent search, insert and remove operations on hash maps. To the best of our knowledge, our proposal is the first that puts together the following characteristics: (i) be lock-free; (ii) use fixed size data structures; and (iii) maintain the access to all internal data structures as persistent memory references. Our design is modular enough to allow different types of configurations aimed for different performances in memory usage and execution time and can be easily implemented in any type of language, library or within other complex data structures. We discuss in detail the key algorithms required to easily reproduce our implementation by others and we present a proof of correctness showing that our proposal is linearizable and lock-free for the search, insert and remove operations. Experimental results show that our proposal is quite competitive when compared against other state-of-the-art proposals implemented in Java.

Databases play a fundamental role in today’s world, being used by most companies, especially those that offer services through the Internet. Today there is a wide variety of database models, each adapted for use according to the specific requirements of each application. Traditionally, the relational models with centralized architectures have been used mostly due to their simplicity and general-purpose query language, which made relational systems suitable for almost any application. However, with the growth of the Internet in recent decades, both in the number of users and in the amount of information, those centralized models began to suffer availability and scalability issues. To address those issues, the use of decentralized architectures and alternative database models began to arise, eventually replacing relational databases and centralized architectures when the requirements on availability and scalability are high. Those database models alternative to the traditional relational model are grouped under the name of NoSQL (Not only Structured Query Language). In this article, we present a NoSQL database developed as an end of degree work, with a flexible data model based on documents and a fully decentralized architecture based on the Gossip protocol for node discovery and a distributed hash table, in particular the rendezvous hashing algorithm, used to distribute and replicate the data across all the nodes. The main goals of the system are to achieve high availability (the data should be almost always accessible) and high scalability (the system should be able to scale by increasing the number of nodes to increase its capacity both on data and number of users). High availability is achieved thanks to the replication of the data, while high scalability is achieved by its decentralized architecture, which allows multiple entry points from the requests, and the data distribution, effectively increasing the database capacity by increasing the number of nodes.

Nowadays, more and more sensors, devices and applications are connected in Industrial Internet of Things (IIoT), producing massive real-time flows which need to be scheduled for Quality-of-Service provision. To realize application-aware and adaptive flow scheduling, the problem of traffic classification must be addressed at first. When edge computing paradigm is introduced into IIoT, the traffic classification service can be deployed on edge node in the near-end. Recently, deep-learning-based IIoT traffic classification methods show better performance, but the computational cost of deep learning model is too high to be deployed on edge node. Moreover, increasingly unknown flows generated by new devices and emerging industrial APPs lead to frequent training of traffic classifiers. It is difficult to migrate the complex process of classifier training from cloud server to edge nodes with limited resources. To address these issues, we take the benefits of hash mechanism and consensus mechanism in blockchain to design a lightweight IIoT traffic classification service, which is more applicable for edge computing paradigm. First, inspired by the hash mechanism in blockchain and the learning to hash for big data, we propose a new learning-to-hash method named extension hashing. By this method, we can build the set of binary coding tress (BCT set), then generating hash table for more efficient k-nearest neighbor-based classification without complex classifier training. Then, we design a new voting-based consensus algorithm to synchronize the BCT sets and the hash tables across edge nodes, thereby providing the traffic classification service. Finally, we conduct data-driven simulations to evaluate the proposed service. By comparing traffic classification results on public data set, we can see that the proposed service achieves the highest classification accuracy with the minimal time cost and memory usage.

We develop a family of efficient plane-sweeping interval join algorithms for evaluating a wide range of interval predicates such as Allen’s relationships and parameterized relationships. Our technique is based on a framework, components of which can be flexibly combined in different manners to support the required interval relation. In temporal databases, our algorithms can exploit a well-known and flexible access method, the Timeline Index, thus expanding the set of operations it supports even further. Additionally, employing a compact data structure, the gapless hash map, we utilize the CPU cache efficiently. In an experimental evaluation, we show that our approach is several times faster and scales better than state-of-the-art techniques, while being much better suited for real-time event processing.

The neighborhood problem appears in many applications of computational geometry, computational mechanics, etc. In all these situations, the main requirement for a competitive implementation is performance, which can only be attained in modern hardware by exploiting parallelism. However, whereas the performance of serial algorithms is fairly predictable, that of parallel methods depends on delicate issues that have a huge impact (cache memory, cache misses, memory alignment, etc.), but are not easy to control. Even if there is not a simple approach to deal with these factors in shared-memory architectures, it is quite convenient to program parallel algorithms where the data are segregated on a per-thread basis. With this objective in mind, we propose a strategy to develop parallel algorithms based on a two-level design, and apply it to efficiently solve the nearest neighborhood problem. At a higher level, the proposed methods orchestrate the parallel algorithm and split the space into cells stored in a hash table; at the lower level, our methods hold serial search algorithms that are completely agnostic to the high-level counterpart. Using this strategy, we have developed a library combining different serial and parallel algorithms, optimized them, and assessed their performance. The analysis carried out allows to better understand the main bottlenecks in the algorithmic solution of the nearest neighborhood problem and come out with very fast implementations that improve existing available software.

Object instance search is a challenging task with a wide range of applications, but the fast search with high accuracy has not been well solved yet. In this paper, we investigate the object instance search from a new perspective in terms of joint precision and computational cost optimization, and propose a novel index structure i.e. , Multi-Block N-ary Trie (MBNT) to accelerate the exact $r$ -neighbor search in the Hamming space. Comprehensive studies are first carried out to reveal the performance of exact and approximate nearest neighbor (NN) algorithms for object instance search. An interesting finding that the exact search is more promising for very compact binary codes ( e.g., 64-bit and 128-bit) is analyzed. Along this vein, we introduce a Trie structure, i.e., MBNT, which is specifically designed for improving the exact NN search performance in the context of large-scale object instance search. To index the binary codes, a subset of continuous bits of a binary string, denoted as a block, is regarded as an atomic indexing element. As such, the problem of lookup misses can be addressed. Theoretical analyses are also provided to show that our MBNT scheme can incur less computational cost than other hash table-based methods. Extensive experimental results on the 100M dataset have demonstrated that our method achieves faster search speed while maintaining the promising search precision towards large-scale object instance search.

Persistent indexing structures are proposed in response to emerging non-volatile memory (NVM) to provide high performance yet durable indexes. However, due to the lack of real NVM hardware, many prior persistent indexing structures were evaluated via emulation, which varies a lot across different setups and differs from the real deployment. Recently, Intel has released its Optane DC Persistent Memory Module (PMM), which is the first production-ready NVM. In this paper, we revisit popular persistent indexing structures on PMM and conduct comprehensive evaluations to study the performance differences among persistent indexing structures, including persistent hash tables and persistent trees. According to the evaluation results, we find that Cacheline-Conscious Extendible Hashing (CCEH) achieves the best performance among all evaluated persistent hash tables, and Failure-Atomic ShifT B+-Tree (FAST) and Write Optimal Radix Tree (WORT) perform better than other trees. Besides, we find that the insertion performance of hash tables is heavily influenced by data locality, while the insertion latency of trees is dominated by the flush instructions. We also uncover that no existing emulation methods accurately simulate PMM for all the studied data structures. Finally, we provide three suggestions on how to fully utilize PMM for better performance, including using clflushopt/clwb with sfence instead of clflush, flushing continuous data in a batch, and avoiding data access immediately after it is flushed to PMM.

MeanShift is one of the popular clustering algorithms and can be used to partition a digital image into semantically meaningful regions in an unsupervised manner. However, due to its prohibitively high computational complexity, a grid-based approach, called MeanShift++, has recently been proposed and succeeded to surprisingly reduce the computational complexity of MeanShift. Nevertheless, we found that MeanShift++ still has computational redundancy and there is room for improvement in terms of accuracy and runtime; thus, we propose an improvement to MeanShift++, named $\alpha $ -MeanShift++. We first attempt to minimize the computational redundancy by using an additional hash table. Then, we introduce a speedup factor ( $\alpha $ ) to reduce the number of iterations required until convergence, and we use more neighboring grid cells for the same bandwidth to improve accuracy. Through intensive experiments on image segmentation benchmark datasets, we demonstrate that $\alpha $ -MeanShift++ can run 4.1- $4.6\times $ faster on average (but up to $7\times $ ) than MeanShift++ and achieve better image segmentation quality.

Building multiple hash tables serves as a very successful technique for gigantic data indexing, which can simultaneously guarantee both the search accuracy and efficiency. However, most of existing multitable indexing solutions, without informative hash codes and strong table complementarity, largely suffer from the table redundancy. To address the problem, we propose a complementary binary quantization (CBQ) method for jointly learning multiple tables and the corresponding informative hash functions in a centralized way. Based on CBQ, we further design a distributed learning algorithm (D-CBQ) to accelerate the training over the large-scale distributed data set. The proposed (D-)CBQ exploits the power of prototype-based incomplete binary coding to well align the data distributions in the original space and the Hamming space and further utilizes the nature of multi-index search to jointly reduce the quantization loss. (D-)CBQ possesses several attractive properties, including the extensibility for generating long hash codes in the product space and the scalability with linear training time. Extensive experiments on two popular large-scale tasks, including the Euclidean and semantic nearest neighbor search, demonstrate that the proposed (D-)CBQ enjoys efficient computation, informative binary quantization, and strong table complementarity, which together help significantly outperform the state of the arts, with up to 57.76% performance gains relatively.

Modern mobile devices, such as smartphones, maintain a directory cache (DCache) to accelerate directory and file accesses. However, the original DCache recursively walks through all the components of a path name for each directory entry (dentry) lookup operation, leading to low lookup efficiency. In this article, we first investigate intrinsic characteristics of dentry lookup operations in smartphones and make several interesting findings: 1) file path lookup operations are called frequently (up to 104 times per second) by mobile applications; 2) file path lookup operations present high temporal and spatial locality; and 3) the latency of a file path lookup is linear to the depth of the path name. Based on our findings, we further propose an efficient directory entry lookup cache architecture, named dynamic skipping cache (DS-Cache), which adopts an ASCII-based hash table to simplify the path lookup complexity. In DS-Cache, a dynamic skip lookup algorithm is proposed to skip the common prefixes of different accessing paths. A rename algorithm and a delete algorithm are designed to promise the consistence of DS-Cache and the backend file system. We also design a prefix-aware cache replacement scheme to optimize the DS-Cache hit ratio. We have implemented and deployed DS-Cache on a Google Nexus 6P smartphone. The experimental results show that we can significantly reduce the latency of invoking system calls by up to 81%, and further reduce the completion time of real-world mobile applications by up to 67%.

In recent years, reconstructing a sparse map from a simultaneous localization and mapping &#x0028 SLAM &#x0029 system on a conventional CPU has undergone remarkable progress. However, obtaining a dense map from the system often requires a high-performance GPU to accelerate computation. This paper proposes a dense mapping approach which can remove outliers and obtain a clean 3D model using a CPU in real-time. The dense mapping approach processes keyframes and establishes data association by using multi-threading technology. The outliers are removed by changing detections of associated vertices between keyframes. The implicit surface data of inliers is represented by a truncated signed distance function and fused with an adaptive weight. A global hash table and a local hash table are used to store and retrieve surface data for data-reuse. Experiment results show that the proposed approach can precisely remove the outliers in scene and obtain a dense 3D map with a better visual effect in real-time.

The Big Data is unavoidable considering the place of the digital is the predominant form of communication in the daily life of the consumer. The control of its stakes and the quality its data must be a priority in order not to distort the strategies arising from their treatment in the aim to derive profit. In order to achieve this, a lot of research work has been carried out companies and several platforms created. MapReduce, is one of the enabling technologies, has proven to be applicable to a wide range of fields. However, despite its importance recent work has shown its limitations. And to remedy this, the Distributed Hash Tables (DHT) has been used. Thus, this document not only analyses the and MapReduce implementations and Top-Level Domain (TLD)s in general, but it also provides a description of a model of DHT as well as some guidelines for the planification of the future research.

Cloud computing is a current phrase in marketing for an idea which has been recognized for years: Outsourcing. Cloud computing provides a large amount of gratuities for each customer and enterprise agency. “Cloud model” is a more of a notion in which the data are hosted online and accessed in a time-anywhere manner, on a pay-per-use model. However, the users may not fully trust the cloud service providers (CSPs) in that environment. So, it is hard to decide whether the CSP meet their expectations to provide the proper secrecy to shared data. Moreover, in the environment of outsourcing, users have no longer control and ownership of data which may cause serious major issues related to data integrity. Previously, many researchers have committed themselves to draft auditing protocols for attaining proper public verification schemes through third-party auditor (TPA). On the other hand, these schemes may leak identity or data value to the third-party auditor. Therefore, to deal with these problems, we introduce an efficient public auditing protocol by constructing binary binomial tree (BBT)-like data structure with Boneh–Lynn–Shacham signature-based Homomorphic Verifiable Authenticator (BLS-HVA). This model also consists an index hash table (IHT), situated at TPA to record the information about the data block’s properties for auditing procedure. This model supports sampling blockless verification, batch auditing, and dynamic updating operations. Moreover, with such novel dynamic data structure, the proposed model guarantees that user’s group can easily trace any type of data changes through the designated BBT. Along with this, the users can also easily recover the accurate data blocks whenever the current data blocks are corrupted. The experimental results demonstrate that the proposed auditing model efficiently attains secure auditing for the cloud environment and outperforms the existing models in terms of communication and computation overhead.

Equi-join operations are fundamental in database management. Hash join algorithms are often used to reduce the computational complexity of join operations; however, their performance is influenced by imperfect data distributions caused by hash collisions. To resolve these collisions, this brief designs a hardware-accelerated hash join architecture. This architecture aims to break the trade-off between complex hash functions, which is computationally expensive, and hash join performance. First, two hash functions are employed to distribute data as evenly as possible, and then multiple entries of the collision list are provided; finally, a small number of the static random-access memory (SRAM) of the field-programmable gate arrays (FPGAs) are used to conduct the join operation in parallel. The proposed method yields high-throughput and is resource-efficient, as it does not require reprocessing of data; further, it improves hash table utilization. The results of implementing this architecture on a Xilinx Zynq FPGA platform indicate an accelerated throughput that is a minimum of $4.2\times $ that of previous hardware-accelerated hash join methods.

The cell mapping method is a prominent one for global analysis of nonlinear dynamical systems, with which multiple invariant sets can be obtained. However, it is a continuous challenge to enhance the efficiency of the cell mapping method, especially when dealing with high-dimensional nonlinear dynamical systems. In this paper, the subdivision technique commonly used in the cell mapping method is incorporated with an interpolation sampling method, which can further enhance the efficiency over the set-oriented method with subdivision for global attractors of nonlinear dynamical systems. In the present method, a new lattice of interpolating nodes is adopted to fit into the nesting structures of the subdivided cells, portions of which are sequentially removed when resolution goes from low to high. An improved interpolation method is developed to obtain one-step sample mappings, instead of integrations when error bounds are met, in the process of subdivision iterations. Furthermore, a Hash table is introduced in order to fast search and locate the coordinates of cells that cover the invariant sets. Three examples of nonlinear dynamical systems are presented to demonstrate the enhancement in efficiency and effectiveness of the proposed method, indicating that a computational cost is one half down to one sixth of the previous methods.

In modern data warehousing, data skipping is essential for high query performance. While index structures such as B-trees or hash tables allow for precise pruning, their large storage requirements make them impractical for indexing secondary columns. Therefore, many systems rely on approximate indexes such as min/max sketches (ZoneMaps) or Bloom filters for cost-effective data pruning. For example, Google PowerDrill skips more than 90% of data on average using such indexes. In this paper, we introduce Cuckoo Index (CI), an approximate secondary index structure that represents the many-to-many relationship between keys and data partitions in a highly space-efficient way. At its core, CI associates variable-sized fingerprints in a Cuckoo filter with compressed bitmaps indicating qualifying partitions. With our approach, we target equality predicates in a read-only (immutable) setting and optimize for space efficiency under the premise of practical build and lookup performance. In contrast to per-partition (Bloom) filters, CI produces correct results for lookups with keys that occur in the data. CI allows to control the ratio of false positive partitions for lookups with non-occurring keys. Our experiments with real-world and synthetic data show that CI consumes significantly less space than per-partition filters for the same pruning power for low-to-medium cardinality columns. For high cardinality columns, CI is on par with its baselines.

Association rule mining (ARM) is a well-known data mining scheme that is used to discover the commonly co-occurred itemsets from the transactional datasets. Two considerable steps of ARM are frequent item recognition and association rule generation. Minimum support and confidence measures are used in the generation of association rules. Many algorithms have been projected by the researchers to generate association rules. Fuzzy logic is incorporated to uncover the recurrent itemsets and interesting fuzzy association rules. In general, huge volume of datasets could be analyzed which in turn needs more number of database scans. In addition to this, all the transactions and items are not required for data analysis. Hence, the first step of this research work uses a dimensionality reduction technique which drastically reduces the size of the data set. This dimensionality reduction technique uses low variance and hash table methods. The proposed algorithm effectively identifies the significant transactions and items from the database. The issues of dimensionality reduction appear when the items in the databases are higher dimension than endure. The proposed algorithm reduces the irrelevant items and transactions from the transactional database. The proposed dimensionality reduction technique dimensionality reduction in transactions and items is compared with the extend frequent pattern (EFP) and intersection set theory EFP and dimensionality reduction using frequency count. Item reduction, transaction reduction, execution time and memory space are the performance factors. Second step proposes fuzzy and whale optimization for frequent item identification and association rule generation. The efficiency of the proposed algorithm is compared with particle swarm optimization genetic algorithm and fuzzy frequent itemset-Miner. Performance metrics used in this step are number of frequent items, association rules generated, execution time and memory required. Experimental results proved that the proposed techniques have produced the good results.

Here we report a simple and flexible method for DNA data storage based on Perl script. For this approach, the text data of the preamble of the “Universal Declaration of Human Rights” consisting of 2,046 words was encoded into the corresponding 8,148 base pairs of DNA using Perl-based encoding with a hash table. The encoded DNA sequences were then artificially synthesized for storage. The information DNA consisted of a total of 22 chemically synthesized DNA fragments with 400 nucleotides each, which were inserted into a cloning vector to multiply the plasmid DNA. The nucleotide integrity of the data-carrying DNA sequences were ensured under the accelerated aging conditions. Also, an erroneous nucleotide in the information DNA sequences was successfully corrected using the overlap extension PCR method. The stored DNA was read by sequencing, and the resulting DNA sequence information was successfully decoded to convert the DNA records back to the original document. Our results indicate that textual data can be stored in DNA using a simple, easy, and flexible Perl by running a script from the command line.

When a pairing $$e: {\mathbb {G}}_1 \times {\mathbb {G}}_2 \rightarrow {\mathbb {G}}_{T}$$ e : G 1 × G 2 → G T , on an elliptic curve E defined over a finite field $${\mathbb {F}}_q$$ F q , is exploited for an identity-based protocol, there is often the need to hash binary strings into $${\mathbb {G}}_1$$ G 1 and $${\mathbb {G}}_2$$ G 2 . Traditionally, if E admits a twist $${\tilde{E}}$$ E ~ of order d, then $${\mathbb {G}}_1=E({\mathbb {F}}_q) \cap E[r]$$ G 1 = E ( F q ) ∩ E [ r ] , where r is a prime integer, and $${\mathbb {G}}_2={\tilde{E}}({\mathbb {F}}_{q^{k/d}}) \cap {\tilde{E}}[r]$$ G 2 = E ~ ( F q k / d ) ∩ E ~ [ r ] , where k is the embedding degree of E w.r.t. r. The standard approach for hashing into $${\mathbb {G}}_2$$ G 2 is to map to a general point $$P \in {\tilde{E}}({\mathbb {F}}_{q^{k/d}})$$ P ∈ E ~ ( F q k / d ) and then multiply it by the cofactor $$c=\#{\tilde{E}}({\mathbb {F}}_{q^{k/d}})/r$$ c = # E ~ ( F q k / d ) / r . Usually, the multiplication by c is computationally expensive. In order to speed up such a computation, two different methods—by Scott et al. (International conference on pairing-based cryptography. Springer, Berlin, pp 102–113, 2009) and by Fuentes-Castaneda et al. (International workshop on selected areas in cryptography)—have been proposed. In this paper we consider these two methods for BLS pairing-friendly curves having $$k \in \{12,24,30,42,48\}$$ k ∈ { 12 , 24 , 30 , 42 , 48 } , providing efficiency comparisons. When $$k=42,48$$ k = 42 , 48 , the application of Fuentes et al. method requires expensive computations which were infeasible for the computational power at our disposal. For these cases, we propose hashing maps that we obtained following Fuentes et al. idea.

Analysis of methods and tools for image colorization was performed. It was explained why artificial neural network model was chosen for graphics information processing. The task of automatic colorization of arbitrary images was formulated. Initial data, conditions and constraints necessary for colorization model are listed. As a result of text classification, set of neural network hypercolumns was retrieved for each image processed. Colorization model was created which allows to determine color of each pixel based on hypercolumns set. In fact, this model consists of two related parts: classifier and colorizer. Classifier is based on using convolutional neural network, and colorizer is based on hash table which stores mapping of hypercolumns and colors. Algorythm of using this model for image colorization is proposed. Comparison of colorization results for developed and existing models was performed. Software tool was created which allows to perform learning of different neural networks and colorization of graphical information. Experiments shown that developed model determines image color quite correctly. Proposed algorithm allows to use convolutional neural network for colorizing black-and-white images, for color correction of pictures, etc.

Cloud depository is one of the customary supplications of the cloud computing system, which offers on-demand offloading services for both individuals and institutions. Although utilizes do not have full faith in the cloud service providers (CSPs) within that, it is hard to decide either the CSPs meet their licit expectations for data security or not. Thence, it is evaluative to come up with productive auditing techniques to boost owners’ trust and reliance in cloud storage. In this paper, we are presenting a scheme of auditing for assured cloud storage based on a 2-dimensional data structure called a dynamic hash table (DHT), used to record the data information for public auditing. This scheme emigrates the approved information from the CSP to the TPA and thereby a remarkable reduction in the computational cost and communication overhead. Also, the deduplication technology is utilized to lower the capacity and bandwidth prerequisites of the utilities by removing repetitious informati zon and stockpiles, only an original replica of them. We enhance our design encourages privacy preservation by homomorphism authenticator constructed on the public key, and attend batch auditing by aggregate BLS signature technique. Experimental results indicate that our mechanism achieves secure deduplication and tag generation improvements.

Image hashing based on deep convolutional neural networks (CNN), deep hashing, has acquired breakthrough in image retrieval. Although deep features from various CNN layers have various levels of information, most of the existing deep hashing methods extract the feature vector only from the output of the penultimate fully-connected layer, focusing primarily on semantic information whilst ignoring detailed structure information. This calls for research on multi-level hashing, utilizing multi-level features to exploit different levels of CNN characteristics. To fill this gap, a novel image hashing method, Multi-Level Supervised Hashing with deep feature (MLSH), is proposed in this paper to further exploit multiple levels of deep image features. It uses a multiple-hash-table mechanism to integrate multi-level features extracted from an individual deep convolutional neural network. It takes advantage of the complementarity among multi-level features from various layers of a single deep network. High-level features reveal the semantic content of the image, while low-level features provide the structural information that is missing in high-level features. Instead of simple concatenation, several hash tables are trained individually using different levels of features from different layers, which are then integrated for efficient image retrieval. The method has been systematically evaluated through experiments on three image databases, including CIFAR-10, MNIST and NUSWIDE, and has thus been demonstrated to set a new state of the art in image hashing, outperforming several state-of-the-art hashing methods. Furthermore, the recall and precision can be balanced and improved simultaneously.

We present a novel spatial hashing based data structure to facilitate 3D shape analysis using convolutional neural networks (CNNs). Our method well utilizes the sparse occupancy of 3D shape boundary and builds hierarchical hash tables for an input model under different resolutions. Based on this data structure, we design two efficient GPU algorithms namely hash2col and col2hash so that the CNN operations like convolution and pooling can be efficiently parallelized. The spatial hashing is nearly minimal, and our data structure is almost of the same size as the raw input. Compared with state-of-the-art octree-based methods, our data structure significantly reduces the memory footprint during the CNN training. As the input geometry features are more compactly packed, CNN operations also run faster with our data structure. The experiment shows that, under the same network structure, our method yields comparable or better benchmarks compared to the state-of-the-art while it has only one-third memory consumption. Such superior memory performance allows the CNN to handle high-resolution shape analysis., 12 pages, 9 figures

Стаття присвячена дослідженню методів збереження даних рекомендаційних систем. Запропоновано та досліджено використання бінарних діаграм рішень для збереження таких даних. Внаслідок великого розміру рекомендаційних систем суттєвими є обмеження по оперативній пам'яті. Метою роботи є розробка методу зберігання даних рекомендаційної системи у формі бінарних діаграм рішень та порівняння з методами збереження на основі інших структур даних. Дані рекомендаційної системи зберігаються у вигляді графу із вершинами, які представляють користувачів системи та об'єкти системи, а ребра – дії користувачів системи, відношення подібності, зв'язки рекомендацій тощо. Для підвищення ефективності у випадку інтенсивного редагування графу запропоновано збереження даних на основі “гарячого” (хеш-таблиця) та “холодного” (бінарна діаграма рішень) сховищ.Проведено серію експериментів для перевірки ефективності розробленого способу зберігання даних, для чого розроблено програмну модель спрощеної рекомендаційної системи та описано алгоритм роботи такої системи. В чисельному експерименті пропонований спосіб зберігання даних на основі бінарних дерев рішень порівнюється із трьома іншими: на основі бітових масивів, зв'язних списків та хеш-таблиць. Розглянуто переваги та недоліки реалізації кожного із вказаних методів. В ході експерименту для різних значень кількості агентів, предметів, сесій та вподобань досліджено максимальні та мінімальні значення використаної оперативної пам'яті, а також час генерації лайків, сесій та рекомендацій. Встановлено, що у випадку застосування бінарних діаграм рішень обсяг використаної оперативної пам’яті є нижчим за інші способи при меншій швидкодії, що частково може бути компенсовано декількома застосованими оптимізаціями. Завдяки меншому використанню оперативної пам'яті можна зберігати інформацію про більшу кількість вподобань, що може виявитися корисним у випадку великих розмірів графу рекомендаційної системи. Можливість для бінарних діаграм рішень пошуку даних за частковими ключами додатково дозволяє зберігати дані більшої розмірності

This paper presents a GPU-based real-time approach for generating high-definition (HD) aerial image mosaics. The cumbersome process of registering HD images is addressed by a parallel scheme that rapidly matches binary features. The proposed feature matcher takes advantage of the fast ORB (oriented FAST and rotated BRIEF) descriptor and its attainable arrangement into hash tables. By exploiting the best functionalities of binary descriptors and hashing-based data structures, the process of creating HD mosaics is accelerated. On average, real-time performance of 14.5 ms is achieved in a frame-to-frame process, for input images of 2.7 K resolution (2704 × 1521). For evaluation purposes in terms of robustness and speed, we selected two image registration methods for comparison. The first method uses the feature extractor and matcher modules of the well-known ORB-SLAM. The second comparison is carried out against the standard KNN-based matcher of OpenCV. The experiments were conducted under different conditions and scenarios, and the proposed approach exhibits a speed-up of 10.5 times compared to ORB-SLAM-based approach and 36.5 times compared to the OpenCV matcher. Therefore, this research widens the range of applications for aerial mosaicing, since the proposed system is capable of creating high-detail panoramas of large sites while acquiring data.

As an important operation in data cleaning, near duplicate Web pages detection and data mining, similarity joins have received much attention recently. Existing similarity joins fall into two broad categories—the similarity-threshold-based similarity join and top-k similarity join (TopkJoin). Compared with the traditional one, TopkJoin is more suitable for cases where the similarity threshold is unknown before hand. In this paper, we focus on the performance optimization problem of TopkJoin. Particularly, we observed that the state-of-the-art TopkJoin algorithm has three serious performance issues, i.e., the inappropriate application of hash table, inefficient use of suffix filtering and unnecessary evaluation of excessive unqualified candidates. To resolve these problems, we proposed a novel algorithm, SETJoin, by combining the existing event-driven framework with three simple yet efficient optimization techniques, viz., (1) reducing the cost in hashing by rearranging the orders of the candidate filtering and hash table lookup operations; (2) maximizing the pruning capability of suffix filtering by judiciously choosing the (near) optimal recursion depth; and (3) terminating join operations earlier by setting a much tighter stop condition for iteration. The experimental results show that SETJoin achieves up to 1.26x–3.49x speedup over the state-of-the-art algorithm on several real datasets.