Search

Private set intersection (PSI) allows two parties to compute the intersection of their data without revealing the data they possess that is outside of the intersection. However, in many cases of joint data analysis, the intersection is also sensitive. We define differentially private set intersection and we propose new protocols using (leveled) homomorphic encryption where the result is differentially private. Our circuit-based approach has an adaptability that allows us to achieve differential privacy, as well as to compute predicates over the intersection such as cardinality. Furthermore, our protocol produces differentially private output for set intersection and set intersection cardinality that is optimal in terms of communication and computation complexity. For a client set of size $m$ and a server set of size $n$ , where $m$ is smaller than $n$ , our communication complexity is $O(m)$ while previous circuit-based protocols only achieve $O(n+m)$ communication complexity. In addition to our asymptotic optimizations which include new analysis for using nested cuckoo hashing for PSI, we demonstrate the practicality of our protocol through an implementation that shows the feasibility of computing the differentially private intersection for large data sets containing millions of elements.

Bloom filters (BFs) are fast and space-efficient data structures used for set membership queries in many applications. BFs are required to satisfy three key requirements: low space cost, high-speed lookups, and fast updates. Prior works do not satisfy these requirements at the same time. The standard BF does not support deletions of items and the variants that support deletions need additional space or performance overhead. The state-of-the-art cuckoo filters (CF) has high performance with seemingly low space cost. However, the CF suffers a critical issue of varying space cost per item. This is because the exclusive-OR (XOR) operation used by the CF requires the total number of buckets to be a power of two, leading to the space inflation. To address the issue, in this paper we propose a scalable variant of the cuckoo filter called additive and subtractive cuckoo filter (ASCF). We aim to improve the space efficiency while sustaining comparably high performance. The ASCF uses the addition and subtraction (ADD/SUB) operations instead of the XOR operation to compute an item's two candidate bucket indexes based on its fingerprint. Experimental results show that the ASCF achieves both low space cost and high performance. Compared to the CF, the ASCF reduces up to 1.9x space cost per item while maintaining the same lookup and update throughput. In addition, the ASCF outperforms other filters in both space cost and performance.

Motivation With an increasing number of patient-derived xenograft (PDX) models being created and subsequently sequenced to study tumor heterogeneity and to guide therapy decisions, there is a similarly increasing need for methods to separate reads originating from the graft (human) tumor and reads originating from the host species’ (mouse) surrounding tissue. Two kinds of methods are in use: On the one hand, alignment-based tools require that reads are mapped and aligned (by an external mapper/aligner) to the host and graft genomes separately first; the tool itself then processes the resulting alignments and quality metrics (typically BAM files) to assign each read or read pair. On the other hand, alignment-free tools work directly on the raw read data (typically FASTQ files). Recent studies compare different approaches and tools, with varying results. Results We show that alignment-free methods for xenograft sorting are superior concerning CPU time usage and equivalent in accuracy. We improve upon the state of the art sorting by presenting a fast lightweight approach based on three-way bucketed quotiented Cuckoo hashing. Our hash table requires memory comparable to an FM index typically used for read alignment and less than other alignment-free approaches. It allows extremely fast lookups and uses less CPU time than other alignment-free methods and alignment-based methods at similar accuracy. Several engineering steps (e.g., shortcuts for unsuccessful lookups, software prefetching) improve the performance even further. Availability Our software xengsort is available under the MIT license at http://gitlab.com/genomeinformatics/xengsort. It is written in numba-compiled Python and comes with sample Snakemake workflows for hash table construction and dataset processing.

The unprecedented growth in the memory needs of emerging memory-intensive workloads has made virtual memory translation a major performance bottleneck. To address this problem, this paper introduces Elastic Cuckoo Page Tables, a novel page table design that transforms the sequential pointer-chasing operation used by conventional multi-level radix page tables into fully-parallel look-ups. The resulting design harvests, for the first time, the benefits of memory level parallelism for address translation. Elastic cuckoo page tables use Elastic Cuckoo Hashing, a novel extension of cuckoo hashing that supports efficient page table resizing. Elastic cuckoo page tables efficiently resolve hash collisions, provide process-private page tables, support multiple page sizes and page sharing among processes, and dynamically adapt page table sizes to meet application requirements. We evaluate elastic cuckoo page tables with full-system simulations of an 8-core processor using a set of graph analytics, bioinformatics, HPC, and system workloads. Elastic cuckoo page tables reduce the address translation overhead by an average of 41% over conventional radix page tables. The result is a 3-18% speed-up in application execution.

An important function in modern routers and switches is to perform a lookup for a key. Hash-based methods, and in particular cuckoo hash tables, are popular for such lookup operations, but for large structures stored in off-chip memory, such methods have the downside that they may require more than one off-chip memory access to perform the key lookup. Although the number of off-chip memory accesses can be reduced using on-chip approximate membership structures such as Bloom filters, some lookups may still require more than one off-chip memory access. This can be problematic for some hardware implementations, as having only a single off-chip memory access enables a predictable processing of lookups and avoids the need to queue pending requests. We provide a data structure for hash-based lookups based on cuckoo hashing that uses only one off-chip memory access per lookup, by utilizing an on-chip pre-filter to determine which of multiple locations holds a key. We make particular use of the flexibility to move elements within a cuckoo hash table to ensure the pre-filter always gives the correct response. While this requires a slightly more complex insertion procedure and some additional memory accesses during insertions, it is suitable for most packet processing applications where key lookups are much more frequent than insertions. An important feature of our approach is its simplicity. Our approach is based on simple logic that can be easily implemented in hardware, and hardware implementations would benefit most from the single off-chip memory access per lookup.

As far as we know, we are the first to propose a general framework to incorporate the quantization-based methods into the conventional similarity-preserving hashing, in order to improve the effectiveness of hashing methods. In theory, any quantization method can be adopted to reduce the quantization error of any similarity-preserving hashing methods to improve their performance.This framework can be applied to both unsupervised and supervised hashing. We experimentally obtained the best performance compared to state-ofthe-art supervised and unsupervised hashing methods on six popular datasets.We successfully show it to work on a huge dataset SIFT1B (1 billion data points) by utilizing the graph approximation and out-of-sample extension. Nowadays, due to the exponential growth of user generated images and videos, there is an increasing interest in learning-based hashing methods. In computer vision, the hash functions are learned in such a way that the hash codes can preserve essential properties of the original space (or label information). Then the Hamming distance of the hash codes can approximate the data similarity. On the other hand, vector quantization methods quantize the data into different clusters based on the criteria of minimal quantization error, and then perform the search using look-up tables. While hashing methods using Hamming distance can achieve faster search speed, their accuracy is often outperformed by quantization methods with the same code length, due to the low quantization error and more flexible distance lookups. To improve the effectiveness of the hashing methods, in this work, we propose Quantization-based Hashing (QBH), a general framework which incorporates the advantages of quantization error reduction methods into conventional property preserving hashing methods. The learned hash codes simultaneously preserve the properties in the original space and reduce the quantization error, and thus can achieve better performance. Furthermore, the hash functions and a quantizer can be jointly learned and iteratively updated in a unified framework, which can be readily used to generate hash codes or quantize new data points. Importantly, QBH is a generic framework that can be integrated to different property preserving hashing methods and quantization strategies, and we apply QBH to both unsupervised and supervised hashing models as showcases in this paper. Experimental results on three large-scale unlabeled datasets (i.e., SIFT1M, GIST1M, and SIFT1B), three labeled datastes (i.e., ESPGAME, IAPRTC and MIRFLICKR) and one video dataset (UQ_VIDEO) demonstrate the superior performance of our QBH over existing unsupervised and supervised hashing methods.

Hashing is a useful technique for fast nearest neighbor search due to its low storage cost and fast query speed. Unsupervised hashing aims at learning binary hash codes for the original features so that the pairwise distances can be best preserved. While several works have targeted on this task, the results are not satisfactory mainly due to the over-simplified model. In this paper, we propose a unified and concise unsupervised hashing framework, called binary multidimensional scaling , which is able to learn the hash code for distance preservation in both batch and online mode. In the batch mode, unlike most existing hashing methods, we do not need to simplify the model by predefining the form of hash map. Instead, we learn the binary codes directly based on the pairwise distances among the normalized original features by alternating minimization. This enables a stronger expressive power of the hash map. In the online mode, we consider the holistic distance relationship between current query example and those we have already learned, rather than only focusing on current data chunk. It is useful when the data come in a streaming fashion. Empirical results show that while being efficient for training, our algorithm outperforms state-of-the-art methods by a large margin in terms of distance preservation, which is practical for real-world applications.

To overcome the barrier of storage and computation when dealing with gigantic-scale data sets, compact hashing has been studied extensively to approximate the nearest neighbor search. Despite the recent advances, critical design issues remain open in how to select the right features, hashing algorithms, and/or parameter settings. In this paper, we address these by posing an optimal hash bit selection problem, in which an optimal subset of hash bits are selected from a pool of candidate bits generated by different features, algorithms, or parameters. Inspired by the optimization criteria used in existing hashing algorithms, we adopt the bit reliability and their complementarity as the selection criteria that can be carefully tailored for hashing performance in different tasks. Then, the bit selection solution is discovered by finding the best tradeoff between search accuracy and time using a modified dynamic programming method. To further reduce the computational complexity, we employ the pairwise relationship among hash bits to approximate the high-order independence property, and formulate it as an efficient quadratic programming method that is theoretically equivalent to the normalized dominant set problem in a vertex- and edge-weighted graph. Extensive large-scale experiments have been conducted under several important application scenarios of hash techniques, where our bit selection framework can achieve superior performance over both the naive selection methods and the state-of-the-art hashing algorithms, with significant accuracy gains ranging from 10% to 50%, relatively.

One of the important tasks for most network security solutions is to track network flows in real-time. The universe of flow identifiers being huge, hash tables with their fast operations are well suited for this task. In order to overcome the limitations of traditional hash tables, the research community have come up with different improved variants; two of the well-knowns being Cuckoo and Peacock hash tables. Yet, network flows have interesting characteristics that can be exploited for tracking flows more efficiently. Besides, the existing hash tables are vulnerable to attacks. In this context, we design, develop and evaluate REX, a resilient and efficient data structure for tracking of network flows. REX is designed to make good use of, both, the characteristics of Internet traffic, as well as the different memory technologies. REX stores most commonly updated flows in the faster and smaller SRAM, while storing the rest in DRAM. We conducted extensive experiments using real network traffic to evaluate and compare REX, Cuckoo and Peacock hash tables. The results demonstrate, under both normal and attack scenarios, that REX not only rejects the least number of packets, but also significantly reduces the total time taken for the important hash table operations.

With the rapid growth of the amount of information, cloud computing servers need to process and analyze large amounts of high-dimensional and unstructured data timely and accurately. This usually requires many query operations. Due to simplicity and ease of use, cuckoo hashing schemes have been widely used in real-world cloud-related applications. However, due to the potential hash collisions, the cuckoo hashing suffers from endless loops and high insertion latency, even high risks of re-construction of entire hash table. In order to address these problems, we propose a cost-efficient cuckoo hashing scheme, called MinCounter. The idea behind MinCounter is to alleviate the occurrence of endless loops in the data insertion by selecting unbusy kicking-out routes. MinCounter selects the “cold” (infrequently accessed), rather than random, buckets to handle hash collisions. We further improve the concurrency of the MinCounter scheme to pursue higher performance and adapt to concurrent applications. MinCounter has the salient features of offering efficient insertion and query services and delivering high performance of cloud servers, as well as enhancing the experiences for cloud users. We have implemented MinCounter in a large-scale cloud testbed and examined the performance by using three real-world traces. Extensive experimental results demonstrate the efficacy and efficiency of MinCounter.

Set synchronization, which targets at identifying and then exchanging the different elements between two given sets, is a fundamental task in distributed applications and implementations. Existing methods that synchronize simple sets are mainly based on compact data structures such as Bloom filter and its variants. However, these methods are infeasible to synchronize a pair of multisets that allow an element to appear multiple times. To this end, in this paper, we propose to leverage the counting cuckoo filter (CCF), a novel variant of cuckoo filter, to represent and, after that, synchronize a pair of multisets. The cuckoo filter (CF) is a minimized hash table that uses cuckoo hashing to resolve collisions. CF has an array of buckets, each of which has multiple slots to store element fingerprints. Based on CF, CCF extends each slot as two fields, the fingerprint field, and the counter field. The fingerprint field records the fingerprint of element which is stored by this slot; while the counter field counts the multiplicity of the stored element. With such a design, CCF is competent to represent any multiset. After generating and exchanging the respective CCFs which represent the local multisets, we propose a query-based and decoding-based methods to identify the different elements between the given multisets. The comprehensive evaluation results indicate that CCF outperforms its same kind in terms of both synchronization accuracy and the space-efficiency, at the cost of a little higher time-consumption.

Talek is a private group messaging system that sends messages through potentially untrustworthy servers, while hiding both data content and the communication patterns among its users. Talek explores a new point in the design space of private messaging; it guarantees access sequence indistinguishability, which is among the strongest guarantees in the space, while assuming an anytrust threat model, which is only slightly weaker than the strongest threat model currently found in related work. Our results suggest that this is a pragmatic point in the design space, since it supports strong privacy and good performance: we demonstrate a 3-server Talek cluster that achieves throughput of 9,433 messages/second for 32,000 active users with 1.7-second end-to-end latency. To achieve its security goals without coordination between clients, Talek relies on information-theoretic private information retrieval. To achieve good performance and minimize server-side storage, Talek introduces new techniques and optimizations that may be of independent interest, e.g., a novel use of blocked cuckoo hashing and support for private notifications. The latter provide a private, efficient mechanism for users to learn, without polling, which logs have new messages.

In this paper, we propose a new private set intersection (PSI) protocol with bi-oblivious data transfer that computes the following functionality. The two parties (P1 and P2) input two sets of items (X and Y, respectively) and one of the parties (P2) outputs fi(bi) for each yi∈ Y, where bi is 0 or 1 depending on the truth value of yi∈ ? X and fi is defined by the other party (P1) as taking 1-bit input and outputting the party’s (P1’s) data to be transferred. This functionality is generally required when the PSI protocol is used as a part of a larger secure two-party secure computation such as threshold PSI or any function of the whole intersecting set in general. Pinkas et al. presented a PSI protocol at Eurocrypt 2019 for this functionality, which has linear complexity only in communication. While there are PSI protocols with linear computation and communication complexities in the classical PSI setting where the intersection itself is revealed to one party, to the best of our knowledge, there is no PSI protocol, which outputs a function of the membership results and satisfies linear complexity in both communication and computation. We present the first PSI protocol that outputs only a function of the membership results with linear communication and computation complexities. While creating the protocol, as a side contribution, we provide a one-time batch oblivious programmable pseudo-random function based on garbled Bloom filters. We also implemented our protocol and provide performance results., Scientific and Technological Research Council of Turkey (TÜBİTAK)

Bloom filters are widely used in networking to accelerate checks and in particular to avoid accessing slow memories when a match will not be found. Unfortunately, filtering requires several on-chip memory bits per element and thus when the tables are large and the on-chip memory small is not applicable. In those cases, caching the most frequently accessed elements on-chip seems the only viable option. However, the key is typically formed by several packet header fields, which means that each cache entry consumes a significant amount of on-chip memory bits. In this paper, an efficient scheme to cache negatives, that is elements that will not find a match on the table is presented. In more detail, the proposed scheme enables the caching of negatives using less than 16 bits per entry regardless of the size of the key. This translates to a reduction of at least 6x in the size of the cache when used for example flow tracking.

We introduce the adaptive cuckoo filter (ACF), a data structure for approximate set membership that extends cuckoo filters by reacting to false positives, removing them for future queries. As an example application, in packet processing queries may correspond to flow identifiers, so a search for an element is likely to be followed by repeated searches for that element. Removing false positives can therefore significantly lower the false-positive rate. The ACF, like the cuckoo filter, uses a cuckoo hash table to store fingerprints. We allow fingerprint entries to be changed in response to a false positive in a manner designed to minimize the effect on the performance of the filter. We show that the ACF is able to significantly reduce the false-positive rate by presenting both a theoretical model for the false-positive rate and simulations using both synthetic data sets and real packet traces.

Modern distributed key-value store-based applications rely on bulk-read operations like 'Multi-Get' (MGet) to accelerate their data serving phase. While state-of-the-art database systems employ SIMD-based techniques to optimize data-parallel operations on their in-memory structures, such as hash-tables, they have not been adapted into high-performance RDMA-accelerated key-value (KV) stores. In this paper, we present a holistic approach to designing high-performance SIMD-aware KV stores for emerging multi-core CPU architectures. Towards this, we first perform an in-depth study of the opportunities and challenges involved in leveraging AVX-512 vectorization-based parallel hash table designs with a state-of-the-art high-performance key-value store like RDMA-Memcached. Based on this, we propose a SIMD-Aware Client-Centric and Optimistic RDMA-based Key-Value Store, SCOR-KV, that optimally exploits 'RDMA+SIMD' to accelerate read-heavy MGet operations. SCOR-KV presents an SIMD-conscious KV store friendly hash table layout, that leverages the vertically vectorized N-way cuckoo hash table design with optimistic KV pair lookup schemes. To complement this, we propose RDMA-optimized SIMD-aware MGet communication protocols that offload the server-side pre-/post-processing overheads to the client, while enabling optimal end-to-end performance. Our performance evaluations over the latest Intel Skylake CPUs and IB EDR interconnects show that our proposed SCOR-KV can achieve up to 3.7-8.6x improvement in server-side Get throughput. Through our SIMD-aware RDMA schemes, SCOR-KV can also improve Multi-Get latencies for read-heavy YCSB workloads by about 2.2x, as compared to the RDMA-Memcached design running over the state-of-the-art CPU-optimized MemC3 hash table design.

Hash tables have been broadly used in many security applications. These applications require fast query speed and high memory efficiency. However, the query speed degrades when hash collisions happen. The design goal of this paper is to achieve high load factor as well as fast query at the same time. In this paper, we propose a novel hashing scheme, namely the Shifting Hash Table (SHT), which consists of two parts. The first part is an enhanced version of the Bloom filter checking which subtable(s) may contain the incoming items, and the second part contains a cuckoo hashing based hash table which stores the key-value pairs. The key technique of this paper is that we divide items into two categories: at-home and abroad. We only insert the second kind of items (abroad) into the Bloom filter, thus the memory usage of the filter is significantly reduced. We conducted extensive experiments and the results show that SHT significantly outperforms the state-of-the-art. Specifically, SHT can query an item using on average less than 1.05 bucket probes and even using 1 bit per entry in the fast memory, and achieve a high load factor which is 95% at the same time.

Hash Tables play a lead role in modern databases systems during the execution of joins, grouping, indexing, removal of duplicates, and accelerating point queries. In this paper, we focus on Cuckoo Hash, a technique to deal with collisions guaranteeing that data is retrieved with at most two memory access in the worst case. However, building the Cuckoo Table with the current scalar methods is inefficient when treating the eviction of the colliding keys. We propose a Vertically Vectorized data-dependent method to build Cuckoo Tables - ViViD Cuckoo Hash. Our method exploits data parallelism with AVX-512 SIMD instructions and transforms control dependencies into data dependencies to make the build process faster with an overall reduction in response time by 90% compared to the scalar Cuckoo Hash.

