Back to search

Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Sciences

The area code tree for approximate nearest neighbour search in dense point sets

Abstract

dc:description.abstract

Location based Services (LBSs) have become very popular due to the rapid development of wireless technology and mobile devices. A LBS provides results to a user of a mobile device (e.g.smart phone, tablet) based on their location, interests, and the type of query being performed. For example, a user may want to know the location of the closest restaurant to them. Sometimes the user may also be happy with another suggestion that may not be the closest but close enough to satisfy them. This is an example of an approximate nearest neighbour search. In this thesis, we propose a spatial data structure the Area Code Tree which is a trie-type structure. The Area Code Tree stores Points of Interest (POIs) that are represented in area code format. We also present the algorithms for mapping the area code of a POI, inserting and building an Area Code Tree, and approximate nearest neighbour search. Next we evaluate the Area Code Tree for accuracy, tree construction time, and compare its search performance with the Brute Force Method. We find that the average search time for Area Code Tree in locating nearest neighbour is very low and constant regardless of the number of POIs in the index. In addition, the Area Code Tree can achieve up to 60\% accuracy for locating the nearest neighbour in dense point sets. This makes the Area Code tree an excellent candidate for continuous approximate nearest neighbour search for location-based services.

Degree

thesis:*
Level thesis:degree_level
Masters
Grantor dc:publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Sciences
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Rahman, Fatema
Advisor dc:contributor.supervisor
  • Osborn, Wendy

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/4999

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Rahman, Fatema. The area code tree for approximate nearest neighbour search in dense point sets. Masters thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Sciences, 2018. https://hdl.handle.net/10133/4999