### 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(log_{B} 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(log_{B}(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(log_{B} 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) log_{M/B} N) I/Os, where M is the size of the 'inner' memory.

Original language | English (US) |
---|---|

Title of host publication | Automata, Languages and Programming - 29th International Colloquium, ICALP 2002, Proceedings |

Editors | Peter Widmayer, Stephan Eidenbenz, Francisco Triguero, Rafael Morales, Ricardo Conejo, Matthew Hennessy |

Publisher | Springer Verlag |

Pages | 195-207 |

Number of pages | 13 |

ISBN (Print) | 3540438645, 9783540438649 |

DOIs | |

State | Published - 2002 |

Event | 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 - Malaga, Spain Duration: Jul 8 2002 → Jul 13 2002 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 2380 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 29th International Colloquium on Automata, Languages, and Programming, ICALP 2002 |
---|---|

Country | Spain |

City | Malaga |

Period | 7/8/02 → 7/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

*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