We investigate concretely efficient protocols for distributed oblivious linear evaluation over vectors (Vector-OLE). Boyle et al. (CCS 2018) proposed a protocol for secure distributed pseudorandom Vector-OLE generation using sublinearcommunication, but they did not provide an implementation. Their construction is based on a variant of the LPN assumption and assumes a distributed key generation protocol for single-point Function Secret Sharing (FSS), as well as an efficient batching scheme to obtain multi-point FSS. We show that this requirement can be relaxed, resulting in a weaker variant of FSS, for which we give an efficient protocol. This allows us to use efficient probabilistic batch codes that were also recently used for batched PIR by Angel et al. (S&P 2018). We construct a full Vector-OLE generator from our protocols, and compare it experimentally with alternative approaches. Our implementation parallelizes very well, and has low communication overhead in practice. For generating a VOLE of size $2^20 $, our implementation only takes $0.52$s on 32 cores.

This paper presents a performance comparison of the cuckoo hash table and Bloom filter for packet classification with application in packet filtering with emphasis on lawful interception systems. Alongside enabling fast packet capture on commodity hardware, Data Plane Development Kit offers those methods already implemented in its library. We have chosen the cuckoo hash table as an exact classification method and the Bloom filter as a space-efficient probabilistic method that should have a better cache utilization and therefore more viable usage in performance critical systems, but allows false positive results. The execution time and memory requirements of the two methods are compared to determine whether the performance benefits of using a probabilistic method outweigh its drawbacks, and in which context those benefits arise.

In recent years, a variety of methods for low-latency key-value store (KVS), such as remote direct memory access (RDMA), have been proposed. However, a majority of KVS systems do not support to access and query data stored in multiple versions, making them inapplicable to application scenarios like snapshot. In this paper, we present a low-latency multi-version in-memory KVS on an FPGA-CPU platform. In order to reduce latency, we store all keys into a hash table using cuckoo hashing on an FPGA board and organize each group of version-value pairs that are corresponded with the identical key into a B-tree in the host memory. The proposed architecture can perform put, get, delete, CAS, getPredecessor and range query operations within a B-tree. Every operation except range query can be completed bypassing the host CPU. The experimental results show that the average latency of get operation within a B-tree of 5 levels is less than 8?s which is at least 9x faster than other implementations with the help of CPU.

Directories for cache coherence have been recently shown to be vulnerable to conflict-based side-channel attacks. By forcing directory conflicts, an attacker can evict victim directory entries, which in turn trigger the eviction of victim cache lines from private caches. This evidence strongly suggests that directories need to be redesigned for security. The key to a secure directory is to block interference between processes. Sadly, in an environment with many cores, this is hard or expensive to do. This paper presents the first design of a scalable secure directory. We call it SecDir. SecDir takes part of the storage used by a conventional directory and re-assigns it to per-core private directory areas used in a victim-cache manner called Victim Directories (VDs). The partitioned nature of VDs prevents directory interference across cores, defeating directory side-channel attacks. The VD of a core is distributed, and holds as many entries as lines in the private L2 cache of the core. To minimize victim self-conflicts in a VD during an attack, a VD is organized as a cuckoo directory. Such a design also obscures the victim's conflict patterns from the attacker. For our evaluation, we model with simulations the directory of an Intel Skylake-X server with and without SecDir. Our results show that SecDir has a negligible performance overhead. Furthermore, SecDir is area-efficient.

Cuckoo hashing is widely used for its worst-case constant lookup performance even at very high load. However at high load, collision resolution will involve lots of probes on item relocation and may still fail in the end. To address the problem, we propose an efficient Cuckoo hashing scheme called Multi-copy Cuckoo or McCuckoo. Different from the blind kick-outs of standard Cuckoo hashing during a collision, we can foresee which way to successfully kick items by using multiple copies. Furthermore, with the knowledge of how many copies each item has in the table, we can identify impossible buckets and skip them during a lookup. In order to avoid expensive rehashing during insertion failures, McCuckoo also supports more efficient stash strategy that minimizes stash checking. McCuckoo uses simple logic and simple data structure, so it is suitable for both software and hardware implementation on platforms where intensive access to the slow and bandwidth limited off-chip external memory is the main bottleneck.

