Probabilistic threshold k nearest neighbor queries over moving objects in symbolic indoor space

Bin Yang, Hua Lu, Christian S. Jensen

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningpeer review


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
TitelAdvances in Database Technology - EDBT 2010 : 13th International Conference on Extending Database Technology, Lausanne, Switzerland, March 22-26, 2010, Proceedings
RedaktørerIoana Manolescu, Stefano Spaccapietra, Jens Teubner, Masaru Kitsuregawa, Alain Léger, Felix Naumann, Anastasia Ailamaki, Fatma Özcan
Antal sider12
ForlagAssociation for Computing Machinery
ISBN (Trykt)78-1-60558-945-9
StatusUdgivet - 2010
Udgivet eksterntJa
Begivenhed13th International Conference on Extending Database Technology - Lausanne, Schweiz
Varighed: 22 mar. 201026 mar. 2010
Konferencens nummer: 13


Konference13th International Conference on Extending Database Technology
NavnACM International Conference Proceeding Series

Citer dette