AbstractThe technique of overlapping region quadtrees results in significant space reduction. This new form of data structure is suitable for representing sequences of similar binary raster images emerging in many areas. Apart from a short introduction to the method of overlapping, an analysis of the space reduction achieved is presented in this article. First, a general theorem about the average number of common nodes of two images obeying a general model is given. Next, two models of image similarity are introduced and the respective formulae are derived from the general one. Evaluating these formulae for various parameters shows the efficiency of overlapping.
Categories and Subject Descriptors: E.1 [Data Structures]; E.2 [Data Storage Representations]; F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.1 [Discrete Mathematics]: Combinatorics; G.2.2 [Discrete Mathematics]: Graph Theory; H.2.2 [Database Management]: Physical Design
Additional Key Words and Phrases: algorithms, performance, quadtrees, random images, overlapping data stuctures
Selected references
- Raphael A. Finkel and Jon Louis Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4:1-9, 1974.
- Hanan Samet. The quadtree and related hierarchical data structures. ACM Computing Surveys, 16(2):187-260, June 1984.