{"id":{"repo_id":"essex","oai_identifier":"oai:repository.essex.ac.uk:22334"},"canonical_url":"https://search.dev.ndltd.org/etd/essex/oai:repository.essex.ac.uk:22334","repository":{"repo_id":"essex","name":"University of Essex","base_url":"https://repository.essex.ac.uk/cgi/oai2"},"display":{"title":"Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Çaylak Kayaturan, Gökçe"],"institution":"University of Essex","degree_name":"phd","degree_level":"doctoral","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2018,"date_issued":"2018-06","date_published":"2018-06","updated_at":"2026-07-24T02:18:21Z","subjects":["QA Mathematics","QA75 Electronic computers. Computer science"],"languages":["en"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":null,"outbound_label":null,"outbound_source":null},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.sponsor","label":"Sponsor","values":["Turkish Ministry of Education"]},{"key":"dc:creator","label":"Author","values":["Çaylak Kayaturan, Gökçe"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2018-06"]},{"key":"dc:date.issued","label":"Date","values":["2018-06"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Mathematical Sciences"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Essex"]},{"key":"dc:relation.isreferencedby","label":"Dc Relation Isreferencedby","values":["https://repository.essex.ac.uk/22334/"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["doctoral"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["phd"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["QA Mathematics","QA75 Electronic computers. Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://repository.essex.ac.uk/22334/1/Gokce%20Caylak%20Kayaturan-repository.pdf"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format","label":"Dc Format","values":["text"]},{"key":"dc:title","label":"Title","values":["Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks"]}]}],"canonical_facts":{"dc:contributor.sponsor":["Turkish Ministry of Education"],"dc:creator":["Çaylak Kayaturan, Gökçe"],"dc:date":["2018-06"],"dc:date.issued":["2018-06"],"dc:description.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."],"dc:format":["text"],"dc:identifier.uri":["https://repository.essex.ac.uk/22334/1/Gokce%20Caylak%20Kayaturan-repository.pdf"],"dc:language":["en"],"dc:publisher.department":["Department of Mathematical Sciences"],"dc:publisher.institution":["University of Essex"],"dc:relation.isreferencedby":["https://repository.essex.ac.uk/22334/"],"dc:subject":["QA Mathematics","QA75 Electronic computers. Computer science"],"dc:title":["Representing shortest paths in graphs using Bloom filters without false positives and applications to routing in computer networks"],"dc:type":["Thesis"],"dc:type.qualificationlevel":["doctoral"],"dc:type.qualificationname":["phd"]},"updated_at":"2026-07-24T02:18:21Z"}