Search

Ensemble Clustering (EC) methods became more popular in recent years. In this methods, some primary clustering algorithms are considered to be as inputs and a single cluster is generated to achieve the best results combined with each other. In this paper, we considered three hierarchical methods, which are single-link, average-link, and complete-link as the primary clustering and the results were combined with each other. This combination was done based on correlation matrix. The basic algorithms were combined as binary and triplicate and the results were evaluated as well. the IMDB film dataset were clustered based on existing features. CH, Silhouette and Dunn Index criteria were used to evaluate the results. These criteria evaluate the clustering quality by calculating intra-cluster and inter-cluster distances. CH index had the highest value when all three basic clusters are combined. our method shows that EC can achieve better results and present clusters with higher robustness and accuracy.

The Latent Dirichlet Allocation (LDA) topic model is a popular research topic in the field of text mining. In this paper, Sentiment Word Co-occurrence and Knowledge Pair Feature Extraction based LDA Short Text Clustering Algorithm (SKP-LDA) is proposed. A definition of a word bag based on sentiment word co-occurrence is proposed. The co-occurrence of emotional words takes full account of different short texts. Then, the short texts of a microblog are endowed with emotional polarity. Furthermore, the knowledge pairs of topic special words and topic relation words are extracted and inserted into the LDA model for clustering. Thus, semantic information can be found more accurately. Then, the hidden n topics and Top30 special words set of each topic are extracted from the knowledge pair set. Finally, via LDA topic model primary clustering, a Top30 topic special words set is obtained that is clustered by K-means secondary clustering. The clustering center is optimized iteratively. Comparing with JST, LSM, LTM and ELDA, SKP-LDA performs better in terms of Accuracy, Precision, Recall and F-measure. The experimental results show that SKP-LDA reveals better semantic analysis ability and emotional topic clustering effect. It can be applied to the field of micro-blog to improve the accuracy of network public opinion analysis effectively.

To improve the pertinence and effectiveness of equipment maintenance work and reasonably reduce the maintenance cost, it is urgent to carry out research on the online diagnosis information collection of key equipment for power distribution. Based on the distributed intelligent system, a smart distributing management system architecture is designed with comprehensive perception and software definition. A layered management and multidimensional display of the power distribution IoT system is studied, and product requirement in the power distribution IoT environment is analyzed. With edge computing, positioning function of product feature target is formulated. By combining demand analysis methods with modular architecture, models of product demanding are built. The primary clustering uses the Ward system clustering method to classify the load characteristics, the secondary clustering uses the fuzzy C-means method, then, the clustering center is provided by the primary Ward clustering results. The method proposed can avoid the sensitivity of the fuzzy C-means clustering method to the initial parameters, and can ensure a better clustering effect.

Clustering as a major task in data mining is responsible for discovering hidden patterns in unlabeled datasets. Finding the best clustering is also considered as one of the most challenging problems in data mining. Due to the problem complexity and the weaknesses of primary clustering algorithm, a large part of research has been directed toward ensemble clustering methods. Ensemble clustering aggregates a pool of base clusterings and produces an output clustering that is also named consensus clustering. The consensus clustering is usually better clustering than the output clusterings of the basic clustering algorithms. However, lack of quality in base clusterings makes their consensus clustering weak. In spite of some researches in selection of a subset of high quality base clusterings based on a clustering assessment metric, cluster-level selection has been always ignored. In this paper, a new clustering ensemble framework has been proposed based on cluster-level weighting. The certainty amount that the given ensemble has about a cluster is considered as the reliability of that cluster. The certainty amount that the given ensemble has about a cluster is computed by the accretion amount of that cluster by the ensemble. Then by selecting the best clusters and assigning a weight to each selected cluster based on its reliability, the final ensemble is created. After that, the paper proposes cluster-level weighting co-association matrix instead of traditional co-association matrix. Then, two consensus functions have been introduced and used for production of the consensus partition. The proposed framework completely overshadows the state-of-the-art clustering ensemble methods experimentally.

The past decade has been marked by the (continued) explosion of diverse data content and the fast development of intelligent data analytics techniques. One problem we identified in the mid-2000s was similarity search of feature-rich data. The challenge here was achieving both high accuracy and high efficiency in high-dimensional spaces. Locality sensitive hashing (LSH), which uses certain random space partitions and hash table lookups to find approximate nearest neighbors, was a promising approach with theoretical guarantees. But LSH alone was insufficient since a large number of hash tables were required to achieve good search quality. Building on an idea of Panigrahy, our multi-probe LSH method introduced the idea of intelligent probing. Given a query object, we strategically probe its neighboring hash buckets (in a query-dependent fashion) by calculating the statistical probabilities of similar objects falling into each bucket. Such intelligent probing can significantly reduce the number of hash tables while achieving high quality. In this paper, we revisit the problem motivation, the challenges, the key design considerations of multi-probe LSH, as well as discuss recent developments in this space and some questions for further research.

