Ioannis Psarros

ICML Conference 2025 Conference Paper

Faster Approximation Algorithms for k-Center via Data Reduction

• Arnold Filtser
• Shaofeng H. -C. Jiang
• Yi Li 0002
• Anurag Murty Naredla
• Ioannis Psarros
• Qiaoyuan Yang
• Qin Zhang 0001

We study efficient algorithms for the Euclidean $k$-Center problem, focusing on the regime of large $k$. We take the approach of data reduction by considering $\alpha$-coreset, which is a small subset $S$ of the dataset $P$ such that any $\beta$-approximation on $S$ is an $(\alpha + \beta)$-approximation on $P$. We give efficient algorithms to construct coresets whose size is $k \cdot o(n)$, which immediately speeds up existing approximation algorithms. Notably, we obtain a near-linear time $O(1)$-approximation when $k = n^c$ for any $0 < c < 1$. We validate the performance of our coresets on real-world datasets with large $k$, and we observe that the coreset speeds up the well-known Gonzalez algorithm by up to $4$ times, while still achieving similar clustering cost. Technically, one of our coreset results is based on a new efficient construction of consistent hashing with competitive parameters. This general tool may be of independent interest for algorithm design in high dimensional Euclidean spaces.

TCS Journal 2023 Journal Article

Near-neighbor preserving dimension reduction via coverings for doubling subsets of ℓ1

• Ioannis Z. Emiris
• Vasilis Margonis
• Ioannis Psarros

Randomized dimensionality reduction has been recognized as one of the cornerstones in handling high-dimensional data, originating in various foundational works such as the celebrated Johnson-Lindenstrauss Lemma. More specifically, nearest neighbor-preserving embeddings exist for ℓ 2 (Euclidean) and ℓ 1 (Manhattan) metrics, as well as doubling subsets of ℓ 2, where doubling dimension is today the most effective way of capturing intrinsic dimensionality, as well as input structure in various applications. These randomized embeddings bound the distortion only for distances between the query point and a point set. Motivated by the foundational character of fast Approximate Nearest Neighbor search in ℓ 1, this paper settles an important missing case, namely that of doubling subsets of ℓ 1. In particular, we introduce a randomized dimensionality reduction by means of a near neighbor-preserving embedding, which is related to the decision-with-witness problem. The input set gets represented with a carefully chosen covering point set; in a second step, the algorithm randomly projects the latter. In order to obtain the covering point sets, we leverage either approximate r-nets or randomly shifted grids, with different tradeoffs between preprocessing time and target dimension. We exploit Cauchy random variables, and derive a concentration bound of independent interest. Our algorithms are rather simple and should therefore be useful in practice.

SODA Conference 2022 Conference Paper

Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance

• Karl Bringmann
• Anne Driemel
• André Nusser
• Ioannis Psarros

We study the c -approximate near neighbor problem under the continuous Fréchet distance: Given a set of n polygonal curves with m vertices, a radius δ > 0, and a parameter k ≤ m, we want to preprocess the curves into a data structure that, given a query curve q with k vertices, either returns an input curve with Fréchet distance at most c · δ to q, or returns that there exists no input curve with Fréchet distance at most δ to q. We focus on the case where the input and the queries are one-dimensional polygonal curves—also called time series—and we give a comprehensive analysis for this case. We obtain new upper bounds that provide different tradeoffs between approximation factor, preprocessing time, and query time. Our data structures improve upon the state of the art in several ways. We show that for any 0 < ∊ ≤ 1 an approximation factor of (1 + ∊ ) can be achieved within the same asymptotic time bounds as the previously best result for (2 + ∊ ). Moreover, we show that an approximation factor of (2 + ∊ ) can be obtained by using preprocessing time and space O(nm ), which is linear in the input size, and query time in, where the previously best result used preprocessing time in and query time in O (1) k. We complement our upper bounds with matching conditional lower bounds based on the Orthogonal Vectors Hypothesis. Interestingly, some of our lower bounds already hold for any super-constant value of k. This is achieved by proving hardness of a one-sided sparse version of the Orthogonal Vectors problem as an intermediate problem, which we believe to be of independent interest.

SODA Conference 2017 Conference Paper

High-dimensional approximate r -nets

• Georgia Avarikioti
• Ioannis Z. Emiris
• Loukas Kavouras
• Ioannis Psarros