Representing shortest paths in graphs using bloom filters without false positives and applications to routing in computer networ
Yanlış Pozitif İçermeyen Bloom Filtrelerini Kullanarak En Kısa Yolları Graflarda Temsil Etme ve Bilgisayar Ağlarında Yönlendirme Uygulamaları
- Tez No: 584198
- Danışmanlar: DR. ALEXEI VERNITSKI
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Matematik, Computer Engineering and Computer Science and Control, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2017
- Dil: İngilizce
- Üniversite: University of Essex
- Enstitü: Yurtdışı Enstitü
- Ana Bilim Dalı: Matematik Ana Bilim Dalı
- Bilim Dalı: Cebir ve Sayılar Teorisi Bilim Dalı
- Sayfa Sayısı: 178
Özet
Özet yok.
Özet (Çeviri)
A Bloom lter is data structure for representing sets in a compressed form, which has many applications. Bloom lters save time and space, but produce errors known as false positives. Recently it has been suggested that Bloom lters can be used for encoding paths in graphs, for the purpose of delivering messages in computer networks. False positives mean that a message will be delivered not only to its destination, but also to some nodes to which it should not have been delivered. Some ways of reducing the probability of such errors have been discussed in the literature. In this thesis, a new approach is suggested. Instead of choosing labels for edges at random (as is done in the standard Bloom lter approach), labels for edges are chosen based on the graph and the position of an edge in the graph. It is shown that under some assumptions (the graph is known, and only shortest paths are encoded), there will be no false positives leading to a message being delivered to a wrong node. Chapter 1 introduces the routing scenario, the Standard Bloom Filters and the encoding methods that are investigated in the following chapters. Di erent types of assumptions concerning the graphs are applied in further chapters. Shortest paths in rectangular grids are encoded in Chapter 2; then king's graphs, hexagonal grids and triangular grids are studied in Chapters 3; 4 and 5, respectively. Another realistic networks is considered in Chapter 6. Finally, a way to generalise these encoding methods to arbitrary graphs is discussed in Chapter 7, which concludes the thesis.
Benzer Tezler
- Parallel bio-inspired single source shortest path algorithms
Paralel biyolojik tabanlı tek kaynaklı en kısa yol algoritmaları
HİLAL ARSLAN
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. MURAT MANGUOĞLU
- Durağan olmayan kanallarda uyarlamalı hata kontrol yöntemleri
Adaptive coding schemes for time-varying channels
ERSİN ERGEZER
Yüksek Lisans
Türkçe
1994
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiDOÇ.DR. H. ÜMİT AYGÖLÜ
- Verex: yapay zeka yaklaşımına dayalı bir tıbbi teşhis programı
Verex: a medical diagnosis program based on artificial itelligence approach (VERtigo EXpert)
MURAT HANEF
Yüksek Lisans
Türkçe
1991
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiDOÇ.DR. MEHMET KORÜREK
- Dinamik ortamlar için yeni bir gerçek zamanlı evrimsel seyrüsefer planlama ve güdümleme sistemi
A new real time evolutionary navigation planning and guidance system for dynamic environments
FERHAT UÇAN
Doktora
Türkçe
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. DENİZ TURGAY ALTILAR
- İki boyutlu uzayda evrişimsel sinir ağları ile iç mekân rota planlama
Indoor route planning with convolutional neural networks in two-dimensional space
AYŞEGÜL KÜBRA KUZUCU
Yüksek Lisans
Türkçe
2024
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolSivas Cumhuriyet ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
DOÇ. DR. AHMET GÜRKAN YÜKSEK