Huang, Ziyun ;
Xu, Jinhui
An Efficient Sum Query Algorithm for Distancebased Locally Dominating Functions
Abstract
In this paper, we consider the following sum query problem:
Given a point set P in R^d, and a distancebased 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 coreset 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 Distancebased Locally Dominating Functions}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {47:147:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8248},
URN = {urn:nbn:de:0030drops82483},
doi = {10.4230/LIPIcs.ISAAC.2017.47},
annote = {Keywords: Sum Query, Distancebased Function, Local Domination, High Dimen sions, Data Structure}
}
07.12.2017
Keywords: 

Sum Query, Distancebased Function, Local Domination, High Dimen sions, Data Structure 
Seminar: 

28th International Symposium on Algorithms and Computation (ISAAC 2017)

Issue date: 

2017 
Date of publication: 

07.12.2017 