Source author record

Kevin Lang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Artificial Intelligence Computer Science and Game Theory

Catalog footprint

Research overview

3works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

A Framework for Estimating Stream Expression Cardinalities

Given $m$ distributed data streams $A_1, \dots, A_m$ , we consider the problem of estimating the number of unique identifiers in streams defined by set expressions over $A_1, \dots, A_m$ . We identify a broad class of algorithms for solving this problem, and show that the estimators output by any algorithm in this class are perfectly unbiased and satisfy strong variance bounds. Our analysis unifies and generalizes a variety of earlier results in the literature. To demonstrate its generality, we describe several novel sampling algorithms in our class, and show that they achieve a novel tradeoff between accuracy, space usage, update speed, and applicability.

preprint2016arXiv

Optimal Quantile Approximation in Streams

This paper resolves one of the longest standing basic problems in the streaming computational model. Namely, optimal construction of quantile sketches. An $\varepsilon$ approximate quantile sketch receives a stream of items $x_1,\ldots,x_n$ and allows one to approximate the rank of any query up to additive error $\varepsilon n$ with probability at least $1-δ$ . The rank of a query $x$ is the number of stream items such that $x_i \le x$ . The minimal sketch size required for this task is trivially at least $1/\varepsilon$ . Felber and Ostrovsky obtain a $O((1/\varepsilon)\log(1/\varepsilon))$ space sketch for a fixed $δ$ . To date, no better upper or lower bounds were known even for randomly permuted streams or for approximating a specific quantile, e.g.,\ the median. This paper obtains an $O((1/\varepsilon)\log \log (1/δ))$ space sketch and a matching lower bound. This resolves the open problem and proves a qualitative gap between randomized and deterministic quantile sketching. One of our contributions is a novel representation and modification of the widely used merge-and-reduce construction. This subtle modification allows for an analysis which is both tight and extremely simple. Similar techniques should be useful for improving other sketching objectives and geometric coreset constructions.

preprint2013arXiv

Bargaining for Revenue Shares on Tree Trading Networks

We study trade networks with a tree structure, where a seller with a single indivisible good is connected to buyers, each with some value for the good, via a unique path of intermediaries. Agents in the tree make multiplicative revenue share offers to their parent nodes, who choose the best offer and offer part of it to their parent, and so on; the winning path is determined by who finally makes the highest offer to the seller. In this paper, we investigate how these revenue shares might be set via a natural bargaining process between agents on the tree, specifically, egalitarian bargaining between endpoints of each edge in the tree. We investigate the fixed point of this system of bargaining equations and prove various desirable for this solution concept, including (i) existence, (ii) uniqueness, (iii) efficiency, (iv) membership in the core, (v) strict monotonicity, (vi) polynomial-time computability to any given accuracy. Finally, we present numerical evidence that asynchronous dynamics with randomly ordered updates always converges to the fixed point, indicating that the fixed point shares might arise from decentralized bargaining amongst agents on the trade network.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.