6
$\begingroup$

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,
  • AESA/LAESA,
  • 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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Try some of the indexes in ELKI to see what works best for your distance function... $\endgroup$
    – Has QUIT--Anony-Mousse
    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$
    – Has QUIT--Anony-Mousse
    Feb 18, 2017 at 1:02

0

Reset to default

Your Answer

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