In recent years, considerable effort has been devoted to research on hash function. Nevertheless, it’s hard to obtain the proporties of sensitivity, confusion and diffusion, collision resistance, and high efficiency simultaneously. Based on research of all attacks to classical hash functions, we propose a parallel and collision resistance hash function. With regard to the design of compression function, in order to resist attacks, such as birthday attack, forgery attack and multi-collision attack, we change the initial value of the chaining variable, which is processed through three-round iterations. On the aspect of iterative structure, instead of calculating sequentially, a parallel structure is designed. The improvement lies in the combination of two message blocks independently in each round. The statistical data and experimental analysis prove that the designed hash function algorithm has good properties of confusion and diffusion, collision resistance and superior efficiency, which can make it become a new type of candidate for hash function.

© 1992-2012 IEEE. Hash-based nearest neighbor search has become attractive in many applications. However, the quantization in hashing usually degenerates the discriminative power when using Hamming distance ranking. Besides, for large-scale visual search, existing hashing methods cannot directly support the efficient search over the data with multiple sources, and while the literature has shown that adaptively incorporating complementary information from diverse sources or views can significantly boost the search performance. To address the problems, this paper proposes a novel and generic approach to building multiple hash tables with multiple views and generating fine-grained ranking results at bitwise and tablewise levels. For each hash table, a query-Adaptive bitwise weighting is introduced to alleviate the quantization loss by simultaneously exploiting the quality of hash functions and their complement for nearest neighbor search. From the tablewise aspect, multiple hash tables are built for different data views as a joint index, over which a query-specific rank fusion is proposed to rerank all results from the bitwise ranking by diffusing in a graph. Comprehensive experiments on image search over three well-known benchmarks show that the proposed method achieves up to 17.11% and 20.28% performance gains on single and multiple table search over the state-of-The-Art methods.

Hash functions have been used to address security requirements such as integrity, message authentication and non-repudiation. In WSNs, these functions are also used to preserve sensor nodes' identity (ID) anonymity, i.e., they are used to generate and verify dynamic pseudonyms that are used to identify sensor nodes in a communication session. In this latter application, there is an open issue as to how long the output of a hash function (i.e. hash value) we should use in pseudonym generation. The longer the hash value, the longer is the pseudonym, thus the harder it is to guess a pseudonym that is generated by using a hash function. On the other hand, the use of a longer hash value also means that the bandwidth and energy costs in transmitting the pseudonym will be higher. As sensor nodes typically have limited resources and are battery powered, the balance between the protection level of ID anonymity and performance and energy costs incurred in providing such a protection is an open issue. This paper inves- tigates the use of hash value truncation in preserving ID anonymity in WSNs and the impact of hash value truncation on four criteria attributes (security against brute force attacks, probability of pseudonym collisions, energy trade- off and end-to-end packet delivery delay). It reports the possible impacts of other factors including the type and usage of hash functions, sensor node capabilities, adversary capabilities, ability to resolve pseudonym collisions, network density and data collection rate. The results show that the impacts of these factors may be contradictory. Therefore, the determination of an optimal level of hash value truncation should consider all trade-offs brought by these factors.

This paper presents a memory-constrained hash join algorithm (PaMeCo Join) designed to operate with main-memory column-store database systems. Whilst RAM has become more affordable and the popularity of main-memory database systems continues to grow, we recognize that RAM is a finite resource and that database systems rarely have an excess of memory available to them. Therefore, we design PaMeCo to operate within an arbitrary memory limitation by processing the input relations by parts, and by using a compact hash table that represents the contained tuples in a compact format. Coupled with a radix-clustering system that lowers memory latencies, we find that PaMeCo can offer competitive performance levels to other contemporary hash join algorithms in an unconstrained environment, while being up to three times faster than a high-performing hash join when memory constraints are applied.

We analyze the computational collision problem on a hash algorithm based on chaotic tent map, and then present an improvement of the original algorithm in this paper. More specifically, we utilize message extension to enhance the correlation of plaintexts in the message and aggregation operation to improve the correlation of sequences of message blocks, which significantly increase the sensitivity between message and hash values, thereby greatly resisting the collision. Finally, we evaluate the performance of the improved algorithm by computer simulation, and the results show that it can resist the computational collision and can satisfy the requirements of a more secure hash algorithm.

In this work we present the first design and implementation of a wait-free hash map. Our multiprocessor data structure allows a large number of threads to concurrently insert, get, and remove information. Wait-freedom means that all threads make progress in a finite amount of time--an attribute that can be critical in real-time environments. This is opposed to the traditional blocking implementations of shared data structures which suffer from the negative impact of deadlock and related correctness and performance issues. We only use atomic operations that are provided by the hardware; therefore, our hash map can be utilized by a variety of data-intensive applications including those within the domains of embedded systems and supercomputers. The challenges of providing this guarantee make the design and implementation of wait-free objects difficult. As such, there are few wait-free data structures described in the literature; in particular, there are no wait-free hash maps. It often becomes necessary to sacrifice performance in order to achieve wait-freedom. However, our experimental evaluation shows that our hash map design is, on average, 7 times faster than a traditional blocking design. Our solution outperforms the best available alternative non-blocking designs in a large majority of cases, typically by a factor of 15 or higher.

This paper addresses a problem in the hashing technique for large scale image retrieval: learn a compact hash code to reduce the storage cost with performance comparable to that of the long hash code. A longer hash code yields a better precision rate of retrieved images. However, it also requires a larger storage, which limits the number of stored images. Current hashing methods employ the same code length for both queries and stored images. We propose a new hashing scheme using two hash codes with different lengths for queries and stored images, i.e., the asymmetric cyclical hashing. A compact hash code is used to reduce the storage requirement, while a long hash code is used for the query image. The image retrieval is performed by computing the Hamming distance of the long hash code of the query and the cyclically concatenated compact hash code of the stored image to yield a high precision and recall rate. Experiments on benchmarking databases consisting up to one million images show the effectiveness of the proposed method.

The problem of determining the state region in which the current state point lies is referred to as the point location problem in the explicit model predictive control. In this paper, a two-level structure to store the state regions is proposed and two efficient methods for solving the point-location problem are developed; these are the two-level grid TLG method and the grid-BST method. The TLG method uses a tow-level hash table. Before building the two-level structure, the synonymy partitions are merged to reduce the memory storage demand. By setting each parameter in a triplet, the two-level hash table can reach its optimal state and balance the complexity among the memory storage, reprocessing offline computation and the online computation. The grid-BST method uses hash table as the first-level structure and builds the binary search tree in the hash grid in which there are many partitions. This two-level structure reduces reprocessing time significantly especially when the state partitions and the piecewise affine control laws PWA control laws are in a large number. Using the hyperplane HP as the node not leaf node of the tree, the method only stores all the different PWA control laws instead of the state partitions. The two proposed methods overcome the quick complexity growth when the number of polyhedral partitions increases and 2 numerical examples show the advantages of the proposed two methods.

Content-based publish/subscribe systems have been employed to deal with complex distributed information flows in many applications. It is well recognized that event matching is a fundamental component of such large-scale systems. Event matching searches a space which is composed of all subscriptions. As the scale and complexity of a system grows, the efficiency of event matching becomes more critical to system performance. However, most existing methods suffer significant performance degradation when the system has large numbers of both subscriptions and their component constraints. In this paper, we present Hash Tree (H-Tree), a highly efficient index structure for event matching. H-Tree is a hash table in nature that is a combination of hash lists and hash chaining. A hash list is built up on an indexed attribute by realizing novel overlapping divisions of the attribute’s value domain, providing more efficient space consumption. Multiple hash lists are then combined into a hash tree. The basic idea behind H-Tree is that matching efficiencies are improved when the search space is substantially reduced by pruning most of the subscriptions that are not matched. We have implemented H-Tree and conducted extensive experiments in different settings. Experimental results demonstrate that H-Tree has better performance than its counterparts by a large margin. In particular, the matching speed is faster by three orders of magnitude than its counterparts when the numbers of both subscriptions and their component constraints are huge.

Hashing methods have been widely applied to deal with large scale image retrieval problems. The orthogonal k-means (OKM) generates hash codes for images via a minimization of quantization errors using a coordinate descent algorithm. However, its performance is dependent on the initialization of the rotation matrix. Therefore, the Multi-Hash OK-means (MHOK) method is proposed to reduce the instability of performance and improve the precision and recall rate yielded by the OKM. The MHOK uses multiple hash tables created by multiple of OKM with different initialization. For each image, instead of keeping all multiple OKM hash codes, the MHOK selects a subset of hash codes via a minimization of quantization errors over different hash tables. Therefore, hash codes of different images are independently selected from different hash tables. Thus, the overall quantization error of all images is minimized over the multiple OKM hash tables. So, the MHOK enjoys the high performance of multi-hashing while uses less storage by hash code selection. Experimental results show that the MHOK achieves better precision-recall curve than the original OKM and other state-of-art unsupervised hashing methods.

Hash tables are common lookup data structures. A key element of such data structure is a hash function because it greatly affects its latency. A badly designed hash function may slow down the hash table by producing hash collisions which is a negative state that has to be resolved using additional computation time. There is no deterministic method for designing a well performing hash function. The designer solely relies on his/her experience, knowledge or intuition. This paper focuses on the evolutionary design of hash functions for Cuckoo hashing which is a modern approach to collision resolution. Its main benefit is constant time complexity of lookup which is achieved by using two or more hash functions per hash table. Hash functions are automatically designed using common elementary hashing operations such as multiplication or binary shift by means of genetic programming. The evolved hash functions are about 2.7 to 7 times faster, can utilize about 1 to 1.6% more keys and use fewer elementary operations than human-created counterparts on the IP address hashing problem.

Longest Prefix Match (LPM) is a basic and important function for current network devices. Hash-based approaches appear to be excellent candidate solutions for LPM with the capability of fast lookup speed and low latency. The number of hash table probes, i.e. the search path of a hash-based LPM algorithm, directly determines the lookup performance. In this paper, we propose Ω-LPM to improve the lookup performance by optimizing the search path of the hash-based LPM. Ω-LPM first reconstructs the forwarding table to support random search [19], then it applies a dynamic programming algorithm to find the shortest search path based on the statistics of the matching probabilities. Ω-LPM concretely reduces the number of hash table probes via searching most of the packets in optimal search paths. Even in the worst case, the upper bound of the average search path of Ω-LPM is 1 + log2(N), here N is the length of the longest prefix in the routing table. The case studies of the name lookup in Named Data Networking and the IP lookup in current Internet demonstrate that Ω-LPM can shorten 61.04% and 86.88% search paths compared with the basic hash-based methods of name lookup [22] and IP lookup [12], respectively, furthermore Ω-LPM reduces 32.3% probes of the name lookup and 73.55% probes of the IP lookup compared with the optimal linear search. The experimental results conducted on extensional name tables and IP tables also show that Ω-LPM has both low memory overhead and excellent scalability.

