The area code tree for approximate nearest neighbour search in dense point sets
Date
2018-01-14
Authors
Rahman, Fatema
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Sciences
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.
Description
Keywords
Approximation algorithms , Cell phones , Location-based services , wireless communication systems