Approximate order-k Voronoi cells over positional streams
Kostas Patroumpas, Theofanis Minogiannis, Timos Sellis · 2007
Handling streams of positional updates from numerous moving ob-jects has become a challenging task for many monitoring applica-tions. Several algorithms have been recently proposed for provid-ing 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 ap-proximate 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 neigh-bors for any query point found inside the constructed cell. We fur-ther 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. Ex-tensive experimental analysis over synthetic datasets confirms the robustness and scalability of this approach offering near real-time cell maintenance with acceptable error margins.