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

Simple item page
dc.contributor.authorRahman, Fatema
dc.contributor.supervisorOsborn, Wendy
dc.date.accessioned2018-01-19T17:13:00Z
dc.date.available2018-01-19T17:13:00Z
dc.date.issued2018-01-14
dc.degree.levelMastersen_US
dc.description.abstractLocation 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.en_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/4999
dc.language.isoen_USen_US
dc.proquest.subject0708en_US
dc.proquest.subject0464en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Sciencesen_US
dc.publisher.departmentDepartment of Mathematics & Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectApproximation algorithmsen_US
dc.subjectCell phonesen_US
dc.subjectLocation-based servicesen_US
dc.subjectwireless communication systemsen_US
dc.titleThe area code tree for approximate nearest neighbour search in dense point setsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Rahman_Fatema_MSC_2017.pdf
Size:
1.1 MB
Format:
Adobe Portable Document Format
Description:
Masters Thesis Project
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
3.25 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses