A Generic Backend for Fast Audio Fingerprint Matching
Author
Skovsgaard, Anders
Term
2. term
Education
Publication year
2008
Abstract
Denne afhandling beskriver udviklingen af et generelt bagvedliggende system (backend), der kan finde det bedste match for lydfingeraftryk. Det kan arbejde sammen med forskellige generatorer af fingeraftryk og med lydkilder, der indeholder støj. Systemet vurderer matches med en scoringsmetode, hvor scoren afhænger af, hvor mange korrekt placerede n‑grammer der findes i fingeraftrykkene. Algoritmen bruger n‑grammer (korte sekvenser) og hash‑tabeller for hurtig opslag. Derudover udvikles et lighedsmål, som hurtigt udvælger et kandidatsæt: en delmængde af databasen med fingeraftryk, der sandsynligvis passer. Søgealgoritmen garanterer ingen falske afvisninger (dvs. at den ikke overser et korrekt match), og parametre kan justeres for at ændre resultaternes pålidelighed. Eksperimentelle ydelsesstudier viser, at løsningen er størrelsesordener hurtigere end beslægtet arbejde.
This thesis presents a general-purpose backend that finds the best match for audio fingerprints. It works with various fingerprint generators and with audio sources that contain noise. The system scores matches using a method based on how many correctly positioned n-grams appear in the fingerprints. The algorithm uses n-grams (short sequences) and hash tables for fast lookup. A similarity measure is also developed to quickly form a candidate set: a subset of database fingerprints estimated as likely matches. The search algorithm guarantees no false dismissals (i.e., it will not miss a correct match), and parameters can be adjusted to change the reliability of the results. Experimental performance studies show the solution is orders of magnitude faster than related work.
[This abstract was generated with the help of AI]
Documents