Authors: Amato, Giuseppe
Title: Approximate similarity search in metric spaces
Language (ISO): en
Abstract: There is an urgent need to improve the efficiency of similarity queries. For this reason, this thesis investigates approximate similarity search in the environment of metric spaces. Four different approximation techniques are proposed, each of which obtain high performance at the price of tolerable imprecision in the results. Measures are defined to quantify the improvement of performance obtained and the quality of approximations. The proposed techniques were tested on various synthetic and real-lifefiles. The results of the experiments confirm the hypothesis that high quality approximate similarity search can be performed at a much lower cost than exact similarity search. The approaches that we propose provide an improvement of efficiency of up to two orders of magnitude, guaranteeing a good quality of the approximation.The most promising of the proposed techniques exploits the measurement of the proximity of ball regions in metric spaces. The proximity of two ball regions is defined as the probability that data objects are contained in their intersection. This probability can be easily obtained in vector spaces but is very difficult to measure in generic metric spaces, where only distance distribution is available and data distribution cannot be used. Alternative techniques, which can be used to estimate such probability inmetric spaces, are thus also proposed, discussed, and validated in the thesis.
Subject Headings: access structures
similarity search
distance only data
approximation algorithms
metric space
Issue Date: 2002-07-17
Provenance: Universität Dortmund
Appears in Collections:LS 06 Informationssysteme und Sicherheit (ISSI), Information Engineering (IE)

Files in This Item:
File Description SizeFormat 
amatount.pdfDNB7.61 MBAdobe PDFView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.