Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Embedding-based subsequence matching with gaps-range-tolerances: a Query-By-Humming application
Stockholms universitet, Samhällsvetenskapliga fakulteten, Institutionen för data- och systemvetenskap.
Stockholms universitet, Samhällsvetenskapliga fakulteten, Institutionen för data- och systemvetenskap.
Visa övriga samt affilieringar
Antal upphovsmän: 5
2015 (Engelska)Ingår i: The VLDB journal, ISSN 1066-8888, E-ISSN 0949-877X, Vol. 24, nr 4, 519-536 s.Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We present a subsequence matching framework that allows for gaps in both query and target sequences, employs variable matching tolerance efficiently tuned for each query and target sequence, and constrains the maximum matching range. Using this framework, a dynamic programming method is proposed, called SMBGT, that, given a short query sequence Q and a large database, identifies in quadratic time the subsequence of the database that best matches Q. SMBGT is highly applicable to music retrieval. However, in Query-By-Humming applications, runtime is critical. Hence, we propose a novel embedding-based approach, called ISMBGT, for speeding up search under SMBGT. Using a set of reference sequences, ISMBGT maps both Q and each position of each database sequence into vectors. The database vectors closest to the query vector are identified, and SMBGT is then applied between Q and the subsequences that correspond to those database vectors. The key novelties of ISMBGT are that it does not require training, it is query sensitive, and it exploits the flexibility of SMBGT. We present an extensive experimental evaluation using synthetic and hummed queries on a large music database. Our findings show that ISMBGT can achieve speedups of up to an order of magnitude against brute-force search and over an order of magnitude against cDTW, while maintaining a retrieval accuracy very close to that of brute-force search.

Ort, förlag, år, upplaga, sidor
2015. Vol. 24, nr 4, 519-536 s.
Nyckelord [en]
Subsequence matching, Query-By-Humming, Indexing, Embeddings
Nationell ämneskategori
Elektroteknik och elektronik Systemvetenskap, informationssystem och informatik
Identifikatorer
URN: urn:nbn:se:su:diva-119533DOI: 10.1007/s00778-015-0387-0ISI: 000358255800003OAI: oai:DiVA.org:su-119533DiVA: diva2:847835
Tillgänglig från: 2015-08-21 Skapad: 2015-08-17 Senast uppdaterad: 2015-08-21Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas

Övriga länkar

Förlagets fulltext

Sök vidare i DiVA

Av författaren/redaktören
Karlsson, IsakPapapetrou, Panagiotis
Av organisationen
Institutionen för data- och systemvetenskap
I samma tidskrift
The VLDB journal
Elektroteknik och elektronikSystemvetenskap, informationssystem och informatik

Sök vidare utanför DiVA

GoogleGoogle Scholar

Altmetricpoäng

Totalt: 29 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf