Document Open Access Logo

An Efficient Sum Query Algorithm for Distance-based Locally Dominating Functions

Authors Ziyun Huang, Jinhui Xu

PDF

File

Thumbnail PDF
PDF
LIPIcs.ISAAC.2017.47.pdf
  • Filesize: 0.88 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • Sum Query
  • Distance-based Function
  • Local Domination
  • High Dimen- sions
  • Data Structure

Metrics

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

Abstract

In this paper, we consider the following sum query problem:
Given a point set P in R^d, and a distance-based function f(p,q) (i.e. a function of the distance between p and q) satisfying some general properties,
the goal is to develop a data structure and a query algorithm for efficiently computing a (1+epsilon)-approximate solution to the sum 
sum_{p in P} f(p,q)  for any query point q in R^d and any small constant epsilon>0. Existing techniques for this problem are mainly based on some core-set techniques which often have difficulties to deal with functions with local domination property. Based on several new insights to this problem, we develop in this paper a novel technique to overcome these encountered difficulties.  Our algorithm is capable of answering queries with high success probability in time no more than ~O_{epsilon,d}(n^{0.5 + c}), and the underlying 
data structure can be constructed in  ~O_{epsilon,d}(n^{1+c}) time for any c>0, where the hidden constant has only polynomial dependence on 1/epsilon and d.
Our technique is simple and can be easily implemented for practical purpose.

Cite As Get BibTex

Ziyun Huang and Jinhui Xu. An Efficient Sum Query Algorithm for Distance-based Locally Dominating Functions. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 47:1-47:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ISAAC.2017.47

Author Details

Ziyun Huang
Jinhui Xu

References

  1. Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 180-186. SIAM, 2009. Google Scholar
  2. Pankaj K. Agarwal, Sariel Har-peled, and Kasturi R. Varadarajan. Geometric approximation via coresets. In Combinatorial and Computational Geometry, MSRI, pages 1-30. University Press, 2005. Google Scholar
  3. Alexandr Andoni, Piotr Indyk, Huy L Nguy~ên, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1018-1028. SIAM, 2014. Google Scholar
  4. Boris Aronov and Sariel Har-Peled. On approximating the depth and related problems. SIAM Journal on Computing, 38(3):899-921, 2008. Google Scholar
  5. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. Google Scholar
  6. D. Z. Chen, Z. Huang, Y. Liu, and J. Xu. On clustering induced voronoi diagrams. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 390-399, 2013. Google Scholar
  7. 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
  8. Dan Feldman and Michael Langberg. A unified framework for approximating and clustering data. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569-578. ACM, 2011. Google Scholar
  9. Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of computing, 8(1):321-350, 2012. Google Scholar
  10. Sariel Har-Peled and Soham Mazumdar. On coresets for k-means and k-median clustering. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 291-300. ACM, 2004. Google Scholar
  11. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963. Google Scholar
  12. Saladi Rahul and Yufei Tao. Efficient top-k indexing via general reductions. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 277-288. ACM, 2016. Google Scholar
  13. Cheng Sheng and Yufei Tao. Dynamic top-k range reporting in external memory. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on Principles of Database Systems, pages 121-130. ACM, 2012. 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact