11 citations · 15 across the 5 of their papers we have counts for
9 papers
Streaming Algorithms with Few State Changes
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typi…
Efficient Centroid-Linkage Clustering
MohammadHossein Bateni, Laxman Dhulipala, Willem Fletcher +4
We give an efficient algorithm for Centroid-Linkage Hierarchical Agglomerative Clustering (HAC), which computes a -approximate clustering in roughly time. We ob…
Data-Dependent LSH for the Earth Mover's Distance
Rajesh Jayaram, Erik Waingarten, Tian Zhang
We give new data-dependent locality sensitive hashing schemes (LSH) for the Earth Mover's Distance (), and as a result, improve the best approximation for nearest nei…
Unleashing Graph Partitioning for Large-Scale Nearest Neighbor Search
Lars Gottesbüren, Laxman Dhulipala, Rajesh Jayaram +1
We consider the fundamental problem of decomposing a large-scale approximate nearest neighbor search (ANNS) problem into smaller sub-problems. The goal is to partition the input po…
Metric Clustering and MST with Strong and Weak Distance Oracles
MohammadHossein Bateni, Prathamesh Dharangutte, Rajesh Jayaram +1
We study optimization problems in a metric space where we can compute distances in two ways: via a ''strong'' oracle that returns exact distances , and a…
Massively Parallel Algorithms for High-Dimensional Euclidean Minimum Spanning Tree
Rajesh Jayaram, Vahab Mirrokni, Shyam Narayanan +1
We study the classic Euclidean Minimum Spanning Tree (MST) problem in the Massively Parallel Computation (MPC) model. Given a set of points, the goal i…