  We study the problem of processing continuous k nearest neighbor (CkNN)
queries over moving objects on road networks, which is an essential operation
in a variety of applications. We are particularly concerned with scenarios
where the object densities in different parts of the road network evolve over
time as the objects move. Existing methods on CkNN query processing are
ill-suited for such scenarios as they utilize index structures with fixed
granularities and are thus unable to keep up with the evolving object
densities. In this paper, we directly address this problem and propose an
object density aware index structure called ODIN that is an elastic tree built
on a hierarchical partitioning of the road network. It is equipped with the
unique capability of dynamically folding/unfolding its nodes, thereby adapting
to varying object densities. We further present the ODIN-KNN-Init and
ODIN-KNN-Inc algorithms for the initial identification of the kNNs and the
incremental update of query result as objects move. Thorough experiments on
both real and synthetic datasets confirm the superiority of our proposal over
several baseline methods.
