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,
- 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?