Back to search

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.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.

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 × 2

Rights

Language dc:language.iso
en_CA

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10133/3865

Chain of custody

source
Harvested from
University of Lethbridge
Base URL
opus.uleth.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gong, Peng; University of Lethbridge. Faculty of Arts and Science. A nearest neighbor search method suitable for low dimensions and location-dependent spatial queries in mobile computing. Masters thesis, Lethbridge, Alta : University of Lethbridge, Dept. of Mathematics and Computer Science, 2015. https://hdl.handle.net/10133/3865