Paper Info
Title
Safe-Time: Distributed Real-Time Monitoring of cKNN in Mobile Peer-to-Peer Networks
Abstract
A continuous k nearest neighbor (cKNN) query is a query that continuously returns a set of k nearest moving objects (mobile hosts) to a given query point. For example, report three nearest moving sensors to a given location continuously. Most existing research efforts focus on centralized solutions. In a mobile peer-to-peer network (M-P2P), a centralized approach incurs expensive communication cost. In this paper, we propose Safe-Time - a distributed solution for cKNN given a stationary query point for M-P2P. The two key features are as follows. 1) Actual execution of a cKNN query is not needed during a safe-time period since the query result is guaranteed to remain the same during this period. 2) Once the safe-time expires, execution of a cKNN query involves only objects in a circular band of width equal to the estimated distance between the kth and the k + 1th nearest neighbors. To further reduce communication cost for dense queries, we introduce Unite-Safe-Time that executes one virtual query derived from nearby queries instead of executing each of them separately. Our simulation result shows that the proposed distributed solutions outperform a centralized solution under a range of conditions. Safe-Time incurs up to 2/3 less communication cost compared to a centralized solution. Unite-Safe-Time shows up to 1/3 less communication cost than Safe-Time in our study.
Year
DOI
Venue
2008
10.1109/MDM.2008.18
MDM
Keywords
Field
DocType
nearby query,cknn query,distributed real-time monitoring,centralized approach,m-p2p,safe-time,stationary query point,mobile hosts,k nearest moving objects,distributed solution,query point,virtual query,dense query,continuous k nearest neighbor,safe-time period,peer-to-peer computing,centralized solution,query result,cmmunication cost,mobile computing,circular band,real-time monitoring,mobile peer-to-peer networks,query processing,security of data,unite-safe-time,indexes,mobile communication,k nearest neighbor,artificial neural networks,nearest neighbor,base stations,p2p,wireless communication
k-nearest neighbors algorithm,Query optimization,Mobile computing,Base station,Peer-to-peer,Computer science,Sargable,Computer network,Artificial neural network,Mobile telephony,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-0-7695-3154-0
5
0.40
References 
Authors
16
3
Name
Order
Citations
PageRank
Kihwan Kim140928.22
Ying Cai293360.43
Wallapak Tavanapong353563.27