A new lower bound for semigroup orthogonal range searching

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Standard

A new lower bound for semigroup orthogonal range searching. / Afshani, Peyman.

35th International Symposium on Computational Geometry, SoCG 2019. ed. / Gill Barequet; Yusu Wang. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. 3 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 129).

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

Harvard

Afshani, P 2019, A new lower bound for semigroup orthogonal range searching. in G Barequet & Y Wang (eds), 35th International Symposium on Computational Geometry, SoCG 2019., 3, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 129, 35th International Symposium on Computational Geometry, SoCG 2019, Portland, United States, 18/06/2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.3

APA

Afshani, P. (2019). A new lower bound for semigroup orthogonal range searching. In G. Barequet, & Y. Wang (Eds.), 35th International Symposium on Computational Geometry, SoCG 2019 [3] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Leibniz International Proceedings in Informatics, LIPIcs, Vol.. 129 https://doi.org/10.4230/LIPIcs.SoCG.2019.3

CBE

Afshani P. 2019. A new lower bound for semigroup orthogonal range searching. Barequet G, Wang Y, editors. In 35th International Symposium on Computational Geometry, SoCG 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. Article 3. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 129). https://doi.org/10.4230/LIPIcs.SoCG.2019.3

MLA

Afshani, Peyman "A new lower bound for semigroup orthogonal range searching". and Barequet, Gill Wang, Yusu (editors). 35th International Symposium on Computational Geometry, SoCG 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 129). 2019. https://doi.org/10.4230/LIPIcs.SoCG.2019.3

Vancouver

Afshani P. A new lower bound for semigroup orthogonal range searching. In Barequet G, Wang Y, editors, 35th International Symposium on Computational Geometry, SoCG 2019. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2019. 3. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 129). https://doi.org/10.4230/LIPIcs.SoCG.2019.3

Author

Afshani, Peyman. / A new lower bound for semigroup orthogonal range searching. 35th International Symposium on Computational Geometry, SoCG 2019. editor / Gill Barequet ; Yusu Wang. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2019. (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 129).

Bibtex

@inproceedings{e28a2eca971c4d1ab8fbad01a67a3c61,
title = "A new lower bound for semigroup orthogonal range searching",
abstract = "We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle{\textquoteright}s result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao{\textquoteright}s influential result had shown that the problem is already non-trivial in one dimension [14]: using m units of space, the query time Q(n) must be Ω(α(m, n) + (Formula presented.) where α(·, ·) is the inverse Ackermann{\textquoteright}s function, a very slowly growing function. In d dimensions, Bernard Chazelle [9] proved that the query time must be Q(n) = Ω((logβ n)d−1) where β = 2m/n. Chazelle{\textquoteright}s lower bound is known to be tight for when space consumption is “high” i.e., m = Ω(n logd+ε n). We have two main results. The first is a lower bound that shows Chazelle{\textquoteright}s lower bound was not tight for “low space”: we prove that we must have mQ(n) = Ω(n(log n log log n)d−1). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.",
keywords = "Data Structures, Lower bounds, Range Searching",
author = "Peyman Afshani",
year = "2019",
month = jun,
doi = "10.4230/LIPIcs.SoCG.2019.3",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Gill Barequet and Yusu Wang",
booktitle = "35th International Symposium on Computational Geometry, SoCG 2019",
note = "35th International Symposium on Computational Geometry, SoCG 2019 ; Conference date: 18-06-2019 Through 21-06-2019",

}

RIS

TY - GEN

T1 - A new lower bound for semigroup orthogonal range searching

AU - Afshani, Peyman

PY - 2019/6

Y1 - 2019/6

N2 - We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle’s result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao’s influential result had shown that the problem is already non-trivial in one dimension [14]: using m units of space, the query time Q(n) must be Ω(α(m, n) + (Formula presented.) where α(·, ·) is the inverse Ackermann’s function, a very slowly growing function. In d dimensions, Bernard Chazelle [9] proved that the query time must be Q(n) = Ω((logβ n)d−1) where β = 2m/n. Chazelle’s lower bound is known to be tight for when space consumption is “high” i.e., m = Ω(n logd+ε n). We have two main results. The first is a lower bound that shows Chazelle’s lower bound was not tight for “low space”: we prove that we must have mQ(n) = Ω(n(log n log log n)d−1). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.

AB - We report the first improvement in the space-time trade-off of lower bounds for the orthogonal range searching problem in the semigroup model, since Chazelle’s result from 1990. This is one of the very fundamental problems in range searching with a long history. Previously, Andrew Yao’s influential result had shown that the problem is already non-trivial in one dimension [14]: using m units of space, the query time Q(n) must be Ω(α(m, n) + (Formula presented.) where α(·, ·) is the inverse Ackermann’s function, a very slowly growing function. In d dimensions, Bernard Chazelle [9] proved that the query time must be Q(n) = Ω((logβ n)d−1) where β = 2m/n. Chazelle’s lower bound is known to be tight for when space consumption is “high” i.e., m = Ω(n logd+ε n). We have two main results. The first is a lower bound that shows Chazelle’s lower bound was not tight for “low space”: we prove that we must have mQ(n) = Ω(n(log n log log n)d−1). Our lower bound does not close the gap to the existing data structures, however, our second result is that our analysis is tight. Thus, we believe the gap is in fact natural since lower bounds are proven for idempotent semigroups while the data structures are built for general semigroups and thus they cannot assume (and use) the properties of an idempotent semigroup. As a result, we believe to close the gap one must study lower bounds for non-idempotent semigroups or building data structures for idempotent semigroups. We develope significantly new ideas for both of our results that could be useful in pursuing either of these directions.

KW - Data Structures

KW - Lower bounds

KW - Range Searching

UR - http://www.scopus.com/inward/record.url?scp=85068091928&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2019.3

DO - 10.4230/LIPIcs.SoCG.2019.3

M3 - Article in proceedings

AN - SCOPUS:85068091928

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th International Symposium on Computational Geometry, SoCG 2019

A2 - Barequet, Gill

A2 - Wang, Yusu

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th International Symposium on Computational Geometry, SoCG 2019

Y2 - 18 June 2019 through 21 June 2019

ER -