Is there a requirement that the measure used in Nearest Neighbor methods be a proper metric distance? What will happen if I use an arbitrary function (e.g., one that does not satisfy the triangle inequality)?
How can you convert an arbitrary function to a valid metric distance?
Replacing the euclidean distance in kNN with another distance function is equivalent to "kernelizing it." A valid Mercer kernel is any function taking two observations that is continuous, symmetric and has a positive definite covariance matrix $\forall x \in D$. Many interesting properties such as stationarity can be imbued in a kernel that make it an attractive option for things like, time-series and geospatial statistics. There exists kernels for structured input that otherwise could not be represented as fixed length vectors. There exists kernels in the literature that are not valid Mercer kernels and still empirically perform well.
If you would like to know more about kernels, I'd recommend reviewing the literature on Gaussian Processes and SVMs.
