Encoding and manipulating pictorial data with S+-trees

Wiebren de Jonge, Peter Scheuermann, Ardie Schijf

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial Databases - 2nd Symposium, SSD 1991, Proceedings
EditorsOliver Gunther, Hans-Jorg Schek
PublisherSpringer Verlag
Number of pages19
ISBN (Print)9783540544142
StatePublished - Jan 1 1991
Event2nd Symposium on Large Spatial Databases, SSD 1991 - Zurich, Switzerland
Duration: Aug 28 1991Aug 30 1991

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume525 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd Symposium on Large Spatial Databases, SSD 1991

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Encoding and manipulating pictorial data with S<sup>+</sup>-trees'. Together they form a unique fingerprint.

Cite this