S⁺-Trees: An Efficient Structure for the Representation of Large Pictures

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 implicitly embedded in the linear representation. Our scheme combines the advantages of treecode and leafcode representations by offering the space efficiency of DR-expressions and the indexing capabilities of B⁺-trees, thus permitting easy sequential and random access to a compact representation of pictorial data. We describe an algorithm which encodes our structure from an ordered list of black leafcodes. The paged structure of the S⁺-tree, whereby each data page is a self-contained tree, enables to design an efficient random access search algorithm to find the color of a given region that corresponds to a quadrant or semi-quadrant. The search algorithm is non-recursive in nature and it can be optimized to work bytewise instead of bitwise. We also present an efficient method for performing translation operations on large pictures stored on secondary devices and illustrate its efficiency with the S⁺-treestructure.