Name
Abstract | ||
|---|---|---|
We consider self-organizing data structures when the number of data accesses is unknown. We show that certain general rearrangement
rules can be modified to reduce significantly the number of data moves, without affecting the asymptotic cost of a data access.
As a special case, explicit formulae are given for the expected cost of a data access and the expected number of data moves
for the modified move-to-front rules for linear lists and binary trees. Since a data move usually costs at least as much as
a data access, the modified rule eventually leads to a savings in total cost (the sum of data accesses and moves). |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1007/BF01759046 | Algorithmica |
Keywords | Field | DocType |
Self-organizing data structures,Move-to-front heuristic | Data structure,Explicit formulae,Combinatorics,Computer science,Binary tree,Theoretical computer science,Expected value,Expected cost,Data access,Total cost,Special case | Journal |
Volume | Issue | ISSN |
6 | 2 | 0178-4617 |
Citations | PageRank | References |
4 | 0.55 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjiv Kapoor | 1 | 4 | 0.55 |
| Edward M. Reingold | 2 | 2214 | 563.65 |