In modern switches, a packet can go through a number of processing steps to determine, for example, if the packet has to be discarded due to security policies, if it needs to be marked for quality of service or to determine the next hop for the packet. Most of those steps can be modeled as a matching of some of the packet fields with a set of rules that are stored in the switch. This has been generalized with the adoption of Software Defined Networks, using for example, the Openflow protocol, on which the processing steps are programmable as table matching operations and defined dynamically by a controller. Implementing this flexible packet matching in a switch is challenging, as we need to support multiple matching tables, each having different key size, and the size of the tables should also be programmable. The main options to support multiple tables are to use different memories for each table or to have several tables share the same memories. In the first approach, each table would have to match the size and width of the memories to achieve an efficient memory usage. This is a severe limitation when flexible table size and entry width need to be supported. In the second approach, all the tables can dynamically share the memories, providing better flexibility. The problem is that the width of the memories needs to be dimensioned to support the largest entry size. This leads to significant memory waste for smaller entries. Hash based techniques like cuckoo hashing can be used to efficiently implement exact matching using standard SRAM memories, and are widely used in modern switches. However, current implementations only support entries of one size. This article presents the Single Double cuckoo hash, which can support elements of two sizes. Its main benefit is to improve memory utilization when multiple tables with entries of different sizes share the same memories. This is achieved at the cost of a small increase in circuit complexity.

Similarity-preserving hashing is a widely used method for nearest neighbor search in large-scale image retrieval. Recently, supervised hashing methods are appealing in that they learn compact hash codes with fewer bits by incorporating supervised information. In this paper, we propose a new two-stage supervised hashing methods which decomposes the hash learning process into a stage of learning approximate hash codes followed by a stage of learning hash functions. In the first stage, we propose a margin-based objective to find approximate hash codes such that a pair of hash codes associating to a pair of similar (dissimilar) images has sufficiently small (large) Hamming distance. This objective results in a challenging optimization problem. We develop a coordinate descent algorithm to efficiently solve this optimization problem. In the second stage, we use convolutional neural networks to learn hash functions. We conduct extensive evaluations on several benchmark datasets with different kinds of images. The results show that the proposed margin-based hashing method has substantial improvement upon the state-of-the-art supervised or unsupervised hashing methods.

By leveraging the uneven distribution of traffic among network flows, the authors improve the query throughput of Cuckoo hashing. They achieve this by placing the most frequently used items in the table that's accessed first during the Cuckoo query operation. Their scheme is named Cuckoo cache, as it's conceptually similar to a cache but implemented inside the Cuckoo hash with little additional cost. Cuckoo cache is evaluated using a traffic monitoring application fed with real traces. The results are compared with existing Cuckoo hashing implementations and show significant improvements.

FPGAs rely on massive datapath parallelism to accelerate applications even with a low clock frequency. However, applications such as sparse linear algebra and graph analytics have their throughput limited by irregular accesses to external memory for which typical caches provides little benefit because of very frequent misses. Non-blocking caches are widely used on CPUs to reduce the negative impact of misses and thus increase performance of applications with low cache hit rate; however, they rely on associative lookup for handling multiple outstanding misses, which limits their scalability, especially on FPGAs. This results in frequent stalls whenever the application has a very low hit rate. In this paper, we show that by handling thousands of outstanding misses without stalling we can achieve a massive increase of memory-level parallelism, which can significantly speed up irregular memory-bound latency-insensitive applications. By storing miss information in cuckoo hash tables in block RAM instead of associative memory, we show how a non-blocking cache can be modified to support up to three orders of magnitude more misses. The resulting miss-optimized architecture provides new Pareto-optimal and even Pareto-dominant design points in the area-delay space for twelve large sparse matrix-vector multiplication benchmarks, providing up to 25% speedup with 24x area reduction or to 2x speedup with similar area compared to traditional hit-optimized architectures.

A membership identification is a key functionality in many network applications. Various data structures have been introduced in order to support the efficient membership identification. Since a Bloom filter can provide simple but efficient membership checking, it is widely used in many network applications. However, the query results of Bloom filters can have false positives, which can degrade the search performance. Thus, reducing false positives of Bloom filters is challenging. In order to reduce the false positive rate, this paper proposes to use two sets of hash functions: primary and secondary. When the cell referenced by the primary hash function is occupied, the value of that cell is relocated to a cell referenced by the secondary hash functions like in the cuckoo hash. The proposed structure is evaluated using various sets, and the simulation results show that the proposed scheme can reduce the false positive rates.

