dc.contributor.supervisor |
Osborn, Wendy |
|
dc.contributor.author |
Gong, Peng |
|
dc.contributor.author |
University of Lethbridge. Faculty of Arts and Science |
|
dc.date.accessioned |
2016-01-15T23:13:12Z |
|
dc.date.available |
2016-01-15T23:13:12Z |
|
dc.date.issued |
2015 |
|
dc.identifier.uri |
https://hdl.handle.net/10133/3865 |
|
dc.description.abstract |
This 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. |
en_US |
dc.language.iso |
en_CA |
en_US |
dc.publisher |
Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science |
en_US |
dc.relation.ispartofseries |
Thesis (University of Lethbridge. Faculty of Arts and Science) |
en_US |
dc.subject |
nearest neighbor search |
en_US |
dc.subject |
trie |
en_US |
dc.title |
A nearest neighbor search method suitable for low dimensions and location-dependent spatial queries in mobile computing |
en_US |
dc.type |
Thesis |
en_US |
dc.publisher.faculty |
Arts and Science |
en_US |
dc.publisher.department |
Department of Mathematics and Computer Science |
en_US |
dc.degree.level |
Masters |
en_US |
dc.proquest.subject |
0984 |
en_US |
dc.proquest.subject |
0800 |
en_US |
dc.proquest.subject |
0366 |
en_US |
dc.proquestyes |
Yes |
en_US |
dc.embargo |
No |
en_US |