De-noising Distances: A Data AnalysisPerspective
Arpan Singh, Balasubramaniam Jayaram · 2019
In data analysis, the use of a distance function is ubiquitous. There is an increased awareness about the non-intuitive, and often counterintuitive, behaviour of distances in high dimensions. Similarity Search (SS) algorithms find the best possible match for a given data point from a set of data points. As the title indicates, this work is an attempt at exploring distances, in the context of SS, from the following two perspectives: On the one hand, considering De-noising as a verb, we would like to understand the properties or characteristics of distances that play a role in an SS. On the other hand, considering De-noising as an adjective, we would like to study distances that de-noise well, i.e., given a data point that is corrupted by some noise as the input, we study the dependencies that may exist between the type of noise and the distance function that accurately finds the original data in an SS, also taking into account the other 3D’s, viz., Dimensionality, Distribution and Denseness of the data.