Document Open Access Logo

Approximate Range Queries for Clustering

Authors Eunjin Oh, Hee-Kap Ahn

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.62.pdf
  • Filesize: 461 kB
  • 14 pages

Document Identifiers

Author Details

Eunjin Oh
Hee-Kap Ahn

Cite As Get BibTex

Eunjin Oh and Hee-Kap Ahn. Approximate Range Queries for Clustering. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.62

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+epsilon)-approximations to the optimal clusterings of P cap Q efficiently for a query consisting of an orthogonal range Q, an integer k, and a value epsilon>0.

Subject Classification

Keywords
  • Approximate clustering
  • orthogonal range queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D. Mehrabi. Range-Clustering Queries. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG 2017), volume 77, pages 5:1-5:16, 2017. Google Scholar
  2. Pankaj K. Agarwal and Jeff Erickson. Geometric range searching and its relatives. In Advances in Discrete and Compputational Geometry, volume 223 of Contemporary Mathematics, pages 1-56. American Mathematical Society Press, 1999. Google Scholar
  3. Pankaj K. Agarwal, Sariel Har-Peled, and Kasturi R. Varadarajan. Geometric approximation via coresets. In Combinatorial and Computational Geometry, volume 52, pages 1-30. MSRI Publications, 2005. Google Scholar
  4. Pankaj. K. Agarwal and Cecillia M. Procopiuc. Exact and approximation algorithms for clustering. Algorithmica, 33(2):201-226, 2002. Google Scholar
  5. Srinivas Aluru. Quadtrees and octrees. In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, chapter 19. Chapman & Hall/CRC, 2005. Google Scholar
  6. Sunil Arya, David M. Mount, and Eunhui Park. Approximate geometric MST range queries. In Proceedings of the 31st International Symposium on Computational Geometry (SoCG 2015), pages 781-795, 2015. Google Scholar
  7. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. Local search heuristics for k-median and facility location problems. SIAM Journal on Computing, 33(3):544-562, 2004. Google Scholar
  8. Peter Brass, Christian Knauer, Chan-Su Shin, Michiel Smid, and Ivo Vigan. Range-aggregate queries for geometric extent problems. In Proceedings of the 19th Computing: The Australasian Theory Symposium (CATS 2013), volume 141, pages 3-10, 2013. Google Scholar
  9. Ke Chen. On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. SIAM Journal on Computing, 39(3):923-947, 2009. Google Scholar
  10. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, 2008. Google Scholar
  11. James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989. Google Scholar
  12. Tomás Feder and Daniel Greene. Optimal algorithms for approximate clustering. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988), pages 434-444, 1988. Google Scholar
  13. Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the 43th Annual ACM Symposium on Theory of Computing (STOC 2011), pages 569-578, 2011. Google Scholar
  14. Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38(Supplement C):293-306, 1985. Google Scholar
  15. Prosenjit Gupta, Ravi Janardan, Yokesh Kumar, and Michiel Smid. Data structures for range-aggregate extent queries. Computational Geometry, 47(2, Part C):329-347, 2014. Google Scholar
  16. Sariel Har-Peled. Geometric Approximation Algorithms. Mathematical surveys and monographs. American Mathematical Society, 2011. Google Scholar
  17. Sariel Har-Peled and Akash Kushal. Smaller coresets for k-median and k-means clustering. Discrete & Computational Geometry, 37(1):3-19, Jan 2007. Google Scholar
  18. Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pages 291-300, 2004. Google Scholar
  19. Anil Kumar Jain, M. Narasimha Murty, and Patrick J. Flynn. Data clustering: A review. ACM Computing Surveys, 31(3):264-323, 1999. Google Scholar
  20. Jiří Matoušek. Geometric range searching. ACM Computing Surveys, 26(4):422-461, 1994. Google Scholar
  21. Kurt Mehlhorn and Stefan Näher. Dynamic fractional cascading. Algorithmica, 5(1):215-241, 1990. Google Scholar
  22. Yakov Nekrich and Michiel H. M. Smid. Approximating range-aggregate queries using coresets. In Proceedings of the 22nd Annual Canadian Conference on Computational Geometry (CCCG 2010), pages 253-256, 2010. Google Scholar
  23. Dimitris Papadias, Yufei Tao, Kyriakos Mouratidis, and Chun Kit Hui. Aggregate nearest neighbor queries in spatial databases. ACM Transactions on Database System, 30(2):529-576, 2005. Google Scholar
  24. Jing Shan, Donghui Zhang, and Betty Salzberg. On spatial-range closest-pair query. In Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases (SSTD 2003), pages 252-269, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact