Static optimality theorem for external memory string access

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

Static optimality theorem for external memory string access

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

Research output: Contribution to journal › Conference article › peer-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 language	English (US)
Pages (from-to)	219-227
Number of pages	9
Journal	Annual Symposium on Foundations of Computer Science - Proceedings
State	Published - 2002
Event	The 34rd Annual IEEE Symposium on Foundations of Computer Science - Vancouver, BC, Canada Duration: Nov 16 2002 → Nov 19 2002

ASJC Scopus subject areas

Hardware and Architecture

Cite this

@article{0f4a1456794c454ab1fb4c1fac2fb208,

title = "Static optimality theorem for external memory string access",

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.",

author = "Valentina Ciriani and Paolo Ferragina and Fabrizio Luccio and S. Muthukrishnan",

year = "2002",

language = "English (US)",

pages = "219--227",

journal = "Annual Symposium on Foundations of Computer Science - Proceedings",

issn = "0272-5428",

note = "The 34rd Annual IEEE Symposium on Foundations of Computer Science ; Conference date: 16-11-2002 Through 19-11-2002",

}

TY - JOUR

T1 - Static optimality theorem for external memory string access

AU - Ciriani, Valentina

AU - Ferragina, Paolo

AU - Luccio, Fabrizio

AU - Muthukrishnan, S.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0036954506&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036954506&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0036954506

SN - 0272-5428

SP - 219

EP - 227

JO - Annual Symposium on Foundations of Computer Science - Proceedings

JF - Annual Symposium on Foundations of Computer Science - Proceedings

T2 - The 34rd Annual IEEE Symposium on Foundations of Computer Science

Y2 - 16 November 2002 through 19 November 2002

ER -

Static optimality theorem for external memory string access

Abstract

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this