Approximate similarity search in metric spaces

Amato, Giuseppe

Approximate similarity search in metric spaces

dc.contributor.advisor	Fuhr, Norbert	de
dc.contributor.author	Amato, Giuseppe	de
dc.contributor.referee	Zezula, Pavel	de
dc.date.accepted	2002
dc.date.accessioned	2004-12-06T12:52:30Z
dc.date.available	2004-12-06T12:52:30Z
dc.date.created	2002-06-14	de
dc.date.issued	2002-07-17	de
dc.description.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.	en
dc.format.extent	7791861 bytes
dc.format.mimetype	application/pdf
dc.identifier.uri	http://hdl.handle.net/2003/2559
dc.identifier.uri	http://dx.doi.org/10.17877/DE290R-1180
dc.language.iso	en	de
dc.publisher	Universität Dortmund	de
dc.subject	access structures	en
dc.subject	similarity search	en
dc.subject	distance only data	en
dc.subject	approximation algorithms	en
dc.subject	metric space	en
dc.subject.ddc	004	de
dc.title	Approximate similarity search in metric spaces	en
dc.type	Text	de
dc.type.publicationtype	doctoralThesis	de
dcterms.accessRights	open access

Files

Original bundle

Now showing 1 - 1 of 1

Name:: amatount.pdf
Size:: 7.43 MB
Format:: Adobe Portable Document Format
Description:: DNB

Download

Collections

LS 06 Datenbanken und Informationssysteme