Conference Proceedings

Incremental rank updates for moving query points

Lars Kulik, Egemen Tanin, M Raubal (ed.), HJ Miller (ed.), AU Frank (ed.), MF Goodchild (ed.)

GEOGRAPHIC INFORMATION SCIENCE, PROCEEDINGS | SPRINGER-VERLAG BERLIN | Published : 2006

Abstract

The query for retrieving the rank of all neighbors of a moving object at any given time, a continuous rank query, is an important case of continuous nearest neighbor (CNN) queries. An application for ranking queries is given by an ambulance driver who needs to keep track of the closest hospitals at all times. We present a set of incremental algorithms that facilitate efficient rank updates for some or all neighbors of a moving query point. The proposed algorithms allow us not only to maintain the exact rank of all n neighbors at any given time but also to track the rank of a subset of all neighbors. We show that updates for these continuous rank queries can be performed in linear time for ar..

View full abstract