Physical Sciences and Mathematics Commons^™

Design And Analysis Of Algorithms For Similarity Search Based On Intrinsic Dimension, Xiguo Ma

Dissertations

One of the most fundamental operations employed in data mining tasks such as classification, cluster analysis, and anomaly detection, is that of similarity search. It has been used in numerous fields of application such as multimedia, information retrieval, recommender systems and pattern recognition. Specifically, a similarity query aims to retrieve from the database the most similar objects to a query object, where the underlying similarity measure is usually expressed as a distance function.

The cost of processing similarity queries has been typically assessed in terms of the representational dimension of the data involved, that is, the number of features used …