direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

Bachelor Thesis:Implementation of a Space-efficient Data Structure for Representing Large Geographic Location Data Sets in Web Applications

Implementation of a Space-efficient Data Structure for Representing Large Geographic Location Data Sets in Web Applications


To come up with a reasonable result set, traditional location based services require the full disclosure of all locations visited by a user, resulting in an easy traceability. New approaches have to be discovered as privacy-issues become more and more of a concern. Additionally size can be an issue, when data sets grow very large, making it unfavorable to forward them with every request. The Geocookie is a recently proposed data structure that aims to store geographical locations in beneficial ways. This is achieved through the combination of a geocode system called the Geohash, which was invented by Gustavo Niemeyer in 2008 and a space-efficient probabilistic data structure called Bloom filter, which was proposed by Burton Howard Bloom in 1970. The Geohash hereby maps the traditional coordinates of latitude and longitude to a one dimensional hash closely following the methodology of space-filling curves, of which the first was discovered by Peano in 1890. Its accuracy is easily controllable by the user. A bloom filter is used to save representations of this encoded geographical data in a bit vector with the help of a number of independent hash functions. These map an infinite domain into a finite range and this can cause certain objects to map to the same positions in the vector, causing a collision. Therefore a query for coverage has two potential answers: 1) the object is definitely not a member, or 2) the objects is probably a member of the set. The Geocookie consequently puts the informational control back into the users hands, offering plausible deniability and accuracy control of locational data, while allowing third parties like location based services to work properly via one-way checks.


Supervisor: Peter Ruppel

Type:  Bachelor Thesis

Duration: 4 months


TU Berlin - Service-centric Networking - TEL 19
Ernst-Reuter-Platz 7
10587 Berlin, Germany
Phone: +49 30 8353 58811
Fax: +49 30 8353 58409
Contact [2]

------ Links: ------

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

Copyright TU Berlin 2008