![Loading...](https://link.springer.com/static/c4a417b97a76cc2980e3c25e2271af3129e08bbe/images/pdf-preview/spacer.gif)
-
Chapter and Conference Paper
Nearly Optimal Private Convolution
We study algorithms for computing the convolution of a private input x with a public input h, while satisfying the guarantees of (ε, δ)-differential privacy. Convolution is a fundamental operation, intimately rel...
-
Chapter and Conference Paper
Forty Years of Text Indexing
This paper reviews the first 40 years in the life of textual inverted indexes, their many incarnations, and their applications. The paper is non-technical and assumes some familiarity with the structures and c...
-
Chapter
Frugal Streaming for Estimating Quantiles
Modern applications require processing streams of data for estimating statistical quantities such as quantiles with small amount of memory. In many such applications, in fact, one needs to compute such statist...
-
Chapter and Conference Paper
Range Medians
We study a generalization of the classical median finding problem to batched query case: given an array of unsorted n items and k (not necessarily disjoint) intervals in the array, the goal is to determine the me...
-
Chapter and Conference Paper
Internet Ad Auctions: Insights and Directions
On the Internet, there are advertisements (ads) of different kinds: image, text, video and other specially marked objects that are distinct from the underlying content of the page. There is an industry behind ...
-
Chapter and Conference Paper
In-Place Suffix Sorting
Given string T = T[1,...,n], the suffix sorting problem is to lexicographically sort the suffixes T[i,...,n] for all i. This problem is central to the construction of suffix arrays and trees with many application...
-
Chapter and Conference Paper
Radix Sorting with No Extra Space
It is well known that n integers in the range [1,n c ] can be sorted in O(n) time in the RAM model using radix sorting. More generally, integers in any range [1,
-
Chapter and Conference Paper
Bidding to the Top: VCG and Equilibria of Position-Based Auctions
Many popular search engines run an auction to determine the placement of advertisements next to search results. Current auctions at Google and Yahoo! let advertisers specify a single amount as their bid in the...
-
Chapter and Conference Paper
Subspace Sampling and Relative-Error Matrix Approximation: Column-Row-Based Methods
Much recent work in the theoretical computer science, linear algebra, and machine learning has considered matrix decompositions of the following form: given an m ×n matrix A, decompose it as a product of three ma...
-
Chapter and Conference Paper
Subspace Sampling and Relative-Error Matrix Approximation: Column-Based Methods
Given an m ×n matrix A and an integer k less than the rank of A, the “best” rank k approximation to A that minimizes the error with respect to the Frobenius norm is A k ...
-
Chapter and Conference Paper
Workload-Optimal Histograms on Streams
A histogram is a piecewise-constant approximation of an observed data distribution. A histogram is used as a small-space, approximate synopsis of the underlying data distribution, which is often too large to b...
-
Chapter and Conference Paper
Sublinear Methods for Detecting Periodic Trends in Data Streams
We present sublinear algorithms — algorithms that use significantly less resources than needed to store or process the entire input stream – for discovering representative trends in data streams in the form of...
-
Chapter and Conference Paper
An Improved Data Stream Summary: The Count-Min Sketch and Its Applications
We introduce a new sublinear space data structure—the Count-Min Sketch— for summarizing data streams. Our sketch allows fundamental queries in data stream summarization such as point, range, and inner product que...
-
Chapter and Conference Paper
Estimating Rarity and Similarity over Data Stream Windows
In the windowed data stream model, we observe items coming in over time. At any time t, we consider the window of the last N observations a t-(N-1), a t-(N-2), . . ...
-
Chapter and Conference Paper
Range Searching in Categorical Data: Colored Range Searching on Grid
Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and spatial databases. Given a set of geometric objects, a typical range query asks for ...
-
Chapter and Conference Paper
Engineering diffusive load balancing algorithms using experiments
We study a distributed load balancing problem on arbitrary graphs. First Order (FO) and Second Order (SO) schemes are popular local diffusive schedules for this problem. To use them, several parameters have to be...