Approximate nearest neighbor search under universal Lp metrics (ANNS-U-Lp) is an important and challenging research problem, as it requires answering queries under all possible p (0.5 to 2) values simultaneously without building an index for each possible p value. The state-of-the-art solution, called MLSH, is a Locality-Sensitive Hashing (LSH)-based ANNS method with barely acceptable query performance. In contrast, graph-based ANNS methods, which offer significantly improved query efficiency on the ANNS-Lp problem (with a fixed p-value), cannot be naively extended to the ANNS-U-Lp problem. In this paper, we propose U-HNSW, the first graph-based method for ANNS-U-Lp. Our scheme uses HNSW graph indexes built on two base metrics (L1 and L2) to generate promising NN candidates, and then verifies these candidates with an early-termination strategy. Experimental results show that U-HNSW not only achieves up to 2670 times shorter query time than the original MLSH implementation running on a RAM disk, but also outperforms the original HNSW on the ANNS-Lp problem, except for a few special p values.

In this work, we solve a long-standing open problem in coding theory with broad applications in networking and systems: designing an erasure code that simultaneously satisfies three requirements: (1) high coding efficiency, (2) low coding complexity, and (3) being a streaming code (defined as one with low decoding latency). We propose METTLE (Multi-Edge Type with Touch-less Leading Edge), the first erasure code to meet all three requirements. Compared to "streaming RaptorQ" (RaptorQ configured with a small source block size to ensure a low decoding latency), METTLE is only slightly worse in coding efficiency, but 47.7 to 84.6 times faster to decode.

The relentless growth of sizes and traffic volumes in data center networks (DCN) is posing a significant challenge on switching: A single giant switch in a modern flattened-topology DCN needs to direct terabits of traffic per second to hundreds of top-of-rack switches in a low latency of just a few milliseconds. The vast majority of existing switching schedulers have yet to address this challenge: Traffic-oblivious RODCN (reconfigurable optical DCN) schedulers do not have high throughput utilization, whereas on-demand hybrid (circuit and packet) switching schedulers are too computationally expensive. To this end, we propose an efficient and performant hybrid switching scheduler, named QPS-Fit, which computes high-quality on-demand schedules in a fully parallelizable way. Our algorithm simultaneously fits many transmissions into the schedule, all by parallel “dirt-cheap” request-grant message exchanges between input and output ports. According to our simulation, QPS-Fit achieves similar throughput utilization as BFF, the state-of-the-art on-demand hybrid switching scheduler, while being nearly 27× faster when running on 96 threads.

How to design switches (and routers) that provide quality of service (QoS) guarantees, such as low transit (through the switch) delay for packets, has been a long-standing research problem. Output-queued (OQ) switch architecture is perfect for minimizing this transit delay, but is prohibitively expensive to implement "as is" in hardware. In theory, combined input- and output-queued (CIOQ) switch architecture can fully emulate OQ while requiring only a 2× speedup on the crossbar. In practice, however, one last hurdle remains for CIOQ to be practically implementable despite more than a decade of research: This emulation requires using stable marriages (matchings) as crossbar schedules, and each stable marriage takes Ω(N2) parallel iterations (N is the number of input/output ports) to compute in the worst case. The contribution of this work is SW-EDF, a novel parallel iterative switching algorithm (PISA) that overcomes this last hurdle: SW-EDF can compute, in a single low-complexity iteration, an "approximate stable marriage" that allows for near-perfect OQ emulation, in terms of tardy (compared to OQ) rates and distribution of tardiness.

Error estimating coding (EEC) is a standard technique for estimating the number of bit errors during packet transmission over wireless networks. In this paper, we propose OddEEC, a novel EEC scheme. OddEEC is a nontrivial adaptation of a data sketching technique named Odd Sketch to EEC, addressing new challenges therein by its bit sampling technique and maximum likelihood estimator. Our experiments show that OddEEC overall achieves comparable estimation accuracy as competing schemes such as gEEC and mEEC, with much smaller decoding complexity.

Set reconciliation (SetR) is an important research problem that has been studied for over two decades. In this problem, two large sets A and B of objects (tokens, files, records, etc.) are stored respectively at two different network-connected hosts, which we name Alice and Bob respectively. Alice and Bob need to communicate with each other to learn the set union A ∪ B (which then becomes their reconciled state), at low communication and computation costs. In this work, we study a different problem intricately related to SetR: Alice and Bob collaboratively compute A ∩ B . We call this problem SetX (set intersection). Although SetX is just as important as SetR, it has never been properly studied in its own right. Rather, there is an unspoken perception by the research community that SetR and SetX are equally difficult (in costs), and hence “roughly equivalent.” Our first contribution is to show that SetX is fundamentally a much “cheaper” problem than SetR, debunking this long-standing perception. Our second contribution is to develop a novel SetX solution, the communication cost of which handily beats the information-theoretic lower bound of SetR. This protocol is based on the idea of compressed sensing (CS), which we describe here only for the special case of A ⊆ B (We do have a more sophisticated protocol for the general case). Our protocol is for Alice to encode A into a CS sketch M 1 A and send it to Bob, where M is a CS matrix with l rows and 1 A is the binary vector representation of A . Our key innovation here is to make l (the sketch size) just large enough (for the sketch) to summarize B ∖ A (what Alice misses). In contrast, in existing protocols l needs to be large enough to summarize A (what Alice knows), which is typically much larger in cardinality. Our third contribution is to design a CS matrix M that is both “friendly” to (the performance of) applications and “compliant” with CS theory.

Locality sensitive hashing (LSH) is a widely used technique for approximate nearest neighbor search (ANNS). In an LSH-based solution for ANNS, the computation of query-to-data (Q2D) distances accounts for a considerable fraction of the query time, but such distance information is thrown away after nearest neighbors are identified. In this paper, we propose CanDE (Candidate-based Distribution Estimation), a lightweight add-on to LSH that reuses such information for a wide range of analytics tasks including Q2D distance distribution estimation (QDDE), kernel density estimation (KDE), and query-time recall estimation (QTRE). This allows for significant savings in indexing costs and query time for multiple tasks associated with the original query.The main technical hurdle that CanDE addresses is the accurate estimation of some important statistics of the dataset via importance sampling. We discover that the existing estimators of these statistics are not accurate, because they approximate the actual number of collisions (called collision rate) in the LSH index using the theoretical collision probability (of the LSH function family), and this approximation is crude. To address this issue, we propose more accurate estimators based on a novel scheme called inferred collision rate (ICR), which gives a much better approximation to the actual collision rate. Furthermore, we propose an efficient algorithm for computing ICR from the nearest neighbor candidates returned by ANNS. Our evaluation shows that CanDE outperforms existing solutions on multiple analytics tasks while adding only about 8% to 19% query time overhead to ANNS.

Point-to-subspace approximate nearest neighbor search in Lpmetric (Lp-P2S-ANNS) is a challenging research problem: Its only existing solution, called LDL1, is barely faster than the naïve linear scan, because its pruning (for promising ANNS candidates) metric is P2S distance in Lp, whose computation involves linear or convex programming that is computationally intensive. In this paper, we propose a novel scheme whose pruning metric is P2S distance in L2instead, which is computationally cheaper by four orders of magnitude, yet is almost as effective for pruning as LDL1’s empirically. We also propose a new framework named LSH pruning, which subsumes and improves all existing dimension reduction schemes, and propose a performance model well-grounded in statistics theory. Our experiments show that these contributions in combination reduce the query time by a factor of 4.8 to 54.

d-dimensional (for d > 1) efficient range-summability (dD-ERS) of random variables (RVs) is a fundamental algorithmic problem that has applications to two important families of database problems, namely, fast approximate wavelet tracking (FAWT) on data streams and approximately answering range-sum queries over a data cube. Whether there are efficient solutions to the dD-ERS problem, or to the latter database problem, have been two long-standing open problems. Both are solved in this work. Specifically, we propose a novel solution framework to dD-ERS on RVs that have Gaussian or Poisson distribution. Our dD-ERS solutions are the first ones that have polylogarithmic time complexities. Furthermore, we develop a novel k-wise independence theory that allows our dD-ERS solutions to have both high computational efficiencies and strong provable independence guarantees. Finally, we show that under a sufficient and likely necessary condition, certain existing solutions for 1D-ERS can be generalized to higher dimensions.

LT (Luby transform) codes are a celebrated family of rateless erasure codes (RECs). Most of existing LT codes were designed for applications in which a centralized encoder possesses all message blocks and is solely responsible for encoding them into codewords. Distributed LT codes, in which message blocks are physically scattered across multiple different locations (encoders) that need to collaboratively perform the encoding, has never been systemically studied before despite its growing importance in applications. In this work, we present the first systemic study of LT codes in the distributed setting, and make the following three major contributions. First, we show that only a proper subset of LT codes are feasible in the distributed setting, and give the sufficient and necessary condition for such feasibility. Second, we propose a distributed encoding protocol that can efficiently implement any feasible code. The protocol is parameterized by a so-called action probability array (APA) that is only a few KBs in size, and any feasible code corresponds to a valid APA setting and vice versa. Third, we propose two heuristic search algorithms that have led to the discovery of feasible codes that are much more efficient than the state of the art.

