4 ms·

Last I checked Dejavu doesn't use LSH or any approximations. It simply queries for exact matches, "aligns" them, and determines if there is enough signal from t

Last I checked Dejavu doesn't use LSH or any approximations. It simply queries for exact matches, "aligns" them, and determines if there is enough signal from the noise to consider it a match.

bequanna 3y ago
Ahh, I see. The approach here is just getting vector nearest neighbors. I guess I don’t see how this could work like “Shazam” when you’re comparing the vector of some sample to the vector for the whole song.
- willseth 3y ago
  Oh, no, it's not for the whole song. For each song, you take N samples, each sample gets converted into a fingerprint, and all of the fingerprints are stored in a database. Then when you query, you perform the same sample-to-fingerprint computation, and query the database for matching fingerprints. The database will return many false positives, but only 1 will "align", meaning the relative timing of the fingerprints returned is in sync with an actual song in the database. Once the number of aligned fingerprints reaches a set threshold, you can stop and return it as a result. That's how it performs subset matching.
  - bequanna 3y ago
    Gotcha. So taking n overlapping samples for the song, fingerprinting then vectorizing each. Then doing the same thing for the captured sample and getting nearest neighbors. I’ve used dejavu for a personal project and it is quite fast. Is the LSH approach somehow more efficient/attractive now because we’ve made strides in vector nearest neighbors search?
    - willseth 3y ago
      Almost, but dejavu doesn't search nearest-neighbors. It searches for exact matches, so its robustness is essentially based on oversampling. Nearest neighbor search might be a way to achieve similar robustness with fewer fingerprints - assuming it results in fewer false negatives. LSH is one way to approach nearest neighbor search. So in theory you could modify dejavu with an LSH-based NN search and potentially increase robustness with less data, modulo whatever tradeoffs are necessary for computing NN search.

Last I checked Dejavu doesn't use LSH or any approximations. It simply queries for exact matches, "aligns" them, and determines if there is enough signal from the noise to consider it a match.

bequanna 3y ago

Ahh, I see. The approach here is just getting vector nearest neighbors. I guess I don’t see how this could work like “Shazam” when you’re comparing the vector of some sample to the vector for the whole song.

willseth 3y ago
Oh, no, it's not for the whole song. For each song, you take N samples, each sample gets converted into a fingerprint, and all of the fingerprints are stored in a database. Then when you query, you perform the same sample-to-fingerprint computation, and query the database for matching fingerprints. The database will return many false positives, but only 1 will "align", meaning the relative timing of the fingerprints returned is in sync with an actual song in the database. Once the number of aligned fingerprints reaches a set threshold, you can stop and return it as a result. That's how it performs subset matching.
- bequanna 3y ago
  Gotcha. So taking n overlapping samples for the song, fingerprinting then vectorizing each. Then doing the same thing for the captured sample and getting nearest neighbors. I’ve used dejavu for a personal project and it is quite fast. Is the LSH approach somehow more efficient/attractive now because we’ve made strides in vector nearest neighbors search?
  - willseth 3y ago
    Almost, but dejavu doesn't search nearest-neighbors. It searches for exact matches, so its robustness is essentially based on oversampling. Nearest neighbor search might be a way to achieve similar robustness with fewer fingerprints - assuming it results in fewer false negatives. LSH is one way to approach nearest neighbor search. So in theory you could modify dejavu with an LSH-based NN search and potentially increase robustness with less data, modulo whatever tradeoffs are necessary for computing NN search.