Λεπτομέρειες

ΕίδοςΔημοσίευση
ΚωδικόςTR-2007-10
ΤίτλοςApproximate Order-k Voronoi Cells over Positional Streams
ΣυγγραφέαςΚώστας Πατρούμπας, Θεοφάνης Μηνόγιαννης, Τίμος Σελλής
Έτος2007
Λέξεις κλειδιάApproximation, Data Streams, Nearest Neighbors, Voronoi Cell, Moving Objects
Περίληψη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.
ΚατηγορίαData Streams
ΔημοσίευσηProceedings of 15th ACM International Symposium on Advances in Geographic Information Systems (ACM GIS 2007), Seattle, Washington, USA, November 7-9, 2007
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα