Search

Motivation The k-mer frequency in whole genome sequences provides researchers with an insightful perspective on genomic complexity, comparative genomics, metagenomics and phylogeny. The current k-mer counting tools are typically slow, and they require large memory and hard disk for assembled genome analysis. Results We propose a novel and ultra-fast k-mer counting algorithm, KCOSS, to fulfill k-mer counting mainly for assembled genomes with segmented Bloom filter, lock-free queue, lock-free thread pool and cuckoo hash table. We optimize running time and memory consumption by recycling memory blocks, merging multiple consecutive first-occurrence k-mers into C-read, and writing a set of C-reads to disk asynchronously. KCOSS was comparatively tested with Jellyfish2, CHTKC and KMC3 on seven assembled genomes and three sequencing datasets in running time, memory consumption, and hard disk occupation. The experimental results show that KCOSS counts k-mer with less memory and disk while having a shorter running time on assembled genomes. KCOSS can be used to calculate the k-mer frequency not only for assembled genomes but also for sequencing data. Availabilityand implementation The KCOSS software is implemented in C++. It is freely available on GitHub: https://github.com/kcoss-2021/KCOSS. Supplementary information Supplementary data are available at Bioinformatics online.

Most hash tables have an insertion time of 𝒪(1), often qualified as "expected" and/or "amortised". While insertions into cuckoo hash tables indeed seem to take 𝒪(1) expected time in practice, only polylogarithmic guarantees are proven in all but the simplest of practically relevant cases. Given the widespread use of cuckoo hashing to implement compact dictionaries and Bloom filter alternatives, closing this gap is an important open problem for theoreticians. In this paper, we show that random walk insertions into cuckoo hash tables take 𝒪(1) expected amortised time when any number k ≥ 3 of hash functions is used and the load factor is below the corresponding peeling threshold (e.g. ≈0.81 for k = 3). To our knowledge, this is the first meaningful guarantee for constant time insertion for cuckoo hashing that works for k ∈ {3,…,9}. In addition to being useful in its own right, we hope that our key-centred analysis method can be a stepping stone on the path to the true end goal: 𝒪(1) time insertions for all load factors below the load threshold (e.g. ≈0.91 for k = 3)., LIPIcs, Vol. 244, 30th Annual European Symposium on Algorithms (ESA 2022), pages 87:1-87:11

Motivation. In biological sequence analysis, alignment-free (also known as k-mer-based) methods are increasingly replacing mapping- and alignment-based methods for various applications. A basic step of such methods consists of building a table of all k-mers of a given set of sequences (a reference genome or a dataset of sequenced reads) and their counts. Over the past years, efficient methods and tools for k-mer counting have been developed. In a different line of work, the use of gapped k-mers has been shown to offer advantages over the use of the standard contiguous k-mers. However, no tool seems to be available that is able to count gapped k-mers with the same efficiency as contiguous k-mers. One reason is that the most efficient k-mer counters use minimizers (of a length m < k) to group k-mers into buckets, such that many consecutive k-mers are classified into the same bucket. This approach leads to cache-friendly (and hence extremely fast) algorithms, but the approach does not transfer easily to gapped k-mers. Consequently, the existing efficient k-mer counters cannot be trivially modified to count gapped k-mers with the same efficiency. Results. We present a different approach that is equally applicable to contiguous k-mers and gapped k-mers. We use multi-way bucketed Cuckoo hash tables to efficiently store (gapped) k-mers and their counts. We also describe a method to parallelize counting over multiple threads without using locks: We subdivide the hash table into independent subtables, and use a producer-consumer model, such that each thread serves one subtable. This requires designing Cuckoo hash functions with the property that all alternative locations for each k-mer are located in the same subtable. Compared to some of the fastest contiguous k-mer counters, our approach is of comparable speed, or even faster, on large datasets, and it is the only one that supports gapped k-mers., LIPIcs, Vol. 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022), pages 12:1-12:20

