Design and analysis of algorithms for similarity search based on intrinsic dimension

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.

Name thesis:degree_name

Doctor of Philosophy in Computing Sciences - (Ph.D.)

Discipline thesis:degree_discipline

Computer Science

Year

2015

Author dc:creator

• Ma, Xiguo

Contributors dc:contributor

• Vincent Oria
• Michael E. Houle
• Alexandros V. Gerbessiotis

• Similarity research
• Nearest neighbor
• Intrinsic dimension
• Dimensional testing
• Multi-step search
• Aggregation
• Computer Sciences

Repository record dc:identifier

https://digitalcommons.njit.edu/dissertations/102

OAI identifier oai:identifier

oai:digitalcommons.njit.edu:dissertations-1157