Bounds on the costs of data encodings

Abstract

Any assessment of the "cost" of encoding one data structure in another must take into account, among other issues, the intended patterns of traversing the guest structure. Two such "usage patterns," namely, worstedge traversal and all-edges-equally-likely traversal, are particularly significant, since any bounds on encoding costs relative to these patterns yield bounds relative to large classes of other patterns also. The foregoing remarks are formalized in this paper, and a number of techniques for bounding the costs of encodings relative to these special usage patterns are developed and exemplified. Specifically, data structures are represented here as undirected graphs; and a number of lower bounds on the costs of data encodings are derived by comparing various structural features of the guest and host graphs. Relevant features include both maximum and average vertex-degree, "volume," and "exposure," a measure of connectivity. © 1978 Springer-Verlag New York Inc.