Hash table is one of the most fundamental and critical data structures for membership query and maintenance. However, the performance of a standard hash table degrades greatly when the hash collision is large due to high load factor or unpredictable dynamic membership updates, especially per-packet updates in network processing. In this paper, we shape a hash table from the conventional slim-and-tall style to a wide-and-short style by facilitating an extension of logical cache block. Then, a cache aware hash table (CaHash) is given and explored in detail. Based on an observation that the operation sequences may be in a potential and probabilistic successive order, especially for network applications, a rewritable hash table (RwHash) is finally proposed, which provides two rewritable policies to dynamically move elements within a bucket when updating. Theoretical analysis shows that, no matter what load factor and collision are, RwHash can achieve near-optimal performance the same as the performance when a standard hash table in the case of no collision. Real experiments show that RwHash can achieve 4.10 times speedup in some parameter and even more with different configurations than a standard hash table in the case of heavy collisions. Our approaches are elegantly practical in implementation for both software and hardware.

Learning-based hashing methods are widely used for nearest neighbor retrieval, and recently, online hashing methods have demonstrated good performance-complexity trade-offs by learning hash functions from streaming data. In this paper, we first address a key challenge for online hashing: the binary codes for indexed data must be recomputed to keep pace with updates to the hash functions. We propose an efficient quality measure for hash functions, based on an information-theoretic quantity, mutual information, and use it successfully as a criterion to eliminate unnecessary hash table updates. Next, we also show how to optimize the mutual information objective using stochastic gradient descent. We thus develop a novel hashing method, MIHash, that can be used in both online and batch settings. Experiments on image retrieval benchmarks (including a 2.5M image dataset) confirm the effectiveness of our formulation, both in reducing hash table recomputations and in learning high-quality hash functions., International Conference on Computer Vision (ICCV), 2017

We present new hash tables for joins, and a hash join based on them, that consumes far less memory and is usually faster than recently published in-memory joins. Our hash join is not restricted to outer tables that fit wholly in memory. Key to this hash join is a new concise hash table (CHT), a linear probing hash table that has 100% fill factor, and uses a sparse bitmap with embedded population counts to almost entirely avoid collisions. This bitmap also serves as a Bloom filter for use in multi-table joins. We study the random access characteristics of hash joins, and renew the case for non-partitioned hash joins. We introduce a variant of partitioned joins in which only the build is partitioned, but the probe is not, as this is more efficient for large outer tables than traditional partitioned joins. This also avoids partitioning costs during the probe, while at the same time allowing parallel build without latching overheads. Additionally, we present a variant of CHT, called a concise array table (CAT), that can be used when the key domain is moderately dense. CAT is collision-free and avoids storing join keys in the hash table. We perform a detailed comparison of CHT and CAT against leading in-memory hash joins. Our experiments show that we can reduce the memory usage by one to three orders of magnitude, while also being competitive in performance.

Similarity search plays an important role in many applications involving high-dimensional data. Due to the known dimensionality curse, the performance of most existing indexing structures degrades quickly as the feature dimensionality increases. Hashing methods, such as locality sensitive hashing (LSH) and its variants, have been widely used to achieve fast approximate similarity search by trading search quality for efficiency. However, most existing hashing methods make use of randomized algorithms to generate hash codes without considering the specific structural information in the data. In this paper, we propose a novel hashing method, namely, robust hashing with local models (RHLM), which learns a set of robust hash functions to map the high-dimensional data points into binary hash codes by effectively utilizing local structural information. In RHLM, for each individual data point in the training dataset, a local hashing model is learned and used to predict the hash codes of its neighboring data points. The local models from all the data points are globally aligned so that an optimal hash code can be assigned to each data point. After obtaining the hash codes of all the training data points, we design a robust method by employing $\ell_{2,1}$ -norm minimization on the loss function to learn effective hash functions, which are then used to map each database point into its hash code. Given a query data point, the search process first maps it into the query hash code by the hash functions and then explores the buckets, which have similar hash codes to the query hash code. Extensive experimental results conducted on real-life datasets show that the proposed RHLM outperforms the state-of-the-art methods in terms of search quality and efficiency.

Connection management uses hash table. Hash function and data structure are both the bottleneck technology. For balancing computation cost and uniformity of hash function, three new hash functions were devised——the Random number Mapping Xor (RMX) function based on random number table mapping, the Segment Sampling Xor (SSX) function and Byte by Byte Shift Xor (BBSX) function based on segment generation and bit operations. The results show that these three functions are all better than IPSX on uniformity. This paper analyzed memory access performance and miss rate of multiple slots hash table, and presented the technical idea for shorting packet process time in connection management. Simulation is described.

Non-cryptographic hash functions have been investigated to identify their pseudo-random nature when employed in the implementation of hash tables for real-time storage and look-up of uniform resource locators. Statistical studies have been performed on the sequences generated using five widely used non-cryptographic hash functions: (1) CRC, (2) Adler, (3) DJBX33A, (4) FNV, and (5) Murmur. The comparative analysis of tested non-cryptographic hash functions shows that the Adler hash function is not suitable for hash table implementation, whereas, the rest of non-cryptographic hash functions exhibit similar and better randomizing features which make them an attractive choice for hash table implementation.

This paper presented a improved method of hash table, the algorithm based on transform and conquer, established a number of small-scale array, then imitated binary search processes and reduced the hash collision. Simulation results shows that , not only the continuous memory requirement is reduced greatly, but also that when the hash collisions occur, the searching efficiency is improved by an order of magnitude from O(n) to O(logn), the space utilization rate is also improved greatly.

This paper presents a quickly locate the query methods in the face of huge amounts of data. The method by analyzing the data relationship, split the database, the formation of cross-database quickly Hash positioning table, and by analyzing the query cost to build double weighted graph and weight table. Each query is given based on the node weight table fast cross-database query path, and quickly locate the target from the cross-database positioning Hash table Hash calculation, in order to achieve fast positioning method.

This paper presents a new duplicate image detection scheme that adopts multiple hash tables in a novel way for quick image matching and, consequently, fast duplicate detection. The proposed scheme contains two phases: the feature generation phase and the duplication inspection phase. The former phase extracts the features of images that need protection and transforms them into key-value pairs, which are stored in the slots of multiple hash tables. When a possibly duplicated image needs to be examined, the latter phase hashes the features of the suspect image into the corresponding slots of the multiple hash tables and determines if the suspect image is a duplicate one. The execution time of the scheme is relatively short thanks to the unique design of the multiple hash tables. The experimental results show that the proposed scheme obtained satisfactory results both on the recall and precision rates, hence demonstrating it can effectively identify duplicate images including digitally modified copies.

The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b, searching for a particular key only takes expected average t q =1+1/2 Ω(b) disk accesses for any load factor α bounded away from 1. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases.We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t q =1+Θ(α/b) even if a truly random hash function is used. Then we demonstrate that the block probing algorithm (Pagh et al. in SIAM Rev. 53(3):547–558, 2011) achieves t q =1+1/2 Ω(b), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b. Note that the two conditions hold on a real machine, although they are not stated in the cache-oblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t q =1+O(α/b), which is exactly what linear probing achieves. The hash table, especially its external memory version, is one of the most important index structures in large databases. Assuming a truly random hash function, it is known that in a standard external hash table with block size b, searching for a particular key only takes expected average t q =1+1/2 Ω(b) disk accesses for any load factor α bounded away from 1. However, such near-perfect performance is achieved only when b is known and the hash table is particularly tuned for working with such a blocking. In this paper we study if it is possible to build a cache-oblivious hash table that works well with any blocking. Such a hash table will automatically perform well across all levels of the memory hierarchy and does not need any hardware-specific tuning, an important feature in autonomous databases.We first show that linear probing, a classical collision resolution strategy for hash tables, can be easily made cache-oblivious but it only achieves t q =1+Θ(α/b) even if a truly random hash function is used. Then we demonstrate that the block probing algorithm (Pagh et al. in SIAM Rev. 53(3):547–558, 2011) achieves t q =1+1/2 Ω(b), thus matching the cache-aware bound, if the following two conditions hold: (a) b is a power of 2; and (b) every block starts at a memory address divisible by b. Note that the two conditions hold on a real machine, although they are not stated in the cache-oblivious model. Interestingly, we also show that neither condition is dispensable: if either of them is removed, the best obtainable bound is t q =1+O(α/b), which is exactly what linear probing achieves.

Hash tables are widely used in network applications, as they can achieve O(1) query, insert, and delete operations at moderate loads. However, at high loads, collisions are prevalent in the table, which increases the access time and induces non-deterministic performance. Slow rates and non-determinism can considerably hurt the performance and scalability of hash tables in the multi-threaded parallel systems such as ASIC/FPGA and multi-core. So it is critical to keep the hash operations faster and more deterministic. This paper presents a novel fast collision-free hashing scheme using Discriminative Bloom Filters (DBFs) to achieve fast and deterministic hash table lookup. DBF is a compact summary stored in on-chip memory. It is composed of an array of parallel Bloom filters organized by the discriminator. Each element lookup performs parallel membership checks on the on-chip DBF to produce a possible discriminator value. Then, the element plus the discriminator value is hashed to a possible bucket in an off-chip hash table for validating the match. This DBF-based scheme requires one off-chip memory access per lookup as well as less off-chip memory usage. Experiments show that our scheme achieves up to 8.5-fold reduction in the number of off-chip memory accesses per lookup than previous schemes.

We propose a new hash function, the unique permutation hash function, and a performance analysis of its hash computation. We denote the cost of a hash function h by C"h(k,N), which stands for the expected number of table entries that are checked when inserting the (k+1)^s^t key into a hash table of size N, where k out of N table entries are filled by previous insertions. A hash function maps a key to a permutation of the table locations. A hash function, h, is simple uniform if items are equally likely to be hashed to any table location (in the first trial). A hash function, h, is random or strong uniform if the probability of any permutation to be a probe sequence, when using h, is 1N!, where N is the size of the table. We show that the unique permutation hash function is not only a simple uniform hash function but also a random hash function, i.e., strong uniform, and therefore has the optimal cost. Namely, each probe sequence is equally likely to be chosen when the keys are uniformly chosen. Our hash function ensures that each empty table location has the same probability to be assigned by a uniformly chosen key. We also show that the expected time for computing the unique permutation hash function is O(1) and the expected number of table locations that are checked before an empty location is found during insertion (or search) is also O(1) for constant load factors @a

This paper proposes a new chaotic keyed hash function based on a single 4-dimensional chaotic cat map whose irregular outputs are used to compute a hash value. The suggested scheme is fast, efficient and flexible. It takes an input message of arbitrary length and returns a hash value of a fixed length n , where n is a multiple of 32 (by convention, n is usually one of the numbers 128, 160, 256, 512, and 1024). Simulation results are presented to demonstrate the suggested hashing scheme’s high sensitivity to the original message and the secret key, as well as its strong capability for confusion and diffusion, and very strong collision resistance. In comparison with existing work, especially those based on chaotic maps, the proposed scheme exhibits superior performance.

Hash table is used in many areas of networking such as route lookup, packet classification, per-flow state management and network monitoring for its constant access time latency at moderate loads. However, collisions may become frequent at high loads in traditional hash tables, which may lead the access time complexity to be linear and intolerable to applications like high-speed route lookups. While some schemes were proposed to help resolve this problem and most of them may achieve O(1) average memory access per lookup, very few of them are able to cut down the access to a deterministic single one. In this paper, we design a structure called deterministic and efficient hash table (DEHT). In DEHT, a novel data structure on on-chip memory is built, with the help of which the off-chip memory access can be decreased to a single one at most per lookup even when the load of the hash table is very high. What's more, the on-chip data structure also plays a similar role as Bloom Filter to do membership screening, which can avoid most lookups of nonexistent items of the hash table visiting the off-chip memory. Through theoretical analysis and simulations, we show that our scheme is faster than other schemes in lookup operations; the usable load of the off-chip hash table, the memory efficiency and the false positive rate of the on-chip data structure are also favorable.

The region of DNA immediately in front of a gene body (also called upstream region) contains short (8-20 base) sequence motifs that help to control when that gene is turned on and off. Unfortunately, these motifs are generally unknown and commonly degenerate. In this work, we propose a motif-finding framework that, given a set of gene upstream regions, performs their all-to-all pairwise comparison and identifies all the motifs of length k (k-mers) that are common to any pair of upstream regions or differ in at most d characters. Our framework stores the k-mers found in each gene in a multi-level hash table. Our hash table design optimizes hash table comparison (rather than hash table insertion or lookup), is highly parallelizable and easily maps onto GPU. We propose four GPU kernels for pairwise hash table comparison, each leveraging a distinct parallelization approach. We study how different factors (the hash function, the number of buckets and the settings of other implementation-specific parameters) affect the performance of our implementation. Experimental results performed using an average-size yeast genome show that our fastest GPU kernel outperforms an 8-thread, cache-efficient CPU implementation by a factor of ~52x.

A hash algorithm converts data into compact strings. In the multimedia domain, effective hashing is the key to large-scale similarity search in high-dimensional feature space. A limit of existing hashing techniques is that they typically use single features. In order to improve search performance, it is necessary to utilize multiple features. Due to the compactness requirement, concatenation of hash values from different features is not an optimal solution. Thus a fusion process is desired. In this paper, we solve the multiple feature fusion problem by a hash bit selection framework. Given multiple features, we derive an n-bit hash value of improved performance compared with hash values of the same length computed from each individual feature. The framework utilizes a feature-independent hash algorithm to generate a sufficient number of bits from each feature, and selects n bits from the hash bit pool by leveraging pair-wise label information. The metric bit reliability is used for ranking the bits. It is estimated by bit-level hypothesis testing. In addition, we also take into account the dependence among bits. A weighted graph is constructed for refined bit selection, where the bit reliability is used as vertex weights and the mutual information among hash bits is used as edge weights. We demonstrate our framework with LSH. Extensive experiments confirm that our method is effective, and outperforms several state-of-the-art methods.

Video hashing has attracted increasing attention in the field of video searching. However, there was no technical research on the prediction of hash length, which is extremely important in mobile circumstance. In this paper, a hash length prediction method is proposed for video hashing in the case of video copy detection. The video feature is mapped to video hashes with different lengths via kernel-based supervised hashing (KSH). A part of the dataset is used as the training data to establish the relationship between the probability of collision (PoC) and hash length according to the probability distributions of the bit error rate (BER) of hash for non-copy and copy videos, respectively. Referring to this relationship, the approximate shortest hash length with approximate best performance for the whole dataset is predicted. Simulations demonstrate that the proposed hash length prediction method can estimate the approximate optimal length for the corresponding video hash, which can be used as a reference for the whole dataset.

