Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor

Author(s):

Arya, Sunil
Malamatos, Theocharis
Mount, David M.

dblp
dblp
dblp

Not MPG Author(s):

Arya, Sunil
Mount, David M.

Editor(s):





BibTeX cite key*:

AMM2006a

Title, Booktitle

Title*:

On the Importance of Idempotence

Booktitle*:

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC'06

Event, URLs

URL of the conference:


URL for downloading the paper:

http://delivery.acm.org/10.1145/1140000/1132598/p564-arya.pdf?key1=1132598&key2=3234908711&coll=&dl=&CFID=15151515&CFTOKEN=6184618

Event Address*:

Seattle, Washington, USA

Language:

English

Event Date*
(no longer used):


Organization:


Event Start Date:

21 May 2006

Event End Date:

23 May 2006

Publisher

Name*:

ACM

URL:


Address*:

New York, NY, USA

Type:


Vol, No, Year, pp.

Series:


Volume:


Number:


Month:


Pages:

564-573

Year*:

2006

VG Wort Pages:


ISBN/ISSN:

1-59593-134-1

Sequence Number:


DOI:




Note, Abstract, ©


(LaTeX) Abstract:

Range searching is among the most fundamental problems in computational geometry. An n-element point set in Rd is given along with an assignment of weights to these points from some commutative semigroup. Subject to a fixed space of possible range shapes, the problem is to preprocess the points so that the total semigroup sum of the points lying within a given query range η can be determined quickly. In the approximate version of the problem we assume that η is bounded, and we are given an approximation parameter ε > 0. We are to determine the semigroup sum of all the points contained within η and may additionally include any of the points lying within distance ε • diam(η) of η's boundar.In this paper we contrast the complexity of range searching based on semigroup properties. A semigroup (S,+) is idempotent if x + x = x for all x ∈ S, and it is integral if for all k ≥ 2, the k-fold sum x + ... + x is not equal to x. For example, (R, min) and (0,1, ∨) are both idempotent, and (N, +) is integral. To date, all upper and lower bounds hold irrespective of the semigroup. We show that semigroup properties do indeed make a difference for both exact and approximate range searching, and in the case of approximate range searching the differences are dramatic.First, we consider exact halfspace range searching. The assumption that the semigroup is integral allows us to improve the best lower bounds in the semigroup arithmetic model. For example, assuming O(n) storage in the plane and ignoring polylog factors, we provide an Ω*(n2/5) lower bound for integral semigroups, improving upon the best lower bound of Ω*(n1/3), thus closing the gap with the O(n1/2) upper bound.We also consider approximate range searching for Euclidean ball ranges. We present lower bounds and nearly matching upper bounds for idempotent semigroups. We also present lower bounds for range searching for integral semigroups, which nearly match existing upper bounds. These bounds show that the advantages afforded by idempotency can result in major improvements. In particular, assuming roughly linear space, the exponent in the ε-dependencies is smaller by a factor of nearly 1/2. All our results are presented in terms of space-time tradeoffs, and our lower and upper bounds match closely throughout the entire spectrum.To our knowledge, our results provide the first proof that semigroup properties affect the computational complexity of range searching in the semigroup arithmetic model. These are the first lower bound results for any approximate geometric retrieval problems. The existence of nearly matching upper bounds, throughout the range of space-time tradeoffs, suggests that we are close to resolving the computational complexity of both idempotent and integral approximate spherical range searching in the semigroup arithmetic model.

URL for the Abstract:

http://portal.acm.org/citation.cfm?id=1132516.1132598&coll=&dl=&type=series&idx=1132516&part=Proceedings&WantType=Proceedings&title=Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing&CFID=15151515&CFTOKEN=6184618



Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{AMM2006a,
AUTHOR = {Arya, Sunil and Malamatos, Theocharis and Mount, David M.},
TITLE = {On the Importance of Idempotence},
BOOKTITLE = {Proceedings of the 38th Annual ACM Symposium on Theory of Computing, STOC'06},
PUBLISHER = {ACM},
YEAR = {2006},
PAGES = {564--573},
ADDRESS = {Seattle, Washington, USA},
ISBN = {1-59593-134-1},
}


Entry last modified by Christine Kiesel, 05/02/2007
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Theocharis Malamatos
Created
11/03/2006 08:09:42 PM
Revisions
7.
6.
5.
4.
3.
Editor(s)
Christine Kiesel
Christine Kiesel
Christine Kiesel
Regina Kraemer
Regina Kraemer
Edit Dates
02.05.2007 10:41:07
02.05.2007 10:39:58
02.05.2007 10:22:57
04/16/2007 09:58:35 AM
01.02.2007 09:42:42
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section