Full metadata record
DC FieldValueLanguage
dc.contributor.advisorFuhr, Norbertde
dc.contributor.authorAmato, Giuseppede
dc.description.abstractThere 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.en
dc.format.extent7791861 bytes-
dc.publisherUniversität Dortmundde
dc.subjectaccess structuresen
dc.subjectsimilarity searchen
dc.subjectdistance only dataen
dc.subjectapproximation algorithmsen
dc.subjectmetric spaceen
dc.titleApproximate similarity search in metric spacesen
dc.contributor.refereeZezula, Pavelde
dcterms.accessRightsopen access-
Appears in Collections:LS 06 Datenbanken und Informationssysteme

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

This item is protected by original copyright

This item is protected by original copyright rightsstatements.org