uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Dynamic Ordered Sets with Exponential Search Trees
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computing Science.
2007 (English)In: Journal of the ACM, ISSN 0004-5411, E-ISSN 1557-735X, Vol. 54, no 3, 1236460- p.Article in journal (Refereed) Published
Abstract [en]

We introduce exponential search trees as a novel technique for converting static polynomial space search structures for ordered sets into fully-dynamic linear space data structures. This leads to an optimal bound of O(log n/log log n) for searching and updating a dynamic set X of n integer keys in linear space. Searching X for an integer y means finding the maximum key in X which is smaller than or equal to y. This problem is equivalent to the standard text book problem of maintaining an ordered set. The best previous deterministic linear space bound was O(log n/log log n) due to Fredman and Willard from STOC 1990. No better deterministic search bound was known using polynomial space. We also get the following worst-case linear space trade-offs between the number n, the word length W, and the maximal key U < 2W: O(min log log n + log n/logW, log log n log log U/log log log U). These trade-offs are, however, not likely to be optimal. Our results are generalized to finger searching and string searching, providing optimal results for both in terms of n.

Place, publisher, year, edition, pages
2007. Vol. 54, no 3, 1236460- p.
Keyword [en]
algorithms, theory, search trees, ordered lists
National Category
Computer Science
Identifiers
URN: urn:nbn:se:uu:diva-25631DOI: 10.1145/1236457.1236460ISI: 000247980500003OAI: oai:DiVA.org:uu-25631DiVA: diva2:53405
Available from: 2007-04-18 Created: 2007-04-18 Last updated: 2017-12-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Andersson, Arne

Search in DiVA

By author/editor
Andersson, Arne
By organisation
Computing Science
In the same journal
Journal of the ACM
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 470 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf