Approximate Range Queries for Clustering

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

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

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clustering to minimize the maximum intercluster distance
• Exact and approximation algorithms for clustering
• Making data structures persistent
• Dynamic fractional cascading
• 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
• A unified framework for approximating and clustering data
• Range-clustering queries
• Approximate geometric MST range queries

Cited In (3)

• STACS 2005
• Approximate Clustering with Same-Cluster Queries
• 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)