Tez No	İndirme	Tez Künye	Durumu
584198		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ı Yazar:GÖKÇE ÇAYLAK KAYATURAN Danışman: DR. ALEXEI VERNITSKI Yer Bilgisi: University of Essex / Yurtdışı Enstitü / Matematik Ana Bilim Dalı / Cebir ve Sayılar Teorisi Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Matematik = Mathematics Dizin:	Onaylandı Doktora İngilizce 2017 178 s.
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. Dierent 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.