3 ms·

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 wit

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?

johnmyleswhite 6y ago
I'm not familiar with DBSCAN as a NN search system. Do you have links to using it for that purpose?
- eximius 6y ago
  > 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?
  - Eridrus 6y ago
    This is used in neural retrieval systems where you are trying to find a specific example, not a cluster.
  - abhgh 6y ago
    kNN is used for classification/regression. Are you maybe talking about k-means?
  - johnmyleswhite 6y ago
    Yes, the nearest neighbor search problem is exactly the problem of finding nearest neighbors: https://en.wikipedia.org/wiki/Nearest_neighbor_search https://en.wikipedia.org/wiki/Nearest_neighbor_search
cs702 6y ago
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.
- ghj 6y ago
  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?).
  - creato 6y ago
    The link is from google research. I'd imagine google has at least a few datasets of this scale.
visarga 6y ago
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.
- cs702 6y ago
  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 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?

johnmyleswhite 6y ago

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

eximius 6y ago
> 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?
- Eridrus 6y ago
  This is used in neural retrieval systems where you are trying to find a specific example, not a cluster.
- abhgh 6y ago
  kNN is used for classification/regression. Are you maybe talking about k-means?
- johnmyleswhite 6y ago
  Yes, the nearest neighbor search problem is exactly the problem of finding nearest neighbors: https://en.wikipedia.org/wiki/Nearest_neighbor_search https://en.wikipedia.org/wiki/Nearest_neighbor_search

cs702 6y ago

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.

ghj 6y ago
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?).
- creato 6y ago
  The link is from google research. I'd imagine google has at least a few datasets of this scale.

visarga 6y ago

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.

cs702 6y ago
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.