Search

Hash tables are ubiquitous in computer science for efficient access to large datasets. However, there is always a need for approaches that offer compact memory utilisation without substantial degradation of lookup performance. Cuckoo hashing is an efficient technique of creating hash tables with high space utilisation and offer a guaranteed constant access time. We are given n locations and m items. Each item has to be placed in one of the k ≥ 2 locations chosen by k random hash functions. By allowing more than one choice for a single item, cuckoo hashing resembles multiple choice allocations schemes. In addition it supports dynamically changing the location of an item among its possible locations. We propose and analyse an insertion algorithm for cuckoo hashing that runs in linear time with high probability and in expectation. Previous work on total allocation time has analysed breadth first search, and it was shown to be linear only in expectation. Our algorithm finds an assignment (with probability 1) whenever it exists. In contrast, the other known insertion method, known as random walk insertion, may run indefinitely even for a solvable instance. We also present experimental results comparing the performance of our algorithm with the random walk method, also for the case when each location can hold more than one item. As a corollary we obtain a linear time algorithm (with high probability and in expectation) for finding perfect matchings in a special class of sparse random bipartite graphs. We support this by performing experiments on a real world large dataset for finding maximum matchings in general large bipartite graphs. We report an order of magnitude improvement in the running time as compared to the Hopkraft–Karp matching algorithm. [ABSTRACT FROM AUTHOR]

We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound even while growing and when taking into account storage that is only needed temporarily. None of the traditionally used hash tables have this property. We show how known approaches like linear probing and bucket cuckoo hashing can be adapted to this scenario by subdividing them into many subtables or using virtual memory overcommitting. However, these rather straightforward solutions suffer from slow amortized insertion times due to frequent reallocation in small increments. Our main result is Dynamic Space Efficient Cuckoo Table (DySECT) which avoids these problems. DySECT consists of many subtables which grow by doubling their size. The resulting inhomogeneity in subtable sizes is counterbalanced by the flexibility available in bucket cuckoo hashing where each element can go to several buckets each of which containing several cells. Experiments indicate that DySECT works well with loads up to 98%. With up to 1.9 times better performance than the next best solution. Additionally, we give a tight theoretical analysis for the possible load threshold of DySECT, i.e., a bound where with high probability the table can be filled up to that load but not above said load. This load also matches our experimental findings. [ABSTRACT FROM AUTHOR]

The focus of this work is hardness-preserving transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of domain extension of pseudorandom functions: given a PRF that takes as input elements of some domain U, we would like to come up with a PRF over a larger domain. Can we do it with little work and without significantly impacting the security of the system? One approach is to first hash the larger domain into the smaller one and then apply the original PRF. Such a reduction, however, is vulnerable to a "birthday attack": after U queries to the resulting PRF, a collision (i.e., two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is insecure against an attacker making this number of queries. In this work, we show how to go beyond the aforementioned birthday attack barrier by replacing the above simple hashing approach with a variant of cuckoo hashing, a hashing paradigm that resolves collisions in a table by using two hash functions and two tables, cleverly assigning each element to one of the two tables. We use this approach to obtain: (i) a domain extension method that requires just two calls to the original PRF can withstand as many queries as the original domain size, and has a distinguishing probability that is exponentially small in the amount of non-cryptographic work; and (ii) a security-preserving reduction from non-adaptive to adaptive PRFs. [ABSTRACT FROM AUTHOR]

An efficient two-level spatial uniform grid structure-based high-quality surface reconstruction method with Marching Cubes (MC) for smoothed particle hydrodynamics (SPH) fluids was presented in this paper. Compared with the traditional way that dividing the simulation domain with uniform grid directly, an enhanced narrow-band approach using the parallel cuckoo hashing method was taken to index the coarse-level surface vertices, hence decrease the memory consumption. Moreover, a two-level spatial uniform grid structure was employed with a scheme of arranging the fine surface vertices, which could preserve the spatial locality property to facilitate the coalesced memory access on the GPU. Our algorithm was designed for parallel architectures, based on which a parallel version of the optimized surface reconstruction was performed on the CUDA platform. In the experiment of comparison to traditional approaches, the results indicated that our surface reconstruction method was more efficient at the same level of quality of the reconstructed surfaces. [ABSTRACT FROM AUTHOR]

Consider a random bipartite multigraph G with n left nodes and m ≥ n≥2 right nodes. Each left node x has d≥1 random right neighbors. The average left degree Δ is fixed, Δ≥2. We ask whether for the probability that G has a left-perfect matching it is advantageous not to fix d for each left node x but rather choose it at random according to some (cleverly chosen) distribution. We show the following, provided that the degrees of the left nodes are independent: If Δ is an integer, then it is optimal to use a fixed degree of Δ for all left nodes. If Δ is non-integral, then an optimal degree-distribution has the property that each left node x has two possible degrees, ⌊Δ⌋ and ⌈Δ⌉, with probability p and 1− p, respectively, where p is from the closed interval [0,1] and the average over all p equals ⌈Δ⌉−Δ. Furthermore, if c= n/ m and Δ>2 are constant, then each distribution of the left degrees that meets the conditions above determines the same threshold c(Δ) that has the following property as n goes to infinity: If c < c(Δ) then asymptotically almost surely there exists a left-perfect matching. If c> c(Δ) then asymptotically almost surely there exists no left-perfect matching. The threshold c(Δ) is the same as the known threshold for offline k-ary cuckoo hashing for integral or non-integral k=Δ. [ABSTRACT FROM AUTHOR]

It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611-622, Springer, Berlin, ) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash size s the probability of a rehash is O(1/ n), the lookup time and the deletion time are O( s) in the worst case, and the amortized expected insertion time is O( s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81-102, ) (resp. Θ(log n)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629-638, ). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant. [ABSTRACT FROM AUTHOR]

A hash table is a fundamental data structure implementing an associative memory that maps a key to its associative value. Besides, the paradigm of micro-architecture design of CPUs is shifting away from faster uniprocessors toward slower chip multiprocessors. In this paper, we propose enhanced chained hashing and Cuckoo hashing methods for modern computers having a lot of CPU cores with exploiting CPU cache line and hardware level lock-free operations. The proposed methods outperform the existing methods in most cases and are very scalable in terms of the number of CPU cores. In addition, their performances do not degrade much even with a high fill factor (e.g., 90 %). Through extensive experiments using Intel 32-core machine, we have shown our proposed methods improve performance compared with the state-of-the-art version of the four exiting major hashing methods of linear, chained, Cuckoo, and Hopscotch. [ABSTRACT FROM AUTHOR]

Many data structures support dictionaries, also known as maps or associative arrays, which store and manage a set of key-value pairs. A multimap is generalization that allows multiple values to be associated with the same key. For example, the inverted file data structure that is used prevalently in the infrastructure supporting search engines is a type of multimap, where words are used as keys and document pointers are used as values. We study the multimap abstract data type and how it can be implemented efficiently online in external memory frameworks, with constant expected I/O performance. The key technique used to achieve our results is a combination of cuckoo hashing using buckets that hold multiple items with a multiqueue implementation to cope with varying numbers of values per key. Our external-memory results are for the standard two-level memory model. [ABSTRACT FROM AUTHOR]

Cuckoo hashing is a hash table data structure introduced by Pagh and Rodler, that offers constant worst case search time. As a major contribution of this paper, we analyze modified versions of this algorithm with improved performance. Further, we provide an asymptotic analysis of the search costs of all these variants of cuckoo hashing and compare these results with the well known properties of double hashing and linear probing. The analysis is supported by numerical results. Finally, our analysis shows, that the expected number of steps of search operations can be reduced by using a modified version of cuckoo hashing instead of standard algorithms based on open addressing. [ABSTRACT FROM AUTHOR]

