Okay, I didn't really understand your question but I am still taking a shot. Firstly, It depends on the fact that how separable your data is if classification is the goal. So, I would suggest doing some visualisations to get a sense of your data. You can usematplotlib if you are using python.
Interval data is going to be an issue, but depending on the data, you can make an assumption to use the middle value or better yet, see if you can create more features out of the interval, such as minimum value, maximum value etc. Now, since you have been gifted with the neighbors already, you can plot them and see how similar are they before you use any function to calculate the similarity. If they are indeed neighbors you will most likely observe a relationship between them.
Since your goal is classification, and I am assuming you have no labels so you are looking at unsupervised classification. Clustering should be the first course of action, you can play around with the distance metrics, in Nearest Neighbors and through a bit of trial and error you will probably arrive at the distance function you are looking at.
If you are only looking to figure out the distance function, it would be better if you take a small chunk of data and try some pairwise experiments with the data and the neighbors you have been given. This will be simpler and faster. You can check out the link I mentioned before to calculate pairwise distances as well.