In this paper, we present a novel keyed hash function based on a dynamic lookup table of functions. More specifically, we first exploit the piecewise linear chaotic map (PWLCM) with secret keys used for producing four 32-bit initial buffers and then elaborate the lookup table of functions used for selecting composite functions associated with messages. Next, we convert the divided message blocks into ASCII code values, check the equivalent indices and then find the associated composite functions in the lookup table of functions. For each message block, the four buffers are reassigned by the corresponding composite function and then the lookup table of functions is dynamically updated. After all the message blocks are processed, the final 128-bit hash value is obtained by cascading the last reassigned four buffers. Finally, we evaluate our hash function and the results demonstrate that the proposed hash algorithm has good statistical properties, strong collision resistance, high efficiency, and better statistical performance compared with existing chaotic hash functions.

This paper deals with hardware design which unifies MD5 and HAS-160 hash algorithms. Two algorithms get a message with arbitrary length and process message blocks divided into 512 bits each time and output a hash code with a fixed length. MD5 ouputs a hash code of 128 bits and HAS-160 a hash code of 160 bits. The unified hash core designed has 32% of slices overhead compared to HAS-160 core. However, there is only a fixed message buffer space used. The unified hash core which run a step in one clock cycle operates at 92MHz and has performance which digests a message in the speed of 724Mbps at MD5 and 581Mbps at HAS-160 hash mode. The unified hash core which is designed can be applicable to the areas such as E-commerce, data integrity and digital signature.

We show that when memory is bounded, i.e. memory buckets are finite, dynamic hash tables that allow insertions and deletions behave significantly worse than their static counterparts that only allow insertions. This behavior differs from previous results in which, when memory is unbounded, the two models behave similarly. We show the decrease in performance in dynamic hash tables using several hash-table schemes. We also provide tight upper and lower bounds on the achievable overflow fractions in these schemes. Finally, we propose an architecture with content-addressable memory (CAM), which mitigates this decrease in performance.

We present a local level-set method based on the hash table data structure, which allows the storage of only a band of grid points adjacent to the interface while providing an O(1) access to the data. We discuss the details of the construction of the hash table data structure as well as the advection and reinitialization schemes used for our implementation of the level-set method. We propose two dimensional numerical examples and compare the results to those obtained with a quadtree data structure. Our study indicates that the method is straightforward to implement but suffers from limitations that make it less efficient than the quadtree data structure.

In the framework of Wegman and Carter, a $k$-independent hash function maps any $k$ keys independently. It is known that 5-independent hashing provides good expected performance in applications such as linear probing and second moment estimation for data streams. The classic $5$-independent hash function evaluates a degree 4 polynomial over a prime field containing the key domain $[n]=\{0,\ldots,n-1\}$. Here we present an efficient 5-independent hash function that uses no multiplications. Instead, for any parameter $c$, we make $2c-1$ lookups in tables of size $O(n^{1/c})$. In experiments on different computers, our scheme gained factors of 1.8 to 10 in speed over the polynomial method. We also conducted experiments on the performance of hash functions inside the above applications. In particular, we give realistic examples of inputs that make the most popular 2-independent hash function perform quite poorly. This illustrates the advantage of using schemes with provably good expected performance for all inputs.

In this paper, we propose an algorithm for one-way hash function construction based on the chaotic look-up table with changeable parameter. First, the original message with padding is divided into block messages as groups and then further broken into sub-block messages, which are translated into corresponding ASCII codes by groups. Then the group ASCII codes are successively inputted into the chaotic look-up table updated by changeable parameter to permute corresponding values. Finally, based on the calculation of the values, 128-bit hash value is generated. Performance analysis indicates that our proposed algorithm satisfies sensitive requirements and can resist all kinds of attacks.

We address the compression efficiency of feedback-free and hash-check distributed video coding, which generates and transmits a hash code of a source information sequence. The hash code helps the decoder perform a motion search. A hash collision is a special case in which the hash codes of wrongly reconstructed information sequences occasionally match the hash code of the source information sequence. This deteriorates the quality of the decoded image greatly. In this paper, the statistics of hash collision are analyzed to help the codec select the optimal trade-off between the probability of hash collision and the length of the hash code, according to the principle of rate-distortion optimization. Furthermore, two novel algorithms are proposed: (1) the nonzero prefix of coefficients (NPC), which indicates the count of nonzero coefficients of each block for the second algorithm, and also saves 8.4% bitrate independently; (2) the adaptive selection of hash functions (AHF), which is based on the NPC and saves a further 2%–6% bitrate on average. The detailed optimization of the parameters of AHF is also presented.

