Static optimality theorem for external memory string access

Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan

    Research output: Contribution to journalConference articlepeer-review

    Abstract

    The problem of designing data structures for external memory string access when a sequence of queries has to be performed is addressed. A novel, and conceptually simple, self-adjusting skip list (SASL) that adapts itself to the distribution of string queries without explicitly setting weight constraints is proposed. The scheme is optimal with respect to the best offline static string index in external memory.

    Original languageEnglish (US)
    Pages (from-to)219-227
    Number of pages9
    JournalAnnual Symposium on Foundations of Computer Science - Proceedings
    StatePublished - 2002
    EventThe 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada
    Duration: Nov 16 2002Nov 19 2002

    ASJC Scopus subject areas

    • Hardware and Architecture

    Fingerprint Dive into the research topics of 'Static optimality theorem for external memory string access'. Together they form a unique fingerprint.

    Cite this