Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

ddimensional (for d > 1) efficient rangesummability (dDERS) 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 rangesum queries over a data cube. Whether there are efficient solutions to the dDERS problem, or to the latter database problem, have been two longstanding open problems. Both are solved in this work. Specifically, we propose a novel solution framework to dDERS on RVs that have Gaussian or Poisson distribution. Our dDERS solutions are the first ones that have polylogarithmic time complexities. Furthermore, we develop a novel kwise independence theory that allows our dDERS 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 1DERS can be generalized to higher dimensions.more » « less

In this work, we formulate and solve a new type of approximate nearest neighbor search (ANNS) problems called ANNS after linear transformation (ALT). In ANNSALT, we search for the vector (in a dataset) that, after being linearly transformed by a userspecified 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 ANNSALT, or its dual that we call ANNSALTD. We propose a novel and computationally efficient solution, called ONe Index for All Kernels (ONIAK), to ANNSALT and all its baby problems when the data dimension 𝑑 is not too large (say 𝑑 ≤ 200). In ONIAK, a universal index is built, once and for all, for answering all future ANNSALT queries that can have distinct query matrices. We show by experiments that, when 𝑑 is not too large, ONIAK has better query performance than linear scan on the mother problem (of ANNSALT), and has query performances comparable to those of the stateoftheart solutions on the baby problems. However, the algorithmic technique behind this universal index approach suffers from a socalled 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 JohnsonLindenstrauss transform (JLT) based ANNS ALT (and ANNSALTD) solution that significantly outperforms any competitor when 𝑑 is large.more » « less

Dan Olteanu and Nils Vortmeier (Ed.)Efficient rangesummability (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, spaceefficient 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 Gaussiandyadic simulation tree (DST), CauchyDST and Random WalkDST, using it. We also propose novel rejection sampling techniques to make these solutions computationally efficient. Furthermore, we develop a novel kwise independence theory that allows our ERS solutions to have both high computational efficiencies and strong provable independence guarantees.more » « less

null (Ed.)In this work, we first propose a parallel batch switching algorithm called SmallBatch QueueProportional Sampling (SBQPS). Compared to other batch switching algorithms, SBQPS significantly reduces the batch size without sacrificing the throughput performance and hence has much lower delay when traffic load is light to moderate. It also achieves the lowest possible time complexity of O(1) per matching computation per port, via parallelization. We then propose another algorithm called SlidingWindow QPS (SWQPS). SWQPS retains and enhances all benefits of SBQPS, and reduces the batching delay to zero via a novel switching framework called slidingwindow switching. In addition, SWQPS computes matchings of much higher qualities, as measured by the resulting throughput and delay performances, than QPS1, the stateoftheart regular switching algorithm that builds upon the same underlying bipartite matching algorithm.more » « less

With the booming of online service systems, anomaly detection on multivariate time series, such as a combination of CPU utilization, average response time, and requests per second, is important for system reliability. Although a collection of learningbased approaches have been designed for this purpose, our empirical study shows that these approaches suffer from long initialization time for sufficient training data. In this paper, we introduce the Compressed Sensing technique to multivariate time series anomaly detection for rapid initialization. To build a jumpstarting anomaly detector, we propose an approach named JumpStarter. Based on domainspecific insights, we design a shapebased clustering algorithm as well as an outlierresistant sampling algorithm for JumpStarter.With realworld multivariate time series datasets collected from two Internet companies, our results show that JumpStarter achieves an average F1 score of 94.12%, significantly outperforming the stateoftheart anomaly detection algorithms, with a much shorter initialization time of twenty minutes. We have applied JumpStarter in online service systems and gained useful lessons in realworld scenarios.more » « less

null (Ed.)Set reconciliation is a fundamental algorithmic problem that arises in many networking, system, and database applications. In this problem, two large sets A and B of objects (bitcoins, files, records, etc.) are stored respectively at two different networkconnected hosts, which we name Alice and Bob respectively. Alice and Bob communicate with each other to learn A Δ B , the difference between A and B , and as a result the reconciled set A ∪ B. Current set reconciliation schemes are based on either invertible Bloom filters (IBF) or errorcorrection codes (ECC). The former has a low computational complexity of O(d) , where d is the cardinality of A Δ B , but has a high communication overhead that is several times larger than the theoretical minimum. The latter has a low communication overhead close to the theoretical minimum, but has a much higher computational complexity of O(d 2 ). In this work, we propose Parity Bitmap Sketch (PBS), an ECCbased set reconciliation scheme that gets the better of both worlds: PBS has both a low computational complexity of O(d) just like IBFbased solutions and a low communication overhead of roughly twice the theoretical minimum. A separate contribution of this work is a novel rigorous analytical framework that can be used for the precise calculation of various performance metrics and for the nearoptimal parameter tuning of PBS.more » « less

In an inputqueued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed for each switching cycle, or time slot. It is a challenging research problem to design switching algorithms that produce highquality matchings yet have a very low computational complexity when the switch has a large number of ports. Indeed, there appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the quality of the computed matchings. Parallel maximal matching algorithms (adapted for switching) appear to be a sweet tradeoff point in this regard. On one hand, they provide the following performance guarantees: Using maxi mal matchings as crossbar schedules results in at least 50% switch throughput and orderoptimal (i.e., independent of the switch size 𝑁 ) average delay bounds for various traffic arrival processes. On the other hand, their computational complexities can be as low as 𝑂 (log_2 𝑁) per port/processor, which is much lower than those of the algorithms for finding matchings of higher qualities such as maximum weighted matching. In this work, we propose QPSr, a parallel iterative switching algorithm that has the lowest possible computational complexity: 𝑂(1) per port. Yet, the matchings that QPSr computes have the same quality as maximal matchings in the following sense: Using such matchings as crossbar schedules results in exactly the same aforementioned provable throughput and delay guarantees as using maximal matchings, as we show using Lyapunov stability analysis. Although QPSr builds upon an existing addon technique called QueueProportional Sampling (QPS), we are the first to discover and prove this nice property of such matchings. We also demon strate that QPS3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running log 𝑁 itera 2 tions), a refined and optimized representative maximal matching algorithm adapted for switching.more » « less

