TU Berlin

Service-centric NetworkingMälzer, P. (2014). Implementation of a Space-efficient Data Structure for Representing Large Geographic Location Data Sets in Web Applications. Bachelor Thesis, Technische Universität Berlin

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

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

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

Description:

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

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe