Exponential structures for efficient cache-oblivious algorithms

Michael A. Bender, Richard Cole, Rajeev Raman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We present cache-oblivious data structures based upon exponential structures. These data structures perform well on a hierarchical memory but do not depend on any parameters of the hierarchy, including the block sizes and number of blocks at each level. The problems we consider are searching, partial persistence and planar point location. On a hierarchical memory where data is transferred in blocks of size B, some of the results we achieve are: - We give a linear-space data structure for dynamic searching that supports searches and updates in optimal O(logB N) worst-case I/Os, eliminating amortization from the result of Bender, Demaine, and Farach-Colton (FOCS '00).We also consider finger searches and updates and batched searches. - We support partially-persistent operations on an ordered set, namely, we allow searches in any previous version of the set and updates to the latest version of the set (an update creates a new version of the set). All operations take an optimal O(logB(m+N)) amortized I/Os, whereN is the size of the version being searched/updated, and m is the number of versions. - We solve the planar point location problem in linear space, taking optimal O(logB N) I/Os for point location queries, where N is the number of line segments specifying the partition of the plane. The pre-processing requires O((N/B) logM/B N) I/Os, where M is the size of the 'inner' memory.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings
EditorsPeter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy
PublisherSpringer Verlag
Pages195-207
Number of pages13
ISBN (Print)3540438645, 9783540438649
DOIs
StatePublished - 2002
Event29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 - Malaga, Spain
Duration: Jul 8 2002Jul 13 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2380 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other29th International Colloquium on Automata, Languages, and Programming, ICALP 2002
CountrySpain
CityMalaga
Period7/8/027/13/02

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Exponential structures for efficient cache-oblivious algorithms'. Together they form a unique fingerprint.

  • Cite this

    Bender, M. A., Cole, R., & Raman, R. (2002). Exponential structures for efficient cache-oblivious algorithms. In P. Widmayer, S. Eidenbenz, F. Triguero, R. Morales, R. Conejo, & M. Hennessy (Eds.), Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings (pp. 195-207). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2380 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-45465-9_18