A nearest neighbor search method suitable for low dimensions and location-dependent spatial queries in mobile computing

dc.contributor.authorGong, Peng
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorOsborn, Wendy
dc.date.accessioned2016-01-15T23:13:12Z
dc.date.available2016-01-15T23:13:12Z
dc.date.issued2015
dc.degree.levelMastersen_US
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.en_US
dc.embargoNoen_US
dc.identifier.urihttps://hdl.handle.net/10133/3865
dc.language.isoen_CAen_US
dc.proquest.subject0984en_US
dc.proquest.subject0800en_US
dc.proquest.subject0366en_US
dc.proquestyesYesen_US
dc.publisherLethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Scienceen_US
dc.publisher.departmentDepartment of Mathematics and Computer Scienceen_US
dc.publisher.facultyArts and Scienceen_US
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)en_US
dc.subjectnearest neighbor searchen_US
dc.subjecttrieen_US
dc.titleA nearest neighbor search method suitable for low dimensions and location-dependent spatial queries in mobile computingen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
GONG_PENG_MSC_2015.pdf
Size:
608.92 KB
Format:
Adobe Portable Document Format
Description:
Thesis (One file only)
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: