272 citations · 611 across the 76 of their papers we have counts for
7 papers · 1 filter
Sampling a Near Neighbor in High Dimensions -- Who is the Fairest of Them All?
Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi +2
Similarity search is a fundamental algorithmic primitive, widely used in many computer science disciplines. Given a set of points and a radius parameter , the -near nei…
Separators for Planar Graphs that are Almost Trees
Linda Cai, Sariel Har-Peled, Simiao Ye
We prove that a connected planar graph with vertices and edges has a vertex separator of size , and this separator can be computed in linear time.
Edge Estimation with Independent Set Oracles
Paul Beame, Sariel Har-Peled, Sivaramakrishnan Natarajan Ramamoorthy +2
We study the task of estimating the number of edges in a graph with access to only an independent set oracle. Independent set queries draw motivation from group testing and have ap…
Computing the k Nearest-Neighbors for all Vertices via Dijkstra
Sariel Har-Peled
We are given a directed graph with vertices and edges, with positive weights on the edges, and a parameter . We show how to compute, for every vertex $v \…
Faster Approximate Distance Queries and Compact Routing in Sparse Graphs
Rachit Agarwal, P. Brighten Godfrey, Sariel Har-Peled
A distance oracle is a compact representation of the shortest distance matrix of a graph. It can be queried to approximate shortest paths between any pair of vertices. Any distance…
Range Medians
Sariel Har-Peled, S. Muthukrishnan
We study a generalization of the classical median finding problem to batched query case: given an array of unsorted items and (not necessarily disjoint) intervals in the ar…
Fast Construction of Nets in Low Dimensional Metrics, and Their Applications
Sariel Har-Peled, Manor Mendel
We present a near linear time algorithm for constructing hierarchical nets in finite metric spaces with constant doubling dimension. This data-structure is then applied to obtain i…