1 Search Results for "Kephart, Owen"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2017.20

Non-Adaptive Data Structure Bounds for Dynamic Predecessor

Authors: Joseph Boninger, Joshua Brody, and Owen Kephart

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract

In this work, we continue the examination of the role non-adaptivity plays in maintaining dynamic data structures, initiated by Brody and Larsen. We consider non-adaptive data structures for predecessor search in the w-bit cell probe model. In this problem, the goal is to dynamically maintain a subset T of up to n elements from {1, ..., m}, while supporting insertions, deletions, and a predecessor query Pred(x), which returns the largest element in T that is less than or equal to x. Predecessor search is one of the most well-studied data structure problems. For this problem, using non-adaptivity comes at a steep price. We provide exponential cell probe complexity separations between (i) adaptive and non-adaptive data structures and (ii) non-adaptive and memoryless data structures for predecessor search. A classic data structure of van Emde Boas solves dynamic predecessor search in log(log(m)) probes; this data structure is adaptive. For dynamic data structures which make non-adaptive updates, we show the cell probe complexity is O(log(m)/log(w/log(m))). We also give a nearly-matching Omega(log(m)/log(w)) lower bound. We also give an m/w lower bound for memoryless data structures. Our lower bound technique is tailored to non-adaptive (as opposed to memoryless) updates and might be of independent interest.

Cite as

Joseph Boninger, Joshua Brody, and Owen Kephart. Non-Adaptive Data Structure Bounds for Dynamic Predecessor. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 20:1-20:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boninger_et_al:LIPIcs.FSTTCS.2017.20,
  author =	{Boninger, Joseph and Brody, Joshua and Kephart, Owen},
  title =	{{Non-Adaptive Data Structure Bounds for Dynamic Predecessor}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{20:1--20:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.20},
  URN =		{urn:nbn:de:0030-drops-83892},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.20},
  annote =	{Keywords: dynamic data structures, lower bounds, predecessor search, non-adaptivity}
}

Refine by Author
1 Boninger, Joseph
1 Brody, Joshua
1 Kephart, Owen

Refine by Classification

Refine by Keyword
1 dynamic data structures
1 lower bounds
1 non-adaptivity
1 predecessor search

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Kephart, Owen"

Non-Adaptive Data Structure Bounds for Dynamic Predecessor

Abstract

Cite as

Thanks for your feedback!

Could not send message