Name
Abstract | ||
|---|---|---|
Let R1 , ... , R nbe a linear list of n elements. W ea ssume the independent reference model, with a fixed but unknown access probability vector .W es urvey briefly the problem of reorganizing the list dynamically ,o nt he basis of accrued references, with the objective o fm inimizing the expected access-cost. The Counter Scheme (CS) is known to be asymptotically optimal for this purpose. The paper explores the CS, with the aim of reducing its storage requirements. We s tart with a detailed exposition of its cost function and then point out that it interacts with the access model to produce some remarkable synergistic effects. These mak ei tp ossible to use very effective 'truncated versions' of the CS, which have very modest space requirements. The versions we consider are: (i) The 'Limited-Counters Scheme', which bounds each of the frequenc yc ounters to a maximal value c. (ii) The original CS with a bound on the number of references during which the scheme is active. The bound is chosen to achieve a desired access cost, compared with the optimal policy. |
Year | DOI | Venue |
|---|---|---|
1991 | 10.1016/0196-6774(91)90032-T | J. Algorithms |
Keywords | Field | DocType |
statistical synergy,independent reference,self-organizing list,cost function,reference model,self organization | Data structure,Discrete mathematics,Data processing,Space requirements,Computer science,Algorithm,Theoretical computer science,Independent Reference Model,Probability vector,List processing,Asymptotically optimal algorithm | Journal |
Volume | Issue | ISSN |
12 | 4 | 0196-6774 |
Citations | PageRank | References |
4 | 0.65 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Micha Hofri | 1 | 342 | 127.96 |
| Hadas Shachnai | 2 | 960 | 78.85 |