A. Mosig,
Algorithmen und Datenstrukturen zur effizienten
Konstellationssuche
(in German, Algorithms and data structures
for efficient constellation search),
Master's thesis,
Univ. Bonn, 2001.
In this thesis, the concept of G-inverted lists is applied to
content-based retrieval of three dimensional
surfaces. G-inverted lists generalize the concept of inverted
file indices known from full text retrieval by the means of group
theory. In the case of three dimensional surfaces, fragments of a
query surface can be retrieved from a large database of pattern
surfaces. The query fragment is retrieved independant of rotation or
translation against the database patterns.
For the prupose of 3D-surface retrieval, the concept of
G-inverted lists needs to be equipped with certain mechanisms
of fault tolerance. To this end, a method for fuzzy set intersections
is introduced and the $\eps$kd-tree data structure is
introduced. This variant of kd-trees allows range queries to be
performed in logarithmic time if the query range is bounded by the
minimum distance of the underlying point set.
Furthermore, G-inverted lists are studied from the category
theory point of view and, finally, issues of index compression based
on Elias-gamma coes, Elias-delta codes and Golomb codes are discussed
briefly.