Encoding and manipulating pictorial data with S⁺-trees

We are concerned in this paper with the efficient encoding and manipulation of pixel trees that are resident on secondary devices. We introduce a new structure, the S⁺-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. Our scheme provides for very compact representation of the data and the index, while, like B⁺-trees, permitting easy sequential and random access. We describe an algorithm which encodes our structure from a binary pixel array and at the same time extracts the separators among successive data pages. We also present algorithms for random and sequential search in this structure that allow us to obtain the color of a leafcode or to decode a region corresponding to a quadrant or semiquadrant.