Tez No	İndirme	Tez Künye	Durumu
246609		Storage and access schemes for aggregate query processing on road networks / Yol ağları üzerindeki topak sorgu işleme için depolama ve erişim planları Yazar:ENGİN DEMİR Danışman: PROF. DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Bölümü / Bilgisayar Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora İngilizce 2009 129 s.
İyi bilinen örnek bir uzamsal ağ olan yol ağları, bölge bazlı servisler, akıllı yolculuk sistemleri, araç telematikleri, ve bölgeye duyarlı reklamcılık gibi coğrafi bilgi sistemi uygulamalarının temel bir parçasını oluşturmaktadır. Uygulamada, yol ağ verileri geçici belleğe sığamayacak kadar büyüktür. Hem çeşitli uzamsal ve uzamsal olmayan özellikler, hem de ilgi çekici noktalar kavşak ve yollarla ilişkilendirildiğinden, verinin oldukça büyük bir parçası ikincil bellekte saklanmalıdır. Ağ sorgusu işlemede, veri erişimi sırasındaki uzamsal tutarlılık zamansal tutarlılığa neden olmaktadır; böylece, bağlı kavşaklara neredeyse eşzamanlı erişilmektedirler. Bu gerçeği gözönünde bulundurarak, bağlı kavşakların verilerini aynı disk bölümleri içerine yerleştirilmesi mantıklı görünmektedir ki veriler daha az sayıda disk erişimi ile getirilebilsin. Şu andaki verileri disk bölümlerine kümeleyen çizge modelinin ardıl getirme operasyonlarının disk erişim maliyetini doğru yakalamadığını gösteriyoruz. Topak sorgu işleme sırasındaki disk erişimini en aza indirmek için sorgu işlemede uzamsal ve zamansal tutarlılığı sorgu kayıtlarını kullanarak doğru kapsayan hiperçizge bölümlemeye dayalı kümeleme modelleri öneriyoruz. Yol ağları için yola dayalı depolama planınını yaygın kullanılan kavşağa dayalı depolama planına alternatif olarak tanıtıyoruz. Ağ sorgularında getirilecek aday ardılları sorgu işleme sırasında azaltacak yeni bir ardıl getirme işlemi olarak Değerlendirilmemiş-Ardılları-Getir'i sunuyoruz. İki değişik Değerlendirilmemiş-Ardılları-Getir işlem örneğini inceliyoruz: İşlenmemiş-Ardılları-Getir işlemi tipik olarak Dijkstra'nın tek başlangıç kısayol çözüm yolunda ve Görülmemiş-Ardılları-Getir işlemi tipik olarak atrımlı ağ genişleme taslağında ortaya çıkıyor. Benzetim sonuçları kümeleyen hiperçizge modellerini kullanan depolama ve erişim planlarımızın topak sorgu işleme sırasındaki disk erişim sayısını azaltmakta oldukça etkili olduğunu göstermektedir.
A well-known example of spatial networks is road networks, which form an integral part of many geographic information system applications, such as location-based services, intelligent traveling systems, vehicle telematics, and location-aware advertising. In practice, road network data is too large to fit into the volatile memory. A considerable portion of the data must be stored on the secondary storage since several spatial and non-spatial attributes as well as points-of-interest data are associated with junctions and links. In network query processing, the spatial coherency that exists in accessing data leads to a temporal coherency; in this way, connected junctions are accessed almost concurrently. Taking this fact into consideration, it seems reasonable to place the data associated with connected junctions in the same disk pages so that the data can be fetched to the memory with fewer disk accesses. We show that the state-of-the-art clustering graph model for allocation of data to disk pages is not able to correctly capture the disk access cost of successor retrieval operations. We propose clustering models based on hypergraph partitioning, which correctly encapsulate the spatial and temporal coherency in query processing via the utilization of query logs in order to minimize the number of disk accesses during aggregate query processing. We introduce the link-based storage scheme for road networks as an alternative to the widely used junction-based storage scheme. We present Get-Unevaluated-Successors (GUS) as a new successor retrieval operation for network queries, where the candidate successors to be retrieved are pruned during processing a query. We investigate two different instances of GUS operation: the Get-unProcessed-Successors operation typically arises in Dijkstra's single source shortest path algorithm, and the Get-unVisited-Successors operation typically arises in the incremental network expansion framework. The simulation results show that our storage and access schemes utilizing the proposed clustering hypergraph models are quite effective in reducing the number of disk accesses during aggregate query processing.