Advances in Clustering and Nearest Neighbor Search

The field of clustering and nearest neighbor search is experiencing significant advancements, driven by the development of novel algorithms and techniques. A key direction is the improvement of approximation factors and running times for various clustering problems, such as k-means and hierarchical clustering. Additionally, there is a growing interest in exploring non-traditional metric spaces, including probabilistic and elastic frameworks. These innovations have the potential to enable more efficient and effective clustering in complex datasets. Noteworthy papers include: Local Search for Clustering in Almost-linear Time, which proposes a local search algorithm for Euclidean clustering that achieves an O(c)-approximation in almost-linear time. Random Normed k-Means, which introduces a probabilistic perspective on clustering and establishes a rigorous theoretical framework for clustering in stochastic environments. ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search, which proposes novel methods for relaxing the strict requirement for subranges to exactly match the query range, leading to improved query efficiency. Coreset Strikes Back: Improved Parameterized Approximation Schemes for (Constrained) k-Median/Means, which presents a unified framework for obtaining EPASes for capacitated and fair k-Median/Means in metrics of bounded algorithmic scatter dimension.

Sources

Local Search for Clustering in Almost-linear Time

Random Normed k-Means: A Paradigm-Shift in Clustering within Probabilistic Metric Spaces

ESG: Elastic Graphs for Range-Filtering Approximate k-Nearest Neighbor Search

Geometric Bipartite Matching Based Exact Algorithms for Server Problems

Handling LP-Rounding for Hierarchical Clustering and Fitting Distances by Ultrametrics

Coreset Strikes Back: Improved Parameterized Approximation Schemes for (Constrained) k-Median/Means

Built with on top of