Dynamic inverted quadtree: A structure for pictorial databases

摘要

We present a new structure, able to support and index a pictorial database. It is a variation of the region quadtree, termed Dynamic Inverted Quadtree, which is suitable for answering queries based on image content (exact and fuzzy image pattern searching). It exhibits certain advantages over the Fully Inverted Quadtree, an analogous structure that can be used for the same purposes. On the average it requires far less disk space; image pattern searching is performed efficiently; it is dynamic; reorganization is not obligatory, it can take place at any status of the structure and can be done on-line. Apart from the presentation of the new structure, we describe the pattern searching algorithms and we analyze the average space of the structure. Moreover, we compare analytically the space needs of Fully and Dynamic Inverted Quadtrees, as well as two different storage order methods that may be used in these structures. Analysis is based on a popular model of image randomness, which we express formally as a branching process.