S(+)-trees: An Efficient Structure for the Representation of Large Synthetic Pictures

摘要

The authors are concerned in the paper with the efficient encoding and manipulation of pixel trees that are resident on secondary devices. They introduce a new structure, the S(sup +)-tree, that consists of a paged linear treecode representation of the picture (data) and an index whose entries represent separators among some of the leafcodes embedded in the linear representation. The authors' scheme provides for very compact representation of the data and the index, while, like B(sup +)-trees, permitting easy sequential and random access. They describe an algorithm which encodes their structure from an ordered list of black leafcodes and at the same time extracts the separators among successive data pages. They also present the algorithm for random search in this structure that allows one to obtain the color of a particular quandrant or semiquadrant.