A New dynamic and adaptive scheme for indexing in metric spaces
Metrik uzaylarda indeksleme için dinamik ve adaptif yeni bir yöntem
- Tez No: 199892
- Danışmanlar: DR. CENGİZ ÇELİK, PROF.DR. ÖZGÜR ULUSOY
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Metric Space, Metric Access Methods, Kvp, Hkvp, EcKvp, M-Tree, Slim-Tree, DF-Tree, Pivot, Distance Computation
- Yıl: 2007
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 89
Özet
ü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
Özet (Çeviri)
ABSTRACTA NEW DYNAMIC AND ADAPTIVE SCHEME FORINDEXING IN METRIC SPACESUmut TOSUNM.S. in Computer EngineeringSupervisor: Dr. Cengiz Celikşü ur UlusoyCo-Supervisor: Prof. Dr. OzgüAugust, 2007Computer Science applications are often concerned with eï¬cient storage andretrieval of data. Well deï¬ned structure of traditional databases help to accessrequired query objects eï¬ectively using the Relational Database paradigm. How-ever, in recent times, we are faced with the challenges of dealing with unstruc-tured and complex data such as images, video, sound clips and text documents.Multimedia Information Retrieval, Data Mining, Pattern Recognition, MachineLearning, Computer Vision and Biomedical Databases are examples of the ï¬eldsthat require eï¬cient management of complex data. Complex, unstructured typeof data often cannot be broken down into well-deï¬ned components, and exactmatching cannot be applied for deï¬ning queries. Instead, the notion of similaritysearch is used where a query or prototype object is provided by the user and thedatabase retrieves the objects that are similar.One popular approach for similarity searching is to approximate the relation-ship between database objects by mapping them into a vector space. There arewell-known indexing methods in literature that support similarity queries in vec-tor spaces, however, it has been shown that these methods are ineï¬ective for highdimensional data. Another approach is to use Metric Spaces model for indexing.Metric spaces are deï¬ned by a distance function that has the triangular inequalityproperty. Since there are no assumptions about the structure of the data itself,they constitute a higher level abstraction and thus have more applicability. Theyhave also been shown to perform better in higher dimensions.A lot of the previous work in metric spaces have concentrated on static meth-ods that do not allow new insertions once the index structure has been initialized.ivvM-Tree, Slim-Tree, DF-Tree, Omni are some of the popular dynamic structures.These methods can grow incrementally by splitting overï¬owed nodes and addingnew levels to the tree very much like the B-tree variants. Unfortunately, they havebeen shown to perform very poorly compared to ï¬at structures such as AESA,LAESA, Spaghettis and Kvp that use a ï¬xed set of global pivots. The distancesbetween the query object and the pivots are computed to eliminate some portionof the database from consideration. The number of pivots can be easily increasedto provide more selectivity, thus better query performance. However, there is anoptimum number of pivots for a given query radius, and using too many pivotsincreases the costs of queries and the initialization of the index. Recently, SparseSpatial Selection(SSS) was introduced as a LAESA variant that allows insertionsof new database objects and dynamically promotes some of the new objects aspivots.In this thesis, we argue that SSS has fundamental problems that results inpoor query performance for clustered or otherwise skewed distributions. Realdatasets have often been observed to show such characteristics. We show thatSSS has been optimized to work for a symmetrical, balanced distribution andfor a speciï¬c radius value. Our ï¬rst main contribution is oï¬ering a new pivotpromotion scheme that can perform robustly for clustered or skewed distributions.Our second contribution is proposing new methods that solve the problem ofdetermining the right number of pivots for diï¬erent query radius values. Weshow that our new indexing scheme performs signiï¬cantly better than tree-baseddynamic structures while having lower insertion costs. We also show that ourstructure adapts to changes in the database population in a superior way.
Benzer Tezler
- An efficient energy scheme for hybrid clustering wireless sensor networks
Hibrit kümelenme kablosuz algılayıcı ağları için verimli enerji programı
AHMED M. SALEEM
Yüksek Lisans
İngilizce
2015
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolÇankaya ÜniversitesiMatematik ve Bilgisayar Bilimleri Ana Bilim Dalı
YRD. DOÇ. DR. SİBEL TARIYAN ÖZYER
- Yeni bir hata değişik delta ağ maddeli arttırılmış delta ağı (ADA)
Başlık çevirisi yok
M.EBRU KOLUSAYIN
Yüksek Lisans
Türkçe
1998
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Bilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MEHMET BÜLENT ÖRENCİK
- Dynamic spectrum management using cognitive radio technology
Bilişsel radyo teknolojoisi ile dinamik spektrum yönetimi
MUSTAFA KAAN ERTAN
Yüksek Lisans
İngilizce
2021
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektronik ve Haberleşme Mühendisliği Ana Bilim Dalı
PROF. DR. AHMET HAMDİ KAYRAN
- Novel interference and spectrum aware routing techniques for cognitive radio ad hoc networks
Tasarsız bilişsel radyo ağları için girişim ve spektruma dayalı özgün yönlendirme teknikleri
AHMET ÇAĞATAY TALAY
Doktora
İngilizce
2011
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. DENİZ TURGAY ALTILAR
- İşbirlikçi robotların haptik arayüzlerle teleoperasyonu
Haptic teleoperation of cooperating robots
ÖMER FARUK ARGIN
Doktora
Türkçe
2021
Mekatronik Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ZEKİ YAĞIZ BAYRAKTAROĞLU