Search

The supermarket model refers to a system with a large number of queues, where new customers choose $d$ d queues at random and join the one with the fewest customers. This model demonstrates the power of even small amounts of choice, as compared to simply joining a queue chosen uniformly at random, for load balancing systems. In this work we perform simulation-based studies to consider variations where service times for a customer are predicted, as might be done in modern settings using machine learning techniques or related mechanisms. Our primary takeaway is that using even seemingly weak predictions of service times can yield significant benefits over blind First In First Out queueing in this context. However, some care must be taken when using predicted service time information to both choose a queue and order elements for service within a queue; while in many cases using the information for both choosing and ordering is beneficial, in many of our simulation settings we find that simply using the number of jobs to choose a queue is better when using predicted service times to order jobs in a queue. In our simulations, we evaluate both synthetic and real-world workloads–in the latter, service times are predicted by machine learning. Our results provide practical guidance for the design of real-world systems; moreover, we leave many natural theoretical open questions for future work, validating their relevance to real-world situations. [ABSTRACT FROM AUTHOR]

The capacity of sticky channels, a subclass of insertion channels where each symbol may be duplicated multiple times, is considered. The primary result is to provide nearly tight numerical upper and lower bounds for the independent and identically distributed (i.i.d.) duplication channel. Index Terms--Capacity bounds, duplication channels, insertion/ deletion channels, sticky channels.

This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability d. It improves significantly upon the best previous framework used to obtain provable lower bounds on this capacity by utilizing a stronger definition of a typical output from the channel. The new results give the best known provable bounds on the capacity for all values of d. Moreover, the techniques presented here extend to yield lower bounds for channels with certain types of random insertions, namely, duplications, or combinations of duplications and deletions. To demonstrate these techniques in this context, two binary channels are analyzed: a channel where each transmitted bit is copied with probability v and a channel where each transmitted bit is copied a geometrically distributed number of times. Index Terms--Binary deletion channel, channel capacity, channels with synchronization errors.

We demonstrate polynomial-time deletion codes based on the verification-based decoding paradigm that come arbitrarily close to capacity. The random deletion channel takes n symbols from a q-ary alphabet, and each symbol is deleted independently with probability p. Taking advantage of recent improvements on the results of Luby and Mitzenmacher for verification-based decoding by Shokrollahi and Wang, we show how to design for any [member of] > 0 and sufficiently large n and q deletion codes with the following properties: the rate is (1 - p)(1 - [member of]), the failure probability is [n.sup.O(1/[[member of].sup.2])/q], and the computational complexity for encoding and decoding is [n.sup.O(1/[[member of].sup.2])/q] log q. We also extend these schemes to obtain the same results even if the undeleted symbols are also transposed arbitrarily, and if a sufficiently small number of random symbols are inserted. Index Terms--Deletion channel, low-density parity-check codes (LDPC), q-ary symmetric channel, verification-based decoding.

We present a simple proof that the capacity of the binary independent and identically distributed (i.i.d.) deletion channel, where each bit is deleted independently with probability d, is at least (1 - d)/9, by developing a correspondence between the deletion channel and an insertion/deletion channel that we call a Poisson-repeat channel. Index Terms--Binary deletion channel, channel capacity, insertion and/or deletion channels.

This correspondence considers binary deletion channels, where bits are deleted independently with probability d; it improves upon the framework used to analyze the capacity of binary deletion channels established by Diggavi and Grossglauser, improving on their lower bounds. Diggavi and Grossglauser considered codebooks with codewords generated by a first-order Markov chain. They only consider typical outputs, where an output is typical if an N bit input gives an N(1 - d)(1 - [member of]) bit output. The improvements in this correspondence arise from two considerations. First, a stronger notion of a typical output from the channel is used, which yields better bounds even for the codebooks studied by Diggavi and Grossglauser. Second, codewords generated by more general processes than first-order Markov chains are considered. Index Terms--Binary deletion channel, channel capacity, channels with memory.

We introduce and analyze verification-based decoding for low-density parity-check (LDPC) codes, an approach specifically designed to manipulate data in packet-sized units. Verification-based decoding requires only linear time for both encoding and decoding and succeeds with high probability under random errors. We describe how to utilize code scrambling to extend our results to channels with errors controlled by an oblivious adversary. Index Terms--Low-density parity-check (LDPC) codes, packet- based codes, q-ary symmetric channel, verification-based decoding.

We show that the following simple compression problem is NP-hard: given a collection of documents, find the pair of Huffman dictionaries that minimizes the total compressed size of the collection, where the best dictionary from the pair is used to compress each document. We also show the NP-hardness of finding optimal multiple preset dictionaries for LZ'77-based compression schemes. Our reductions make use of the catalog segmentation problem, a natural partitioning problem. Our results justify heuristic attacks used in practice. Index Terms--Huffman coding, LZ'77, NP-completeness, preset dictionaries, two-stage compression.

An early result in the history of power laws, due to Miller, concerned the following experiment. A monkey types randomly on a keyboard with N letters (N > 1) and a space bar, where a space separates words. A space is hit with probability p; all other letters are hit with equal probability (1 - p)/N. Miller proved that in this experiment, the rank-frequency distribution of words follows a power law. The case where letters are hit with unequal probability has been the subject of recent confusion, with some suggesting that in this case the rank-frequency distribution follows a lognormal distribution. We prove that the rank-frequency distribution follows a power law for assignments of probabilities that have rational log-ratios for any pair of keys, and we present an argument of Montgomery that settles the remaining cases, also yielding a power law. The key to both arguments is the use of complex analysis. The method of proof produces simple explicit formulas for the coefficient in the power law in cases with rational log-ratios for the assigned probabilities of keys. Our formula in these cases suggests an exact asymptotic formula in the cases with an irrational log-ratio, and this formula is exactly what was proved by Montgomery. Index Terms--Analytic information theory, analytic number theory, monkeys typing randomly, power laws, rank-frequency distribution.

We study the limits of performance of Gallager codes (low-density parity-check (LDPC) codes) over binary linear inter-symbol interference (ISI) channels with additive white Gaussian noise (AWGN). Using the graph representations of the channel, the code, and the sum-product message-passing detector/decoder, we prove two error concentration theorems. Our proofs expand on previous work by handling complications introduced by the channel memory. We circumvent these problems by considering not just linear Gallager codes but also their cosets and by distinguishing between different types of message flow neighborhoods depending on the actual transmitted symbols. We compute the noise tolerance threshold using a suitably developed density evolution algorithm and verify, by simulation, that the thresholds represent accurate predictions of the performance of the iterative sum-product algorithm for finite (but large) block lengths. We also demonstrate that for high rates, the thresholds are very close to the theoretical limit of performance for Gallager codes over ISI channels. If C denotes the capacity of a binary ISI channel and if [C.sub.i.i.d.] denotes the maximal achievable mutual information rate when the channel inputs are independent and identically distributed (i.i.d.) binary random variables ([C.sub.i.i.d.] [less than or equal to] C), we prove that the maximum information rate achievable by the sum-product decoder of a Gallager (coset) code is upper-bounded by [C.sub.i.i.d.]. The last topic investigated is the performance limit of the decoder if the trellis portion of the sum-product algorithm is executed only once; this demonstrates the potential for trading off the computational requirements and the performance of the decoder. Index Terms--Bahl-Cocke-Jelinek-Raviv (BCJR)-once bound, channel capacity, density evolution, Galager codes, independent and identically distributed (i.i.d.) capacity, intersymbol interference (ISI) channel, low-density parity-check (LDPC) codes, sum-product algorithm, turbo equalization.

It is shown that in a dynamic load balancing model that allows customers to choose between the shortest of two servers produces an exponential improvement, compared to distributing customers uniformly at random.

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. [ABSTRACT FROM AUTHOR]

As advances in technology allow for the collection, storage, and analysis of vast amounts of data, the task of screening and assessing the significance of discovered patterns is becoming a major challenge in data mining applications. In this work, we address significance in the context of frequent itemset mining. Specifically, we develop a novel methodology to identify a meaningful support threshold s* for a dataset, such that the number of itemsets with support at least s* represents a substantial deviation from what would be expected in a random dataset with the same number of transactions and the same individual item frequencies. These itemsets can then be flagged as statistically significant with a small false discovery rate. We present extensive experimental results to substantiate the effectiveness of our methodology. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractions of nodes of different degrees on both sides of the graph which is necessary and sufficient for the decoding process to finish successfully with high probability. By carefully designing these graphs we can construct for any given rate R and any given real number [Epsilon] a family of linear codes of rate R which can be encoded in time proportional to ln(1/[Epsilon]) times their block length n. Furthermore, a codeword can be recovered with high probability from a portion of its entries of length (1 + [Epsilon]) Rn or more. The recovery algorithm also runs in time proportional to n ln(1/[Epsilon]). Our algorithms have been implemented and work well in practice; various implementation issues are discussed. Index Terms--Erasure channel, large deviation analysis, low-density parity-check codes.

We construct new families of error-correcting codes based on Gallager's low-density parity-check codes. We improve on Gallager's results by introducing irregular parity-check matrices and a new rigorous analysis of hard-decision decoding of these codes. We also provide efficient methods for finding good irregular structures for such decoding algorithms. Our rigorous analysis based on martingales, our methodology for constructing good irregular codes, and the demonstration that irregular structure improves performance constitute key points of our contribution. We also consider irregular codes under belief propagation. We report the results of experiments testing the efficacy of irregular codes on both binary-symmetric and Gaussian channels. For example, using belief propagation, for rate 1/4 codes on 16000 bits over a binary-symmetric channel, previous low-density parity-check codes can correct up to approximately 16% errors, while our codes correct over 17%. In some cases our results come very close to reported results for turbo codes, suggesting that variations of irregular low density parity-check codes may be able to match or beat turbo code performance. Index Terms--Belief propagation, concentration theorem, Gallager codes, irregular codes, low-density parity-check codes.

