The New Jersey Institute of Technology's
Electronic Theses & Dissertations Project

Title:	Design and analysis of algorithms for similarity search based on intrinsic dimension
Author:	Ma, Xiguo
View Online:	njit-etd2015-024 (xiv, 135 pages ~ 1.0 MB pdf)
Department:	Department of Computer Science
Degree:	Doctor of Philosophy
Program:	Computer Science
Document Type:	Dissertation
Advisory Committee:	Oria, Vincent (Committee co-chair) Houle, Michael E. (Committee co-chair) Gerbessiotis, Alexandros V. (Committee member) Theodoratos, Dimitri (Committee member) Chen, Yi (Committee member) Korn, Philip R. (Committee member)
Date:	2015-01
Keywords:	Similarity research Nearest neighbor Intrinsic dimension Dimensional testing Multi-step search Aggregation
Availability:	Unrestricted
Abstract:	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 to represent individual data objects. It is generally the case that high representational dimension would result in a significant increase in the processing cost of similarity queries. This relation is often attributed to an amalgamation of phenomena, collectively referred to as the curse of dimensionality. However, the observed effects of dimensionality in practice may not be as severe as expected. This has led to the development of models quantifying the complexity of data in terms of some measure of the intrinsic dimensionality. The generalized expansion dimension (GED) is one of such models, which estimates the intrinsic dimension in the vicinity of a query point q through the observation of the ranks and distances of pairs of neighbors with respect to q. This dissertation is mainly concerned with the design and analysis of search algorithms, based on the GED model. In particular, three variants of similarity search problem are considered, including adaptive similarity search, flexible aggregate similarity search, and subspace similarity search. The good practical performance of the proposed algorithms demonstrates the effectiveness of dimensionality-driven design of search algorithms.