Efficient range-summability (ERS) of a long list of random variables is a fundamental algorithmic problem that has applications to three important database applications, namely, data stream processing, space-efficient histogram maintenance (SEHM), and approximate nearest neighbor searches (ANNS). In this work, we propose a novel dyadic simulation framework and develop three novel ERS solutions, namely Gaussian-dyadic simulation tree (DST), Cauchy-DST and Random Walk-DST, using it. We also propose novel rejection sampling techniques to make these solutions computationally efficient. Furthermore, we develop a novel k-wise independence theory that allows our ERS solutions to have both high computational efficiencies and strong provable independence guarantees.

In this work, we formulate and solve a new type of approximate nearest neighbor search (ANNS) problems called ANNS after linear transformation (ALT). In ANNS-ALT, we search for the vector (in a dataset) that, after being linearly transformed by a user-specified query matrix, is closest to a query vector. It is a very general mother problem in the sense that a wide range of baby ANNS problems that have important applications in databases and machine learning can be reduced to and solved as ANNS-ALT, or its dual that we call ANNS-ALTD. We propose a novel and computationally efficient solution, called ONe Index for All Kernels (ONIAK), to ANNS-ALT and all its baby problems when the data dimension d is not too large (say d ≤ 200). In ONIAK, a universal index is built, once and for all, for answering all future ANNS-ALT queries that can have distinct query matrices. We show by experiments that, when d is not too large, ONIAK has better query performance than linear scan on the mother problem (of ANNS-ALT), and has query performances comparable to those of the state-of-the-art solutions on the baby problems. However, the algorithmic technique behind this universal index approach suffers from a so-called dimension blowup problem that can make the indexing time prohibitively long for a large dataset. We propose a novel algorithmic technique, called fast GOE quadratic form (FGoeQF), that completely solves the (prohibitively long indexing time) fallout of the dimension blowup problem. We also propose a Johnson-Lindenstrauss transform (JLT) based ANNS-ALT (and ANNS-ALTD) solution that significantly outperforms any competitor when d is large.

Approximate Nearest Neighbor Search (ANNS) is a fundamental algorithmic problem, with numerous applications in many areas of computer science. Locality-Sensitive Hashing (LSH) is one of the most popular solution approaches for ANNS. A common shortcoming of many LSH schemes is that since they probe only a single bucket in a hash table, they need to use a large number of hash tables to achieve a high query accuracy. For ANNS- L 2 , a multi-probe scheme was proposed to overcome this drawback by strategically probing multiple buckets in a hash table. In this work, we propose MP-RW-LSH, the first and so far only multi-probe LSH solution to ANNS in L 1 distance, and show that it achieves a better tradeoff between scalability and query efficiency than all existing LSH-based solutions. We also explain why a state-of-the-art ANNS -L 1 solution called Cauchy projection LSH (CP-LSH) is fundamentally not suitable for multi-probe extension. Finally, as a use case, we construct, using MP-RW-LSH as the underlying "ANNS- L 1 engine", a new ANNS-E (E for edit distance) solution that beats the state of the art.

Influence Maximization (IM) aims to maximize the number of people that become aware of a product by finding the “best” set of “seed” users to initiate the product advertisement. Unlike most prior arts on the static networks containing fixed number of users, we study the evolving IM in more realistic evolving networks with temporally growing topology. The task of evolving IM, however, is far more challenging over static cases in the sense that the seed selection should consider its impact on future users who will join network during influence diffusion and the probabilities that users influence one another also evolve over time. We address the challenges brought by network evolution through EIM, a newly proposed bandit-based framework that alternates between seed nodes selection and knowledge (i.e., nodes’ growing speed and evolving activation probabilities) learning during network evolution. Remarkably, the EIM framework involves three novel components to handle the uncertainties brought by evolution: (1) A fully adaptive particle learning of nodes’ growing speed for accurately estimating future influenced size, with real growing behaviors delineated by a set of weighted particles. (2) A bandit-based refining method with growing arms to cope with the evolving activation probabilities via growing edges from previous influence diffusion feedbacks. (3) Evo-IMM , an evolving seed selection algorithm, which leverages the Influence Maximization via Martingale (IMM) framework, with the objective to maximize the influence spread to highly attractive users during evolution. Theoretically, the EIM framework returns a regret bound that provably maintains its sublinearity with respect to the growing network size. Empirically, the effectiveness of the EIM framework is also validated with three notable million-scale evolving network datasets possessing complete social relationships and nodes’ joining time. The results confirm the superiority of the EIM framework in terms of an up to 50% larger influenced size over four static baselines.