Suffix tree indexing for music information retrieval

Abstract

Bu tez çalışması, müziksel veri tabanlarından hızlı ve güvenli veri erişimi hedeflemiştir. Bu amaçla gerek tek sesli, gerekse çok sesli müzik dosyalarında veri indirgeme ve dizinleme yaklaşımları önermiştir. Çalışmanın literatüre katkısı üç alt konudandır. Bunlar veri indirgeme, sonek ağacıyla dizinleme ve ağacın dışsal bellekte yerleşimi. Veri indirgeme sürecini temin etmek amacıyla yeni bir ezgi çıkarım algoritmaları önermekteyiz. Geliştirdiğimiz ezgi çıkarım algoritması nota perdelerinin histogram ve entropisini dikkate almaktadır. Süreç sonunda ezgiye katkıda bulunmadığı tespit edilen notalar veri setinden atılmaktadır. Dizinleme açısından ise akışkan müziksel nota serilerinin dizinlenmesini sağlayacak yeni bir sonek ağacı önermekteyiz. Gözlemlerimize göre mevcut sonek ağaçları müzik verilerini dizinlemek amacıyla tasarlanmamıştır. Bu eksikliği gidermek amacıyla sonek ağacının fiziksel yapısı, müziğe göre uyarlanmıştır. En son olarak sonek ağacının dengesiz yapısı ve belleğe yerleşimi irdelenmiştir. Daha açık bir ifade iler dışsal belleğe erişimi azaltmak için müziksel verilerin dizinlenmeden önce sınıflandırılması önerilmiştir. Böylece her bir sınıfa ait müzik verileri ayrı bir ağaçta dizinlenecektir. Gerek melodi çıkarma, gerekse sonek ağacı inşasına ilişkin yaklaşımları detaylı şekilde test edilmiş ve tartışılmıştır. Deneylerin değerlendirilmesi için müzik kulağı, matematiksel ispatlar ve simulasyon kullanılmıştır. This thesis intended for fast and reliable data retrieval from music databases. It introduces new data reduction and indexing approaches for both polyphonic and monophonic music sequences. The study contributes to the literature from three aspects. These are data reduction, suffix tree indexing and tree alignment on external memory. In terms of data reduction, we present a new melody extraction approach for polyphonic music sequences. The new melody extraction approach considers the pitch histogram, and entropy of music sequences. Consequently, accompany channels of the MIDI music sequences are determined for data reduction. In terms of indexing, we present a new suffix tree construction approach for streaming music sequences. Current suffix tree construction algorithms have leaks about indexing music sequences. Hence, we adapted the physical structure of suffix trees for music notes. At last, we consider balance and alignment of suffix trees. In music, alphabet size of music is large. Therefore, we present clustering of music sequence. Therefore each sequence cluster can be indexed by a separate suffix tree to balance the tree. Both our melody extraction and suffix tree construction approaches are tested in detail and discussed. Our evaluation metrics are based on cognition, mathematical proofs and simulations. Experimental results showed that our approaches outperforms.