In an inputqueued switch, a crossbar schedule, or a matching between the input ports and the output ports needs to be computed for each switching cycle, or time slot. It is a challenging research problem to design switching algorithms that produce highquality matchings yet have a very low computational complexity when the switch has a large number of ports. Indeed, there appears to be a fundamental tradeoff between the computational complexity of the switching algorithm and the quality of the computed matchings. Parallel maximal matching algorithms (adapted for switching) appear to be a sweet tradeoff point in this regard. On one hand, they provide the following performance guarantees: Using maxi mal matchings as crossbar schedules results in at least 50% switch throughput and orderoptimal (i.e., independent of the switch size 𝑁 ) average delay bounds for various traffic arrival processes. On the other hand, their computational complexities can be as low as 𝑂 (log2 𝑁 ) per port/processor, which is much lower than those of the algorithms for finding matchings of higher qualities such as maximum weighted matching. In this work, we propose QPSr, a parallel iterative switching algorithm that has the lowest possible computational complexity: 𝑂(1) per port. Yet, the matchings that QPSr computes have the same quality as maximal matchings in the following sense: Using such matchings as crossbar schedules results in exactly the same aforementioned provable throughput and delay guarantees as using maximal matchings, as we show using Lyapunov stability analysis. Although QPSr builds upon an existing addon technique called QueueProportional Sampling (QPS), we are the first to discover and prove this nice property of such matchings. We also demon strate that QPS3 (running 3 iterations) has comparable empirical throughput and delay performances as iSLIP (running log 𝑁 itera 2 tions), a refined and optimized representative maximal matching algorithm adapted for switching.more » « less