Approximate range queries for clustering

DOI10.4230/LIPICS.SOCG.2018.62MaRDI QIDQ5116522zbMATH OpenOpenAlexFDO

Authors Eunjin Oh, Hee-Kap Ahn

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1803.03978

zbMATH Keywords

orthogonal range queriesapproximate clustering

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Abstract: We study the approximate range searching for three variants of the clustering problem with a set $P$ of $n$ points in $d$-dimensional Euclidean space and axis-parallel rectangular range queries: the $k$-median, $k$-means, and $k$-center range-clustering query problems. We present data structures and query algorithms that compute $(1+varepsilon)$-approximations to the optimal clusterings of $PcapQ$ efficiently for a query consisting of an orthogonal range $Q$, an integer $k$, and a value $varepsilon>0$.

Recommendations

• Range-clustering queries
• Approximate range searching
• Approximate nearest neighbor queries revisited
• Approximate range searching in higher dimension
• Efficient approximation algorithms for clustering point-sets

Cites work

• scientific article; zbMATH DE number 1241835 (Why is no real title available?)
• scientific article; zbMATH DE number 6876076 (Why is no real title available?)
• scientific article; zbMATH DE number 5019895 (Why is no real title available?)
• A unified framework for approximating and clustering data
• Approximate geometric MST range queries
• Clustering to minimize the maximum intercluster distance
• Computational geometry. Algorithms and applications.
• Data structures for range-aggregate extent queries
• Dynamic fractional cascading
• Exact and approximation algorithms for clustering
• Geometric approximation algorithms
• Local Search Heuristics for k-Median and Facility Location Problems
• Making data structures persistent
• On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
• On coresets for k-means and k-median clustering
• Range-clustering queries
• Smaller coresets for \(k\)-median and \(k\)-means clustering

Cited in

(9)

• Range-clustering queries
• Range search on tuples of points
• Preclustering Algorithms for Imprecise Points
• STACS 2005
• Space exploration via proximity search
• Approximate correlation clustering using same-cluster queries
• Balanced compact clustering for efficient range queries in metric spaces
• Space exploration via proximity search
• Approximate Clustering with Same-Cluster Queries

This page was built for publication: Approximate range queries for clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5116522)