Building a high performance IP packet forwarding (PF) engine remains a challenge due to increasingly stringent throughput requirements and the growing size of IP forwarding tables. The router has to match the incoming packet's IP address against all entries in the forwarding table. The matching process has to be done at increasingly higher wire speed; hence, scalability and low power consumption are critical for PF engines. Various hash table based schemes have been considered for use in PF engines. Set associative memory can be used for hardware implementations of hash tables with the property that each bucket of a hash table can be searched in a single memory cycle. However, the classic hashing downsides, such as collisions and worst case memory access time have to be dealt with. While open addressing hash tables, in general, provide good average case search performance, their memory utilization and worst case performance can degrade quickly due to collisions (that lead to bucket overflows). The two standard solutions to the overflow problem are either to use predefined probing (e.g., linear or quadratic probing) or to use multiple hash functions. This work presents two new simple hash schemes that extend both aforementioned solutions to tackle the overflow problem efficiently. The first scheme is a hash probing scheme that is called Content-based HAsh Probing (CHAP). As the name suggests, CHAP, based on the content of the hash table, avoids the classical side effects of predefined hash probing methods (i.e., primary and secondary clustering phenomena) and at the same time reduces the overflow. The second scheme, called Progressive Hashing (PH), is a general multiple hash scheme that reduces the overflow as well. The basic idea of PH is to split the prefixes into groups where each group is assigned one hash function, then reuse some hash functions in a progressive fashion to reduce the overflow. Both schemes are amenable to high-performance hardware implementations with low overflow and constant worst-case memory access time. We show by experimenting with real IP lookup tables and synthetic traces that both schemes outperform other existing hashing schemes.

An efficient key generating method that uses recursive hash chains is proposed for hierarchical access control. The proposed method introduces recursive hash chains for reducing the number of managed keys. In addition to decreasing this number down to one, regardless of the number of the controlled targets and their depth, the number of keys delivered to a user by using the proposed method is equal to or less than that in conventional methods.

Hashing with linear probing dates back to the 1950s and is among the most studied algorithms for storing (key, value) pairs. In recent years it has become one of the most important hash table organizations since it uses the cache of modern computers very well. Unfortunately, previous analyses rely either on complicated and space consuming hash functions, or on the unrealistic assumption of free access to a hash function with random and independent function values. Carter and Wegman, in their seminal paper on universal hashing, raised the question of extending their analysis to linear probing. However, we show in this paper that linear probing using a 2-wise independent hash function may have expected logarithmic cost per operation. Recently, Pactrascu and Thorup have shown that 3- and 4-wise independent hash functions may also give rise to logarithmic expected query time. On the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. This resolves the question of finding a space and time efficient hash function that provably ensures good performance for hashing with linear probing.

Dominant features for the content-based image retrieval usually have high-dimensionality. So far, many researches have been done to index such values to support fast retrieval. Still, many existing indexing schemes are suffering from performance degradation due to the curse of dimensionality problem. As an alternative, heuristic algorithms have been proposed to calculate the answer with ‘high probability’ at the cost of accuracy. In this paper, we propose a new hash tree-based indexing structure called tertiary hash tree for indexing high-dimensional feature data. Tertiary hash tree provides several advantages compared to the traditional extendible hash structure in terms of resource usage and search performance. Through extensive experiments, we show that our proposed index structure achieves outstanding performance.

A hash chain H for a one-way hash function h(·) is a sequence of hash values , where v0 is a public value, vn a secret value, and vi =h(vi+1). A hash chain traversal algorithm T computes and outputs the hash chain H, returning vi in time period (called round) i for 1 ≤ i ≤ n. While previous hash chain traversal algorithms were designed to output all hash values vi (1 ≤ i ≤ n) in order, there are applications where every m-th hash value (i.e., vm, v2m, v3m, . . .) is required to be output. We introduce a hash chain traversal algorithm that selectively outputs every m-th hash value efficiently. The main technique is a transformation from a hash chain traversal algorithm outputting every hash value into that outputting every m-th hash value. Compared with the direct use of previous hash chain traversal algorithms, our proposed method requires less memory storages and computational costs.

In this paper, a novel multimedia identification system based on quantum hashing is considered. Many traditional systems are based on binary hash which is obtained by encoding intermediate hash extracted from multimedia content. In the system considered, the intermediate hash values extracted from a query are encoded into quantum hash values by incorporating uncertainty in the binary hash values. For this, the intermediate hash difference between the query and its true-underlying content is considered as a random process. Then, the uncertainty is represented by the probability density estimate of the intermediate hash difference. The quantum hashing system is evaluated using both audio and video databases, and with marginal increment in computational cost, the quantum hashing system is shown to be more robust against various distortions than the binary hashing system using the same intermediate hash values.

Hash join is used to join large, unordered relations and operates independently of the data distributions of the join relations. Real-world data sets are not uniformly distributed and often contain significant skew. Although partition skew has been studied for hash joins, no prior work has examined how exploiting data skew can improve the performance of hash join. In this paper, we present histojoin, a join algorithm that uses histograms to identify data skew and improve join performance. Experimental results show that for skewed data sets histojoin performs significantly fewer I/O operations and is faster by 10-60% than hybrid hash join.

A novel chaotic hash algorithm based on a network structure formed by 16 chaotic maps is proposed. The original message is first padded with zeros to make the length a multiple of four. Then it is divided into a number of blocks each contains 4 bytes. In the hashing process, the blocks are mixed together by the chaotic map network since the initial value and the control parameter of each tent map are dynamically determined by the output of its neighbors. To enhance the confusion and diffusion effect, the cipher block chaining (CBC) mode is adopted in the algorithm. Theoretic analyses and numerical simulations both show that the proposed hash algorithm possesses good statistical properties, strong collision resistance and high flexibility, as required by practical keyed hash functions.