Approximate indexing in road network databases

In this paper, we address approximate indexing for efficient processing of k-nearest neighbor(k-NN) queries in road network databases. Previous methods suffer from either serious performance degradation in query processing or large storage overhead because they did not employ indexing mechanisms based on their network distances. To overcome these drawbacks, we propose a novel method that builds an index on those objects in a road network by approximating their network distances and processes k-NN queries efficiently by using that index. Also, we verify the superiority of the proposed method via extensive experiments using the real-life road network databases. Copyright 2009 ACM