Hacker News Reader

Comment by eximius | Hacker News Reader

I'm surprised that I don't see DBSCAN, HDBSCAN, Spectral, etc. I don't even recognize these methods. Am I missing something or have the methods I'm familiar with become obsolete that fast?

View on HN

DBSCAN, HDBSCAN, Spectral, and many other classical algorithms are not scalable. You cannot use them to search for approximate nearest neighbors, say, among several billion embeddings in a 1024-dimensional vector space, which is the sort of thing you can do with this library.

I don't know anything about this field. Are these distributed systems? A billion 1024 dimensional vectors sounds like a whole lot of memory (8 TB if each dimension is a double?).

The link is from google research. I'd imagine google has at least a few datasets of this scale.

Different category: DBSCAN is doing clustering, Approx Nearest Neighbours is a method to do dot product between a query vector and a large collection, and get a list of the top K, so it's a fast method for similarity search and ranking.

Well... the authors of this paper propose using "anisotropic vector quantization" functions that take into account the density of points in the embedding space -- instead of more conventional locality sensitive hashing functions that ignore such density. I like to think of it as "clustering" in the space of vector quantization functions, then using those functions to quantize the data for fast nn search.

The analogy with classical algorithms would be to apply something like DBSCAN or Spectral clustering to cluster points, then find a way to use the clusters to speed up nn search. In practice no one would do this; I'm mentioning it here only because I think it's a helpful analogy.

I'm not familiar with DBSCAN as a NN search system. Do you have links to using it for that purpose?

> a NN Search System

And what is that exactly? I was under the impression result of running nearest-neighbor algorithms are clusters. DBSCAN is a clustering algorithm. kNN is a clustering algorithm.

Is this used to find neighbors for use in a clustering algorithm?

This is used in neural retrieval systems where you are trying to find a specific example, not a cluster.

kNN is used for classification/regression. Are you maybe talking about k-means?

Yes, the nearest neighbor search problem is exactly the problem of finding nearest neighbors: https://en.wikipedia.org/wiki/Nearest_neighbor_search

Reply on news.ycombinator.com