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ı
- Tez No: 246609
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2009
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
- Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Sayfa Sayısı: 129
Özet
İ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.
Özet (Çeviri)
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.
Benzer Tezler
- Cloud computing in maritime transport for data collection: Cyber security risk analysis with FMECA method
Deniz taşımacılıgında veri toplama işlemi için bulut bilişim cözümü: FMECA methodu ile siber güvenlik risk analizi
TOPRAK OBA
Yüksek Lisans
İngilizce
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDeniz Ulaştırma Mühendisliği Ana Bilim Dalı
PROF. DR. YASİN ARSLANOĞLU
- Dynamic data replication and distribution in database systems
Veri tabanı sistemlerinde dinamik veri kopyalama ve dağıtımı
SAADI HAMAD THALIJ ALLUHAIBI
Doktora
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYıldız Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
Assoc. Prof. Dr. VELİ HAKKOYMAZ
- A hierarchical key assignment scheme for access control in cloud computing
Bulut bilişimde erişim kontrolü için hiyerarşik anahtar atama şeması
BARIŞ ÇELİKTAŞ
Doktora
İngilizce
2022
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilişim Uygulamaları Ana Bilim Dalı
DOÇ. DR. ENVER ÖZDEMİR
- A contributory study on access control and authentication mechanisms for internet of things
Nesnelerin interneti üzerine giriş kontrol ve kimlik onaylama mekanizmaları üzerine bir çalışma
MANOLYA ATALAY
Yüksek Lisans
İngilizce
2019
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolAkdeniz ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ MURAT AK
- V.42 bis sıkıştırma yönteminin gerçekleşme ve başarım incelenmesi
Implementation of V.42 bis compression procedure and performance results
OSMAN ALİEFENDİOĞLU
Yüksek Lisans
Türkçe
1992
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. A. EMRE HARMANCI