Princeton University, Princeton, NJ, USA
(MATH) A locality sensitive hashing scheme is a distribution on a family $\F$ of hash functions operating on a collection of objects, such that for two objects x,y, Prh&egr;F[h(x) = h(y)] = sim(x,y), where sim(x,y) &egr; [0,1] is some ...
Moses Charikar, Sudipto Guha, Éva Tardos, David B. Shmoys
We present the first constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the most well-studied clustering problems, i.e., those problems in which the aim is to partition a given set of points into ...
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
We define and study the notion of min-wise independent families of permutations. We say that F⊆Sn is min-wise independent if for any set X ⊆ [n] and any x ∈ X, when π is chosen at random in F we have Pr parenleftbig min{π(X)} = π(x) ...
Moses Charikar, Surajit Chaudhuri, Rajeev Motwani, Vivek R. Narasayya
Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2000 – PODS
We consider the problem of estimating the number of distinct values in a column of a table. For large tables without an index on the column, random sampling appears to be the only scalable approach for estimating the number of distinct values. We ...
Nir Ailon, Moses Charikar, Alantha Newman
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005 – STOC
We address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the number of disagreements with the respective inputs. Specifically, the problems ...
Andrei Z. Broder, Moses Charikar, Alan M. Frieze, Michael Mitzenmacher
Journal of Computer and System Sciences, vol. 60,no. 3,2000 – JCSS
We define and study the notion of min-wise independent families of permutations. We say
Moses Charikar, Chandra Chekuri, Tomás Feder, Rajeev Motwani
Motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. We propose a model-c~led incremental clustering which is based on a careful ...
Moses Charikar, Kevin Chen, Martin Farach-Colton
Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, vol. 2380,2002 – ICALP
Abstract. We present a 1-pass algorithm for estimating the most frequent items in a data stream using very limited storage space. Our method relies on a novel data structure called a count sketch, which allows us to estimate the frequencies of all ...
Moses Charikar, Liadan O'Callaghan, Rina Panigrahy
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003 – STOC
We study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. Our main result is a randomized algorithm for the k--Median ...
Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha
Most optimization problems on an undirected graph reduce in complexity when restricted to instances on a t.ree. A recent result [3] for probabiistically approsimating graph metrics by trees such that no edge &retches (in an expected sense) by ...