Approximate range queries for clustering

DOI10.4230/LIPICS.SOCG.2018.62zbMATH Open1489.68369arXiv1803.03978OpenAlexW2963509702MaRDI QIDQ5116522FDOQ5116522

Authors: Eunjin Oh, Hee-Kap Ahn 

Publication date: 18 August 2020

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$.

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

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

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)

Cites Work

• Computational geometry. Algorithms and applications.
• Clustering to minimize the maximum intercluster distance
• Exact and approximation algorithms for clustering
• Making data structures persistent
• Title not available (Why is that?)
• Dynamic fractional cascading
• Geometric approximation algorithms
• Local Search Heuristics for k-Median and Facility Location Problems
• 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
• Data structures for range-aggregate extent queries
• Smaller coresets for \(k\)-median and \(k\)-means clustering
• Title not available (Why is that?)
• A unified framework for approximating and clustering data
• Range-clustering queries
• Approximate geometric MST range queries
• Title not available (Why is that?)

Cited In (9)

• Preclustering Algorithms for Imprecise Points
• STACS 2005
• Range search on tuples of points
• Space exploration via proximity search
• Space exploration via proximity search
• Approximate Clustering with Same-Cluster Queries
• Range-clustering queries
• Balanced compact clustering for efficient range queries in metric spaces
• Approximate correlation clustering using 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)