To provide the necessary security and privacy privileges for registered users of biometric systems, a novel template protection method for generating cancelable palmprint features based on randomized cuckoo hashing and minHash is proposed in this paper. Firstly, the orthogonal features of palmprint are extracted using the anisotropic filter. Then, a novel randomized cuckoo hashing is applied on the binary palmprint feature as a means of first layer security. Randomized cuckoo hashing composes of two hash tables; before hashing, each column of original biometric template is filtered with a random matrix to improve discriminative ability. For the randomized cuckoo hashing with the same positions, we use different Gray coding methods instead, which improves irreversibility. Furthermore, to improve the efficiency and resist unlinkability attacks, another layer of privacy protection, MinHash is adopted. Experimental results on PolyU database show that our method can nearly preserve the original verification performance. The irreversibility, unlinkability and revocability properties are examined experimentally. Also, the privacy of palmprint protection scheme is analyzed under the Brute-force Attack, False Accept Attack and Birthday attack.

Every day social multimedia applications generate millions of images. To handle such huge amount of images, an optimal solution is using the public cloud, since it has powerful storage capability. Images usually contain a wealth of sensitive information, therefore social service providers need not only to provide services such as retrieval and sharing but also to protect the privacies of the images. In this paper, we propose a privacy-preserving scheme for content-based image retrieval and sharing in social multimedia applications. First, the users extract visual features from the images, and perform locality-sensitive hashing functions on visual features to generate image profile vectors. We then model the retrieval on the images as the equality search on the image profile vectors. To enable accurate and efficient retrieval, we design the secure index structure based on cuckoo hashing, which has constant lookup time. To meet the requirements of dynamic image updating, we enrich our service with image insertion and deletion. In order to reduce the key management overhead and the access control overhead in social applications, we process keys using secret sharing techniques to enable the users holding similar images to query and decrypt images independently. Finally we implement the prototype of the proposed scheme, and perform experiments over encrypted image databases.

Radio Frequency IDentification (RFID) technology is widely used in the inventory management of goods. Fast searching a subset consisting of some particular target tags is of practical importance for a variety of applications. Existing protocols are inefficient due to the low utilization of frame. In this paper, in order to improve the utilization of slot frame, we first generalize Cuckoo hash to extended Cuckoo hash which can use more than two hash functions. Then, we propose an extended CUckoo hash-based missing tag Detection (CUD) protocol, which can efficiently identify all missing tags within a predefined specific set. In CUD, the reader first uses the extended cuckoo hash to generate a fingerprint vector of the target tags. By using this vector, almost all target tags can be assigned a single slot and the majority of non-target tags can be filtered out. Furthermore, we optimize the parameters through theoretical analysis to minimize the execution time of the protocol. Extensive simulation results demonstrate that CUD is superior to the state-of-the-art protocols.

Serving DRAM as the storage through key–value abstraction has proved as an attractive option, which provides fast data access for data-intensive computing. However, due to the drawbacks of network round trips and requesting conflicts, remote data access over traditional commodity networking technology might incur high latency for the key–value data store. The major performance bottleneck lies in client-side request waiting and server-side I/O overhead. Accordingly, this paper proposes RHKV: a novel R DMA and H TM friendly k ey– v alue store to provide fast and scalable data management by using the designed G-Cuckoo hashing scheme. Our work expands the idea as follows: (i) An RHKV client transmits data requests to our improved Cuckoo hashing scheme — G-Cuckoo, which constructs a Cuckoo graph as directed pseudoforests in RHKV server. The RHKV server computes the reply for each data request. The server maintains a bucket-to-vertex mapping and pre-determines the possibility of a loop prior to data insertion. Through the use of this Cuckoo graph, the endless kick-out loop of data insertions that can potentially be experienced in the case of generic Cuckoo hashing can be detected. (ii) Despite messaging primitives are slower than RDMA READs for data requests, RHKV adopts RDMA messaging verbs unconventionally. It leverages rich network semantics and makes full use of RDMA’s high bandwidth and low latency for data access over high-performance RDMA interconnects. (iii) Moreover, in order to ensure the data operation’s atomicity, RHKV strives to utilize the advanced HTM technique. Experimental performance evaluation with YCSB workloads shows that, when basic data operations are conducted, RHKV outperforms several state-of-the-art key–value stores with lower latency and higher throughput.

A new threat in encrypted databases, called volume leakage was reported by Kellaris et al. and Grubbs et al., where the volume of data associated with each key in a multi-map is leaked. An existing method addresses this problem by adding noise entries to the multi-map according to differential privacy so that adversaries cannot infer the volume of data. However, it assumes that the data is static and therefore does not support any update operations, such as insertion, deletion, etc. To this problem, this paper proposes a method that enables data insertion in the encrypted multi-map with volume hiding. The basic idea is to use local differential privacy instead of differential privacy in adding noise entries when performing insertions. Besides, we employ cuckoo hashing to perturb the place of insertion, thereby allowing insertions of new items without leaking the volume of entries.However, our proposed method is not suitable for large databases. We consider the use of cloud database in healthcare as a use case. The cloud database is necessary for healthcare in cases such as when multiple medical institutions want to share medical data or when home healthcare providers want to access medical data from outside of hospitals. There are privacy issues if the number of patients for each disease is known. Furthermore, when inserting data of a new patient, we want to hide which disease the patient is suffering from.We conduct experiments to assess the feasibility of the proposed method, and it presents a reasonable performance.

For any forest G = (V, E) it is possible to orient the edges E so that no vertex in V has out-degree greater than 1. This paper considers the incremental edge-orientation problem, in which the edges E arrive over time and the algorithm must maintain a low-out-degree edge orientation at all times. We give an algorithm that maintains a maximum out-degree of 3 while flipping at most O(log log n) edge orientations per edge insertion, with high probability in n. The algorithm requires worst-case time O(log n log log n) per insertion, and takes amortized time O(1). The previous state of the art required up to O(log n / log log n) edge flips per insertion. We then apply our edge-orientation results to the problem of dynamic Cuckoo hashing. The problem of designing simple families ℋ of hash functions that are compatible with Cuckoo hashing has received extensive attention. These families ℋ are known to satisfy static guarantees, but do not come typically with dynamic guarantees for the running time of inserts and deletes. We show how to transform static guarantees (for 1-associativity) into near-state-of-the-art dynamic guarantees (for O(1)-associativity) in a black-box fashion. Rather than relying on the family ℋ to supply randomness, as in past work, we instead rely on randomness within our table-maintenance algorithm., LIPIcs, Vol. 204, 29th Annual European Symposium on Algorithms (ESA 2021), pages 12:1-12:18

Cuckoo hashing [1] is an efficient hash method with high space occupancy. For improved latency and throughput of cuckoo hashing, FPGA is used to accelerate basic operations of the hash table based on cuckoo hashing recently. However, the frequent kick out and reinsert operations degrade the throughput of cuckoo hashing implementation on FPGAs, especially under high table occupancy. In this paper, we propose a cuckoo hashing accelerator on FPGAs that uses one-step BFS (breadth-first search) to reduce the number of reinsert operations when the table occupancy becomes high. The average throughput of the accelerator achieves 185 million requests per second (MRPS) when the table occupancy reaches 92% at 200MHz. And the throughput at 90% table occupancy is 30% higher than the work in [2].

