Paper Info
Title
Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space
Abstract
The availability of indoor positioning renders it possible to deploy location-based services in indoor spaces. Many such services will benefit from the efficient support for k nearest neighbor (kNN) queries over large populations of indoor moving objects. However, existing kNN techniques fall short in indoor spaces because these differ from Euclidean and spatial network spaces and because of the limited capabilities of indoor positioning technologies. To contend with indoor settings, we propose the new concept of minimal indoor walking distance (MIWD) along with algorithms and data structures for distance computing and storage; and we differentiate the states of indoor moving objects based on a positioning device deployment graph, utilize these states in effective object indexing structures, and capture the uncertainty of object locations. On these foundations, we study the probabilistic threshold kNN (PTkNN) query. Given a query location q and a probability threshold T, this query returns all subsets of k objects that have probability larger than T of containing the kNN query result of q. We propose a combination of three techniques for processing this query. The first uses the MIWD metric to prune objects that are too far away. The second uses fast probability estimates to prune unqualified objects and candidate result subsets. The third uses efficient probability evaluation for computing the final result on the remaining candidate subsets. An empirical study using both synthetic and real data shows that the techniques are efficient.
Year
DOI
Venue
2010
10.1145/1739041.1739083
EDBT
Keywords
Field
DocType
knn query result,query return,indoor positioning technology,knn technique,minimal indoor walking distance,indoor setting,symbolic indoor space,neighbor query,probabilistic threshold knn,query location q,indoor positioning,indoor space,location based service,empirical study,uncertainty,k nearest neighbor
k-nearest neighbors algorithm,Data mining,Graph,Data structure,Spatial network,Computer science,Search engine indexing,Theoretical computer science,Euclidean geometry,Probabilistic logic
Conference
Citations 
PageRank 
References 
45
1.57
24
Authors
3
Name
Order
Citations
PageRank
Bin Yang170634.93
Hua Lu2138083.74
Christian S. Jensen3106511129.45