Implementation of index structures for fuzzy spatial querying

Abstract

öz BELİRSİZ UZAYSAL SORGULAMA İÇİN DİZİN YAPILARI UYGULAMALARI Sözer, Aziz Yüksek Lisans, Bilgisayar Mühendisliği Bölümü Tez Yöneticisi: Prof. Dr. Adnan Yazıcı Kasım 2001, 91 sayfa Son yıllarda veritabanı yönetim sistemleri uzaysal verileri de içerecek şekilde büyümüştür. Bu yeni uygulamalar geleneksel veritabanı teknolojisine göre ciddi zorluklara sahiptir (örneğin, uzaysal bileşenler ve belirsiz özellikler). Uzaysal veri karmaşık ve bir dizi kendine has özelliklere sahiptir. Uzaysal veri tabanı sistemleri (örneğin coğrafık bilgi sistemleri) eğer uzaysal veriler fiziki veri tabanlarında uygun şekilde tutulursa etkili olabilir. Bu nedenle uzaysal ve/veya uzaysal olmayan sorgulama için etkili uzaysal dizinleme teknikleri geliştirmek önemlidir. Bu tezde iki farklı dizin yapısı ile belirsiz uzaysal sorgulama üzerine çalışılmıştır. İlk aşamada çok seviyeli ızgara dosyası (MLGF) üzerinde uzaysal ve/veya uzaysal olmayan sorgulamalar yapılmıştır. İkinci safhada R-tree ve R*-tree dizin yapıları üzerine çalışılmıştır. Karşılaştırmalar yapmak üzere R-tree ve R*-tree yapılan uzaysal olmayan özellikleri tutmak için değiştirilmiştir. Her iki yapı da coğrafik veri kullanılarak karşılaştırılmıştır. Anahtar kelimeler: Uzaysal Veri Tabanı, Çok Seviyeli Izgara Dosyası, R-tree, Coğrafik Bilgi Sistemleri, Belirsiz Uzaysal Sorgulama iv

ABSTRACT IMPLEMENTATION OF INDEX STRUCTURES FOR FUZZY SPATIAL QUERYING Sözer, Aziz MS., Department of Computer Engineering Supervisor: Prof. Dr. Adnan Yazıcı November 2001, 91 pages Over the years database management systems have been enlarged to include spatially referenced data. These new application areas pose serious challenges to the traditional database technology. Spatial data are complex and have a number of unique requirements (i.e. spatial components and uncertain properties). Spatial database systems (e.g., Geographical Information Systems) can be effective if the spatial data are properly handled in physical databases. It's important to develop effective spatial and aspatial indexing techniques to facilitate spatial and/or aspatial querying. In this thesis we deal with fuzzy spatial querying on different index structures. In the first part, we study Multi-level grid file (MLGF) index structure and run fuzzy spatial and/or aspatial queries. Second part deals with R-tree and R*-tree index structures. In order to make some comparisons, we adapted R-tree and R*-tree. We modified R-tree and R*-tree structures to handle aspatial attributes as well. We implemented and compared three index structures with geographic data. Keywords: Spatial database, Multi-level Grid File, R-tree, Geographical Information Systems, Fuzzy Spatial Querying. in