Research Repository

Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks

Çaylak Kayaturan, Gökçe (2018) Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks. PhD thesis, University of Essex.

[img]
Preview
Text
Gokce Caylak Kayaturan-repository.pdf

Download (8MB) | Preview

Abstract

A Bloom filter is data structure for representing sets in a compressed form, which has many applications. Bloom filters save time and space, but produce errors known as false positives. In this thesis, a new approach is suggested. Instead of choosing labels for edges in graphs at random (as is done in the standard Bloom filter 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.

Item Type: Thesis (PhD)
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Mathematical Sciences, Department of
Depositing User: Gokce Caylak Kayaturan
Date Deposited: 29 Jun 2018 09:32
Last Modified: 29 Jun 2018 09:32
URI: http://repository.essex.ac.uk/id/eprint/22334

Actions (login required)

View Item View Item