I'm trying to find an indexing data structure most suitable for my metric space:

  • set of IP network related data (IP addresses, ports, TCP flags, ...),
  • distance function is continuous, non-Euclidean but satisfies non-negativity, symmetry and triangle inequality,

with respect to the fixed-radius range query performance. I want to use it for a clustering algorithm (DBSCAN or similar) on a data sets with millions of elements. So far I have studied:

  • ball trees/VPT,
  • MVPT,
  • GHT, GNAT,
  • cover trees,

and basically all other methods from Searching in metric spaces survey, but all mentioned are suited for varying-radius queries. Many related SO answers advise Locality-sensitive hashing (LSH) as a current trend, but I didn't find any clear information whether it exploits the advantage of fixed-range and whether it is usable for non-Euclidean metrics. Any advices/references?

  • $\begingroup$ Try some of the indexes in ELKI to see what works best for your distance function... $\endgroup$ Feb 16, 2017 at 19:18
  • $\begingroup$ @Anony-Mousse In ELKI there are only cover trees and M-trees metrical indexes. Others (including LSH) can be used with certain subset of distance functions only. $\endgroup$
    – Jan Wrona
    Feb 17, 2017 at 10:56
  • $\begingroup$ Yes, LSH etc. need specializations for every distance function. So you'll have to do this yourself. $\endgroup$ Feb 18, 2017 at 1:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.