Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
A nearest neighbor search method suitable for low dimensions and location-dependent spatial queries in mobile computing
Abstract
dc:description.abstractThis thesis proposes a k-nearest-neighbor search method inspired by the grid space partitioning and the compact trie tree structure. A detailed implementation based on the Best-First-Nearest-Neighbor-Search scheme is presented and illustrated with sample data. Then k-nearest-neighbor search performance comparison is carried out among the proposed compact-trie-based method, the brute-force method, and the k-d tree based method, with one million two-dimensional spatial points and k up to 1000. The result of the comparison shows that the proposed method can perform up to 300 times better than the other two methods when k is small, suggesting that the proposed method might be suitable for low dimensions and location-dependent spatial queries in mobile computing.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Grantor dc:publisher
- Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science
- Year dc:date.issued
- 2015
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Gong, Peng
- University of Lethbridge. Faculty of Arts and Science
- Advisor dc:contributor.supervisor
-
- Osborn, Wendy
Subjects
dc:subject × 2Rights
- Language dc:language.iso
- en_CA
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10133/3865