A New dynamic and adaptive scheme for indexing in metric spaces

üOZET˙ ˙ ˙şË™ ˙ ˙METRIK UZAYLARDA INDEKSLEME ICIN DINAMIK˙ ˙˙ üVE ADAPTIF YENI BIR YONTEMUmut TOSUNBilgisayar Mühendisliği, Yüksek Lisansu g uTez Yüneticisi: Dr. Cengiz Celiko şüuTez Yüneticisi: Prof. Dr. Ozgür UlusoyoAğustos, 2007gBilgisayar Bilimi uygulamaları, genellikle verinin etkin bir bişimde depolan-cması ve getirilmesi ile ilgilenirler. Geleneksel veritabanlarının iyi tanımlanmışs˙ skisel Veritabanı paradigmasını kullanarakyapısı, gereken sorgu nesnelerine Ilişetkin bir şekilde erişmeyi sağlar. Fakat günümüzde gürüntü, video, ses klibi ves s g uu u ou umetin dükümanı gibi yapısal olmayan ve karmaşık veri ile uğraşmanın zorluk-ou s gslarıyla karşılaşılmaktadır. Multimedya Veri Edinme, Veri Madenciliği, Gürüntüss g ou uü grenmesi, Bilgisayar Gürüsü, Biyomedikal VeritabanlarıTanıma, Makina Oğ ouukarmaşık verinin etkin bir bişimde yünetilmesini gerektiren alanlardır. Karmaşıks c o sve yapısal olmayan veri şoğu zaman iyi tanımlanmış parşalara bülünememekte vecg s c outam bir eşleme sorguları tanımlamak işin uygulanamamaktadır. Bunun yerine,s ckullanılacak bir sorgu nesnesi yada prototip nesne sağlayarak benzer nesnelerigveritabanının getirmesini sağlayan benzerlik araştırması kullanılmaktadır.g sBenzerlik Araştırması işin bir popüler yaklaşım da veritabanı nesneleris c u sarasındaki ilişkiyi vektür uzayında ifade ederek bu ilişkiye yaklaşmaya şalışmaktır.s o s s csLiteratürde vektür uzaylarındaki benzerlik sorgusunu destekleyen iyi bilinen in-u odeksleme yüntemleri bulunmaktadır. Fakat bu yüntemlerin yüksek boyutlu verio o uişin etkili olmadığı güsterilmiştir. Diğer bir yaklaşım ise indeksleme işin Metrikc go s g s cUzaylar modelini kullanmaktır. Metrik Uzaylar uşgensel eşitsizlik üzelliği taşıyanüc s o gsbir uzaklık fonksyonu ile tanımlanırlar. Verinin iş yapısı ile ilgili varsayımlar ol-cmadığı işin yüksek seviyeli bir soyutlama sağlarlar ve daha fazla uygulanabilirliğegc u g gsahiptirler. Yüksek boyutlarda daha iyi performans sağladıkları da güsterilmiştir.u g o sDaha ünceki bir şok şalışma indeks yapısı oluşturulduktan sonra yeni nesneo c cs sviviieklenmesine izin vermeyen statik metotlara konsantre olmuştur. M-Ağaş, Slims gcAğaş, DF-Ağaş, Omni bazı popüler dinamik yapılardır. Bu metotlar taşangc gc u sdügumleri ayırarak ve ağaca B-Ağaş şeşitleri gibi yeni seviyeler ekleyerek ar-uğü g gccstarak büyüyebilirler. Maalesef bu yüntemler AESA, LAESA, Spaghettis ve Kvpuu ogibi sabit global pivot seti taşıyan düz yapılara güre şok daha kütü performanss u oc ougüstermektedirler. Sorgu nesnesi ve pivotlar arasındaki uzaklıklar hesaplanarak,overitabanının bir kısmı ünemli olmaktan şıkarılır. Pivot sayısı daha fazla seşiciliko c csağlamak işin kolaylıkla arttırılabilir ve daha iyi performans elde edilir. Fakat bellig cbir sorgu yarışapı işin optimum sayıda pivot bulunmaktadır ve şok fazla pivotc c ckullanımı sorgu ve indeks oluşturma maliyetlerini arttırır. Yakın zamanda yenisveritabanı nesneleri eklenebilen ve dinamik bir şekilde yeni nesnelerin bazılarınıspivot olarak seşerek ilerleyen LAESA varyasyonu Sparse Spatial Selection(SSS)ctakdim edilmiştir.sBu tezde SSS yünteminin kümelenmiş ve bir uca toplanmış dağılımlar işino u s sg cyol aştığı temel problemlere değinilecektir. Gerşek veri gruplarında bu türcg g c uüzellikler sıklıkla güzlemlenmiştir. SSS'in simetrik ve dengeli dağılımlar ayrıcao o s güzel sorgu yarışapları işin optimize edildiği güsterilecektir. Bu tezin ilk ana katkısıo c c gokümelenmiş yada bir uca toplanmış veride uygulanabilecek yeni bir pivot seşimu s s c˙yüntemi sunmaktır. Ikinci katkı ise değişik sorgu yarışapları işin doğru pivoto gs c c gseşim sayısını bulmak olacaktır. Ayrıca sunulacak yeni indeksleme yüntemininc onesne ekleme maliyetine yük getirmezken ağaş tabanlı uygulamalara güre şoku gc ocdaha iyi performans sağladığı güsterilmektedir. Bunun yanı sıra bu yeni yapıg goveritabanındaki populasyon artışlarına da ustün şekilde adapte olabilmektedir.s üusAnahtar süzcükler : Metrik Uzay, Metrik Erişim Metotları, Kvp, Hkvp, EcKvp,ou sM-Ağaş, Slim-Ağaş, DF-Ağaş, Pivot, Uzaklık Hesaplaması.gc gc gc