Approximate order-k Voronoi cells over positional streams

Patroumpas, K, Minogiannis, T and Sellis, T 2007, 'Approximate order-k Voronoi cells over positional streams', in Proceedings of the 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007), Seattle, USA, 7-9 November 2007, pp. 276-283.


Document type: Conference Paper
Collection: Conference Papers

Title Approximate order-k Voronoi cells over positional streams
Author(s) Patroumpas, K
Minogiannis, T
Sellis, T
Year 2007
Conference name Proceedings of the 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007)
Conference location Seattle, USA
Conference dates 7-9 November 2007
Proceedings title Proceedings of the 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007)
Publisher ACM
Place of publication USA
Start page 276
End page 283
Total pages 8
Abstract Handling streams of positional updates from numerous moving objects has become a challenging task for many monitoring applications. Several algorithms have been recently proposed for providing exact answers particularly to continuous range and k-nearest neighbor queries against current object positions. In this work, we introduce a processing technique for efficiently maintaining an approximate order-k Voronoi cell around a certain point of interest when all objects continuously change their locations. This heuristic can easily provide a fairly reliable estimate of the k-nearest neighbors for any query point found inside the constructed cell. We further extend our method to handle positional updates that are not received concurrently for all objects, but instead remain valid for a specific time interval according to a sliding window model. Extensive experimental analysis over synthetic datasets confirms the robustness and scalability of this approach offering near real-time cell maintenance with acceptable error margins.
Subjects Database Management
Keyword(s) approximation
data streams
moving objects
nearest neighbors
Voronoi cell
DOI - identifier 10.1145/1341012.1341059
Copyright notice © ACM
ISBN 9781595939142
Versions
Version Filter Type
Citation counts: Scopus Citation Count Cited 5 times in Scopus Article | Citations
Altmetric details:
Access Statistics: 120 Abstract Views  -  Detailed Statistics
Created: Tue, 19 Feb 2013, 12:43:00 EST by Catalyst Administrator
© 2014 RMIT Research Repository • Powered by Fez SoftwareContact us