In many applications, there is a need to identify to which of a group of sets an element $x$ belongs, if any. For example, in a router, this functionality can be used to determine the next hop of an incoming packet. This problem is generally known as set separation and has been widely studied. Most existing solutions make use of hash-based algorithms, particularly when a small percentage of false positives is allowed. A known approach is to use a collection of Bloom filters in parallel. Such schemes can require several memory accesses, a significant limitation for some implementations. We propose an approach using Block Bloom Filters, where each element is first hashed to a single memory block that stores a small Bloom filter that tracks the element and the set or sets the element belongs to. In a naïve solution, when an element $x$ in a set $S$ is stored, it necessarily increases the false positive probability for finding that $x$ is in another set $T$. In this paper, we introduce our One Memory Access Set Separation (OMASS) scheme to avoid this problem. OMASS is designed so that for a given element $x$, the corresponding Bloom filter bits for each set map to different positions in the memory word. This ensures that the false positive rates for the Bloom filters for element $x$ under other sets are not affected. In addition, OMASS requires fewer hash functions compared to the naïve solution. [ABSTRACT FROM PUBLISHER]

Research into the problem of load balancing in distributed computing systems in settings where old information on queue lengths can be used constructively by new incoming tasks.

In a standard multiple-choice hashing scheme, each item is stored in one of d\geq 2 hash table buckets. The availability of choice in where items are stored improves space utilization. These schemes are often very amenable to a hardware implementation, such as in a router. Recently, researchers have discovered powerful variants where items already in the hash table may be moved during the insertion of a new item. Unfortunately, these schemes occasionally require a large number of items to be moved to perform an insertion, making them inappropriate for a hardware implementation. We show that it is possible to significantly increase the space utilization of multiple-choice hashing schemes by allowing at most one item to be moved during an insertion. Furthermore, our schemes can be effectively analyzed, optimized, and compared using numerical methods based on fluid limit arguments, without resorting to much slower simulations. [ABSTRACT FROM PUBLISHER]

We consider deletion channels and insertion channels under an additional segmentation assumption: the input consists of disjoint segments of b consecutive bits, with at most one error per segment. Under this assumption, we demonstrate simple and computationally efficient deterministic encoding and decoding schemes that achieve a high provable rate even under worst case errors. We also consider more complex schemes that experimentally achieve higher rates under random error. [ABSTRACT FROM AUTHOR]

Cuckoo hashing holds great potential as a high-performance hashing scheme for real applications. Up to this point, the greatest drawback of cuckoo hashing appears to be that there is a polynomially small but practically significant probability that a failure will occur during the insertion of an item, requiring an expensive rehashing of all items in the table. In this paper, we show that this failure probability can be dramatically reduced by the addition of a very small constant-sized stash. We demonstrate both analytically and through simulations that stashes of size equivalent to only three or four items yield tremendous improvements, enhancing cuckoo hashing's practical viability in both hardware and software. Our analysis naturally extends previous analyses of multiple cuckoo hashing variants, and the approach may prove useful in further related schemes. [ABSTRACT FROM AUTHOR]

We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied secretary problem. Like the secretary problem, it captures fundamental aspects of decision making under uncertainty and has many possible applications. We analyze natural strategies of hiring above the current average, considering both the mean and the median averages; we call these Lake Wobegon strategies. Like the hiring problem itself, our strategies are intuitive, simple to describe, and amenable to mathematically and economically significant modifications. We demonstrate several intriguing behaviors of the two strategies. Specifically, we show dramatic differences between hiring above the mean and above the median. We also show that both strategies are intrinsically connected to the lognormal distribution, leading to only very weak concentration results, and the marked importance of the first few hires on the overall outcome. [ABSTRACT FROM AUTHOR]

We demonstrate an efficient data-parallel algorithm for building large hash tables of millions of elements in real-time. We consider two parallel algorithms for the construction: a classical sparse perfect hashing approach, and cuckoo hashing, which packs elements densely by allowing an element to be stored in one of multiple possible locations. Our construction is a hybrid approach that uses both algorithms. We measure the construction time, access time, and memory usage of our implementations and demonstrate real-time performance on large datasets: for 5 million key-value pairs, we construct a hash table in 35.7 ms using 1.42 times as much memory as the input data itself and we can access all the elements in that hash table in 15.3 ms. For comparison, sorting the same data requires 36.6 ms, but accessing all the elements via binary search requires 79.5 ms. Furthermore, we show how our hashing methods can be applied to two graphics applications: 3D surface intersection for moving data and geometric hashing for image matching. [ABSTRACT FROM AUTHOR]