logo
CanyamAI summaries for academic research
language
MobileMobile
  • Phone FeatureWeChat Mini Program
EnglishEnglish
noticeNotice
BlogBlog
delete
arrow
Return

Efficient Probabilistic K-NN Computation in Uncertain Sensor Networks

delete2021-07-01
delete2
PRE
AI
X
Xiaofeng Ding
J
Jing Liu
P
Pan Zhou *
DOI：10.1109/TNSE.2021.3099864delete
deleteOriginal
deleteOriginal request for help
deleteShare
deleteSave
Abstract

Abstract

En 中文
Uncertain data management has recently attracted much research interest in the networking community and database community, as in many emerging applications, e.g., sensor data monitoring, location-based services and vehicle tracking, where data are inherently uncertain due to measurement errors, update delays etc. The probabilistic k nearest neighbor (k-PNN) query returns k objects with the highest probability of being the k-th nearest neighbor from a given query point Q. However, compared to the traditional k-NN over precise data, the computation cost of k-PNN is rather expensive due to the costly numerical integration or Monte-Carlo approach it adopts, which raises a challenge in answering k-PNN in very large uncertain sensor networks. To address this challenge, we propose an efficient strategy for processing k-PNN queries. Specifically, we introduce two effective pruning methods, spatial pruning and probabilistic pruning, to speed up the query procedure by reducing the search space. The spatial pruning is based on the bounding region of the k-th nearest neighbor, while the probabilistic pruning is based on the lower and upper probability bounds of each k-NN candidate object after spatial pruning. Extensive experiments have been implemented to demonstrate the efficiency and effectiveness of our proposed method under various settings, in terms of both wall clock time and the number of candidate objects to be evaluated.
Keywords:
Probabilistic logic
Uncertainty
Spatial databases
Indexes
Semantics
Query processing
Probability density function
Sensor networks
uncertain data
probabilistic queries
k nearest-neighbor queries
AI Summary

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.

Journal

I
IEEE Transactions on Network Science and Engineering
IF:
7.9
Papers:
2.5K
Citations:
10.0K

Organization

No organization information available