To close the increasing performance gap between disk storage and processors, flash based solid-state devices (FSSDs) have been adopted within the memory hierarchy to improve the performance of hard disk drive (HDD) based storage system. However, FSSDs still suffer from erase-before-write restriction, coarse access granularity and limited write endurance. Recently, the cutting-edge non-volatile memory technologies are merging, e.g., phase-change memory and resistive memory, which offer us new storage alternatives with faster access, byte-addressability and better endurance. In order to address the imperative data intensive computing issues, we propose to leverage PCM as disk write cache for constructing a hybrid PCM+HDD storage architecture in this paper. First, we develop a novel hash-based write caching scheme called HALO to improve both spatial and temporal locality on hard disks, thus addressing the limitations of traditional LRU caching algorithms and rendering better I/O performance. To deal with the limited durability of PCM devices and reclaim the degraded spatial locality in previous wear-leveling techniques, we further propose novel PCM wear leveling algorithms that provide effectively uniform writes while maximizing access parallelism. We have evaluated this PCM-based hybrid storage architecture using applications with a diverse set of I/O access patterns. Our experimental results demonstrate that the HALO caching scheme leads to an average reduction of 36.8% in execution time compared to the LRU caching scheme, and that the space filling curve based wear leveling extends the lifetime of PCM by a factor of 21.6.To close the increasing performance gap between disk storage and processors, flash based solid-state devices (FSSDs) have been adopted within the memory hierarchy to improve the performance of hard disk drive (HDD) based storage system. However, FSSDs still suffer from erase-before-write restriction, coarse access granularity and limited write endurance. Recently, the cutting-edge non-volatile memory technologies are merging, e.g., phase-change memory and resistive memory, which offer us new storage alternatives with faster access, byte-addressability and better endurance. In order to address the imperative data intensive computing issues, we propose to leverage PCM as disk write cache for constructing a hybrid PCM+HDD storage architecture in this paper. First, we develop a novel hash-based write caching scheme called HALO to improve both spatial and temporal locality on hard disks, thus addressing the limitations of traditional LRU caching algorithms and rendering better I/O performance. To deal with the limited durability of PCM devices and reclaim the degraded spatial locality in previous wear-leveling techniques, we further propose novel PCM wear leveling algorithms that provide effectively uniform writes while maximizing access parallelism. We have evaluated this PCM-based hybrid storage architecture using applications with a diverse set of I/O access patterns. Our experimental results demonstrate that the HALO caching scheme leads to an average reduction of 36.8% in execution time compared to the LRU caching scheme, and that the space filling curve based wear leveling extends the lifetime of PCM by a factor of 21.6.To close the increasing performance gap between disk storage and processors, flash based solid-state devices (FSSDs) have been adopted within the memory hierarchy to improve the performance of hard disk drive (HDD) based storage system. However, FSSDs still suffer from erase-before-write restriction, coarse access granularity and limited write endurance. Recently, the cutting-edge non-volatile memory technologies are merging, e.g., phase-change memory and resistive memory, which offer us new storage alternatives with faster access, byte-addressability and better endurance. In order to address the imperative data intensive computing issues, we propose to leverage PCM as disk write cache for constructing a hybrid PCM+HDD storage architecture in this paper. First, we develop a novel hash-based write caching scheme called HALO to improve both spatial and temporal locality on hard disks, thus addressing the limitations of traditional LRU caching algorithms and rendering better I/O performance. To deal with the limited durability of PCM devices and reclaim the degraded spatial locality in previous wear-leveling techniques, we further propose novel PCM wear leveling algorithms that provide effectively uniform writes while maximizing access parallelism. We have evaluated this PCM-based hybrid storage architecture using applications with a diverse set of I/O access patterns. Our experimental results demonstrate that the HALO caching scheme leads to an average reduction of 36.8% in execution time compared to the LRU caching scheme, and that the space filling curve based wear leveling extends the lifetime of PCM by a factor of 21.6. [ABSTRACT FROM AUTHOR]