Optimal and nearly optimal weighted skip lists
Visualitza/Obre
Estadístiques de LA Referencia / Recolecta
Inclou dades d'ús des de 2022
Cita com:
hdl:2117/82430
Tipus de documentReport de recerca
Data publicació1995-01-01
Condicions d'accésAccés obert
Tots els drets reservats. Aquesta obra està protegida pels drets de propietat intel·lectual i
industrial corresponents. Sense perjudici de les exempcions legals existents, queda prohibida la seva
reproducció, distribució, comunicació pública o transformació sense l'autorització del titular dels drets
Abstract
We consider the problem of building a static (i.e. no updates are performed) skip list of n elements, given these n elements and the corresponding access probabilities or weights. We develop a dynamic programming algorithm that builds an optimal skip list in the sense that the average access cost is minimized. We also consider nearly optimal skip lists, whose average access cost is not optimal but good enough, and can be built more efficiently than optimal skip lists. Several related issues are also discussed, for instance, other approaches to the construction of nearly optimal skip lists or the construction of optimal skip lists that minimize different kinds of search costs.
CitacióMartínez Parra, Conrado; Roura Ferret, Salvador. "Optimal and nearly optimal weighted skip lists". 1995.
Forma partLSI-95-34-R
Col·leccions
Fitxers | Descripció | Mida | Format | Visualitza |
---|---|---|---|---|
R95-34.ps | 249,7Kb | Postscript | Visualitza/Obre |