The Gauss-Tree: Efficient Object Identification of Uncertain Data

Speaker: CHUI Chun Kit

Abstract

In applications of biometric databases the typical task is to identify individuals according to features which are not exactly known. Reasons for this inexactness are varying measuring techniques or environmental circumstances. Since these circumstances are not necessarily the same when determining the features for different individuals, the exactness might strongly vary between the individuals as well as between the features. To identify individuals, similarity search on feature vectors is applicable, but even the use of adaptable distance measures is not capable to handle objects having an individual level of exactness. Therefore, the authors develop a comprehensive probabilistic theory in which uncertain observations are modeled by probabilistic feature vectors (pfv), i.e. feature vectors where the conventional feature values are replaced by Gaussian probability distribution functions. Each feature value of each object is complemented by a variance value indicating its uncertainty. The authors define two types of identification queries, k-mostlikely identification and threshold identification. For efficient query processing, the authors propose a novel index structure, the Gauss-tree. Experimental evaluation demonstrates that pfv stored in a Gauss-tree significantly improve the result quality compared to traditional feature vectors. Additionally, the authors show that the Gauss-tree significantly speeds up query times compared to competitive methods.