The focus of this work is \emph{hardness-preserving} transformations of somewhat limited pseudorandom functions families (PRFs) into ones with more versatile characteristics. Consider the problem of \emph{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 $\sqrt{\size{U}}$ queries to the resulting PRF, a collision (\ie two distinct inputs having the same hash value) is very likely to occur. As a consequence, the resulting PRF is \emph{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 \textit{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 {\em 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 {\em security-preserving} reduction from non-adaptive to adaptive PRFs., This is the final draft of this paper. The full version was published in the Journal of Cryptology 2019. An extended abstract of this work appeared in the Theory of Cryptography Conference (TCC) 2013

The hash table is a fundamental structure that has been implemented on graphics processing units (GPUs) to accelerate a wide range of analytics workloads. Most existing works have focused on static scenarios and occupy large GPU memory to maximize the insertion efficiency. In many cases, data stored in hash tables get updated dynamically, and existing approaches use unnecessarily large memory resources. One naive solution is to rebuild a hash table (known as rehashing) whenever it is either filled or mostly empty. However, this approach renders significant overheads for rehashing. In this paper, we propose a novel dynamic cuckoo hash table technique on GPUs, known as DyCuckoo. We devise a resizing strategy for dynamic scenarios without rehashing the entire table that ensures a guaranteed filled factor. The strategy trades search performance with resizing efficiency, and this tradeoff can be configured by users. To further improve efficiency, we propose a 2-in-d cuckoo hashing scheme that ensures a maximum of two lookups for find and delete operations, while retaining similar performance for insertions as a general cuckoo hash. Extensive experiments have validated the proposed design’s effectiveness over several state-of-the-art hash table implementations on GPUs. DyCuckoo achieves superior efficiency while enables fine-grained memory control, which is not available in existing GPU hash table approaches.

The approximate set-membership data structures (ASMDS), like the Bloom filter and cuckoo filter, provide constant-time testing of set-membership. They produce false positives because of a loss of bits during compression. However, in case all potential false positives are known (or can be evaluated), it is possible to use filter cascades and collectively eliminate such false positives. The application of filter cascading algorithm to the Bloom filter was originally proposed for optimizing memory usage and is currently an integral part of CRLLite. Recently proposed cuckoo filters function similarly to Bloom filters but with cuckoo hashing techniques. They produce comparatively lower storage overheads and additionally support efficient deletions. Therefore, applying the cascading algorithms to the cuckoo filter will also produce lower storage overheads in comparison to cascading Bloom filters. Further, cuckoo filter's support for deletions enable efficient updates to the filter cascades. In this paper, we present the design and analysis of cascading cuckoo filters, a potentially more space-optimal ASMDS in comparison to cascading Bloom filters. A novel contribution of this paper is the application of filter cascading algorithm to cuckoo filter, which has not been proposed before to the best of our knowledge.

Severe consequences in volume leakage (subject to the conditions required by specific attacks) stimulate a new research direction (Eurocrypt 2019) of volume-hiding structured encryption (\(\mathsf {STE}\)), particularly encrypted multi-maps (\(\mathsf {EMM}\)), in which all queries should share the same (as the largest) response size unless the scheme is lossy. Meanwhile, note that the responses are originated from the actual ciphertexts outsourced to the server. Conventional wisdom suggests that the ciphertexts (to be accessed by the server while answering a query) should also contain many dummy results to make a query look uniform with others. Supporting updates is also natural; however, attaching dummy results to a query also complicates the operation and leakage of updates, which excludes many advanced data structures, e.g., cuckoo hashing (CCS 2019). This paper proposes a space-efficient \(\mathsf {EMM}\) without storing any dummy ciphertext, which is volume hiding against passive adversaries (SP 2021) and compatible with dynamic extensions. Its crux structure is a hash ring, which is famous for load balancing but rarely appears in any \(\mathsf {STE}\). Efficiency-wise, our scheme beats the state-of-the-art (Eurocrypt 2019, CCS 2019), maintaining the necessary communication overhead and downsizing the server storage to be linear in the number of values in the \(\mathsf {EMM}\), while ruling out any data loss due to truncations or differential privacy.

Sketch is a hash-based data structure that can record traffic characteristic information in a high-speed network environment. Sketch only occupies a small amount of space resources while maintaining theoretically provable estimation accuracy. Although various sketches have been proposed, most of them achieve either high accuracy or high speed in limited memory, especially for skewed data sets. In order to achieve both goal, we combined our prior work, CBFSketch, with the odd-even cuckoo hash table which is a data structure that provides storage and accurate lookup. The new scheme is named OEBSA- Sketch, we compared our sketch with the several typical sketches in effectiveness and efficiency. The results showed the accuracy of Heavy Hitter in our scheme is 4 times higher than other sketches at most, and the accuracy of Heavy Changer is up to 16 times at most. The average absolute error is reduced by about 50% compared with CBFSketch. At the same average relative error, the space used can be reduced by about 50%.

IP blocking has become a vital task for all network attached devices. Every device from Internet of Things, to routers, to application servers requires the ability to filter certain IP addresses from delivering malicious information. Blocking IPs requires storing and checking lists of tens to hundreds of millions of IP addresses. Cuckoo hash sets provide strong performance by offering relatively low numbers of memory accesses per lookup. This makes them optimal for time sensitive applications like networking. Using cuckoo++ hash tables as a baseline, we propose a new data structure known as cuckoo prefix for the purpose of blocking IPs quickly with relatively little space. Leveraging IP subnets allows us to achieve similar throughput rates as implementations such as cuckoo++ with 8 times less memory usage. In addition, in this paper we offer a comparison of throughput and memory usage of several modern hash set and hash table implementations. In particular, we examine linear probing, robin hood hashing, bit sets (including EBVBL), and cuckoo hashing implementations to determine which provides the best throughput at the lowest memory cost.