This paper introduces CuCoTrack, a cuckoo hash based data structure designed to efficiently implement connection tracking. The proposed scheme exploits the fact that queries always match one existing connection to compress the 5-tuple that identifies the connection. This significantly reduces the amount of memory needed to store the connections and also the memory bandwidth needed for lookups. CuCoTrack uses a dynamic fingerprint to avoid collisions thus ensuring that queries are completed in at most two memory accesses and facilitating a hardware implementation. The proposed scheme has been analyzed theoretically and validated by simulation. The results show that using 16 bits for the fingerprint is enough to avoid collisions in practical configurations.

Packet classification is one of the core functions in present-day networking applications. Various classification algorithms have been developed, including tuple space search (TSS) which is used in the Open vSwitch due to its flexibility and scalability. In order to solve the problem of excessive memory access to the vast rule-set stored off-chip, many algorithms adopt bloom filter (BF) to reduce unnecessary accesses. However, deteriorated false positive and increased collisions at high load ratio may still be a problem. Here in this paper a new tuple pruning based packet classification algorithm is proposed that can achieve much reduced off-chip access per-lookup even at high load by adopting a better compact structure on-chip and Cuckoo hash off-chip. At the same time, we can accelerate the classification rate further by optimizing the search sequence of tuples making it more likely to find the matching rules earlier. Experimental results show that with the proposed mechanism the off-chip table lookup time is only 1/3 to 1/4 of the baseline BF- based scheme.

Many network functions are moving from hardware to software to get better programmability and lower cost. Measurement is critical to most network functions because getting detailed information about traffic is often the first step to make control decisions and diagnose problems. The key challenge for measurement is how to keep a large number of counters while processing packets at line rate. Previous work on measurement algorithms mostly focuses on reducing memory usage while achieving high accuracy. However, software servers have plenty of memory but incur new challenges of achieving both high performance and high accuracy. In this paper, we revisit the measurement algorithms and data structures under the new metrics of performance and accuracy. We show that saving memory through extra computation is not worthwhile. As a result, a linear hash table and count array outperform more complex data structures such as Cuckoo hashing, Count-Min sketches, and heaps in a variety of scenarios.

Phase Change Memory (PCM) is emerging as an attractive alternative to Dynamic Random Access Memory (DRAM) in building data-intensive computing systems. PCM offers read/write performance asymmetry that makes it necessary to revisit the design of in-memory applications. In this paper, we focus on in-memory hash tables, a family of data structures with wide applicability. We evaluate several popular hash-table designs to understand their performance under PCM. We find that for write-heavy workloads the designs that achieve best performance for PCMdiffer from the ones that are best for DRAM, and that designs achieving a high load factor also cause a high number of memory writes. Finally, we propose PFHT, a PCM-Friendly Hash Table which presents a cuckoo hashing variant that is tailored to PCM characteristics, and offers a better trade-off between performance, the amount of writes generated, and the expected load factor than any of the existing DRAMbased implementations.

Cuckoo hashing has proven to be an efficient option to implement exact matching in networking applications. It provides good memory utilization and deterministic worst case access time. The continuous increase in speed and complexity of networking devices creates a need for higher throughput exact matching in many applications. In this paper, a new Cuckoo hashing implementation named parallel d-pipeline is proposed to increase throughput. The scheme presented is targeted to implementations in which the tables are accessed in parallel. A parallel implementation increases the throughput and therefore is well suited to high speed applications. Parallel schemes are common for ASIC/FPGA implementations in which the tables are stored in several embedded memories. Using the proposed technique, the throughput can be significantly increased with gains that in practical scenarios can reach 60 percent compared to existing parallel implementations. The new scheme has been evaluated using a case study and detailed results for performance and implementation costs are reported.