AudioDB- Scalable approximate nearest-neighbor search with .ppt

1、Thursday, November 13, 2008,ASA 156: Statistical Approaches for Analysis of Music and Speech Audio Signals,AudioDB: Scalable approximate nearest-neighbor search with automatic radius-bounded indexing,Michael A. Casey Digital Musics Dartmouth College, Hanover, NH,Scalable Similarity,8M tracks in comm

2、ercial collection PByte of multimedia data Require passage-level retrieval ( 2 bars) Require scalable nearest-neighbor methods,Specificity,Partial track retrieval Alternate versions: remix, cover, live, album Task is mid-high specificity,Example: remixing,Original Track Remix 1 Remix 2 Remix 3,Audio

3、 Shingles, concatenate l frames of m dimensional features,A shingle is defined as:,Shingles provide contextual information about features Originally used for Internet search engines: Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, Geoffrey Zweig: “Syntactic Clustering of the Web”. Computer Ne

4、tworks 29(8-13): 1157-1166 (1997) Related to N-grams, overlapping sequences of featuresApplied to audio domain by Casey and Slaney : Casey, M. Slaney, M. “The Importance of Sequences in Musical Similarity”, in Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 2006. ICASSP 2006,Audio

5、Shingle Similarity,Audio Shingle Similarity, a query shingle drawn from a query track Q, database of audio tracks indexed by (n), a database shingle from track n,Shingles are normalized to unit vectors, therefore:,For shingles with M dimensions (M=l.m); m=12, 20; l=30,40,Open source: google: “audioD

6、B” Management of tracks, sequences, salience Automatic indexing parameters OMRAS2, Yahoo!, AWAL, CHARM, more Web-services interface (SOAP / JSON) Implementation of LSH for large N 1B 1-10 ms whole-track retrieval from 1B vectors,AudioDB: Shingle Nearest Neighbor Search,AudioDB: Shingle Nearest Neigh

7、bor Search,Whole-track similarity,Often want to know which tracks are similar Similarity depends on specificity of task Distortion / filtering / re-encoding (high) Remix with new audio material (mid) Cover song: same song, different artist (mid),Whole-track resemblance: radius-bounded search,Compute

8、 the number of shingle collisions between two tracks:,Whole-track resemblance: radius-bounded search,Compute the number of shingle collisions between two tracks:,Requires a threshold for considering shingles to be relatedNeed a way to estimate relatedness (threshold) for data set,Statistical approac

9、hes to modeling distance distributions,Distribution of minimum distances,Database: 1.4 million shingles. The left bump is the minimum between 1000 randomly selected query shingles and this database. The right bump is a small sampling (1/98 000 000) of the full histogram of all distances.,Radius-boun

10、ded retrieval performance: cover song (opus task),Performance depends critically on xthresh, the collision thresholdWant to estimate xthresh automatically from unlabelled data,Order Statistics,Minimum-value distribution is analytic Estimate the distribution parameters Substitute into minimum value d

11、istribution Define a threshold in terms of FP rate This gives an estimate of xthresh,Estimating xthresh from unlabelled data,Use theoretical statistics Null Hypothesis: H0: shingles are drawn from unrelated tracks Assume elements i.i.d., normally distributed M dimensional shingles, d effective degre

12、es of freedom: Squared distance distribution for H0,ML for background distribution,Likelihood for N data points (distances squared)d = effective degrees of freedomM = shingle dimensionality,Background distribution parameters,Likelihood for N data points (distances squared)d = effective degrees of fr

13、eedomM = shingle dimensionality,Minimum value over N samples,Minimum value distribution of unrelated shingles,Estimate of xthresh, false positive rate,Unlabelled data experiment,Unlabelled data set Known to contain: cover songs (same work, different performer) Near duplicate recordings (misattributi

14、on, encoding) Estimate background distance distribution Estimate minimum value distribution Set xthresh so FP rate is = 1% Whole-track retrieval based on shingle collisions,Cover song retrieval,Scaling,Locality sensitive hashing Trade-off approximate NN for time complexity 3 to 4 orders of magnitude

15、 speed-up No noticeable degradation in performance For optimal radius threshold,LSH,Remix retrieval via LSH,Current deployment,Large commercial collections AWAL 100,000 tracks Yahoo! 2M+ tracks, related song classifier AudioDB: open-source, international consortium of developers Google: “audioDB”,Co

16、nclusions,Radius-bounded retrieval model for tracks Shingles preserve temporal information, high d Implements mid-to-high specificity search Optimal radius threshold from order statistics null hypothesis: shingles are drawn from unrelated tracks LSH requires radius bound, automatic estimate Scales to 1B shingles+ using LSH,Thanks,Malcolm Slaney, Yahoo! Research Inc. Christophe Rhodes, Goldsmiths, U. of London Michela Magas, Goldsmiths, U. of London Funding: EPSRC: EP/E02274X/1,