Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks
type: CreativeWork
description: 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. 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 ﬁ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.
abstract: 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. 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 ﬁ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.
author: Çaylak Kayaturan, Gökçe
language: en
keywords: QA Mathematics, QA75 Electronic computers. Computer science
date published: 2018-06
date modified: 2026-07-24T02:18:21Z
provider: University of Essex
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: University of Essex