License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2017.47
URN: urn:nbn:de:0030-drops-82483
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8248/
Go to the corresponding LIPIcs Volume Portal

Huang, Ziyun ; Xu, Jinhui

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

pdf-format:
LIPIcs-ISAAC-2017-47.pdf (0.9 MB)

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.

BibTeX - Entry

@InProceedings{huang_et_al:LIPIcs:2017:8248,
  author =	{Ziyun Huang and Jinhui Xu},
  title =	{{An Efficient Sum Query Algorithm for Distance-based Locally Dominating Functions}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{47:1--47:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8248},
  URN =		{urn:nbn:de:0030-drops-82483},
  doi =		{10.4230/LIPIcs.ISAAC.2017.47},
  annote =	{Keywords: Sum Query, Distance-based Function, Local Domination, High Dimen- sions, Data Structure}
}

Keywords: Sum Query, Distance-based Function, Local Domination, High Dimen- sions, Data Structure
Collection: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 07.12.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI