Degree Type

Thesis

Date of Award

2008

Degree Name

Master of Science

Department

Computer Science

First Advisor

Ying Cai

Second Advisor

Wensheng Zhang

Third Advisor

Daji Qiao

Abstract

A continuous k nearest neighbor (CKNN) query retrieves the set of k mobile nodes that are nearest to a query point, and provides real-time updates whenever this set of nodes changes. A CKNN query can be either stationary or mobile, depending on the mobility of its query point. Efficient processing of CKNN queries is essential to many applications, yet most existing techniques assume a centralized system, where one or more central servers are used for query management. In this thesis, we assume a fully distributed mobile peer-to-peer system, where mobile nodes are the only computing devices, and present a unified platform for efficient processing of both stationary and mobile CKNN queries. For each query, our technique computes a set of safe boundaries and lets mobile nodes monitor their movement with respect to these boundaries. We show that the result of a query does not change unless a node crosses over a safe boundary. As such, our technique requires a query to be re-evaluated only when there is a crossing event, thus minimizing the cost of query evaluation. For performance study, we model the communication cost incurred in query processing with a detailed mathematical analysis and verify its accuracy using simulation. Our extensive study shows that the proposed technique is able to provide real-time and accurate query results with a reasonable cost.

DOI

https://doi.org/10.31274/rtd-180813-16584

Publisher

Digital Repository @ Iowa State University, http://lib.dr.iastate.edu/

Copyright Owner

Patricio A. Galdames S

Language

en

Proquest ID

AAI1453176

OCLC Number

243468371

ISBN

9780549544050

File Format

application/pdf

File Size

54 pages

Share

COinS