Talk: [Overview] [Papers and Talks] [Source Code] [Data set] [Contacts]
For GIS data situated on a road network, shortest path search is a basic operation. In practice, however, users are often interested at routing when certain constraints on the textual information have been also incorporated. This work complements the standard shortest path search with multiple keywords and an approximate string similarity function, where the goal is to find the shortest path that passes through at least one matching object per keyword; we dub this problem the multi-approximate-keyword routing (makr) query. We present both exact and approximate solutions. When the number ĸ of query keywords is small (e.g.,ĸ<= 6), the exact solution works efficiently. However, when ĸ increases, it becomes increasingly expensive (especially on large GIS data). In this case, our approximate methods achieve superb query efficiency, excellent scalability, and high approximation quality, as indicated in our extensive experiments on large, real datasets (up to 2 million points on road networks with hundreds of thousands of nodes and edges). We also prove that one approximate method has a ĸ-approximation in the worst case.
1. Multi-Approximate-Keyword Routing in GIS Data,
Full version:
Talk:
Important Notice
Please cite our paper if you use this library for your work. Thanks!
If you find any bugs or any suggestions/comments, we are very happy to hear from you!
Library Description
The library is developed in GNU C++. For installation and usage, please refer to the README file.
Downloads
Multi-Approximate-Keyword Routing in GIS Data Library.
We have generated and experimented with the data sets described in the paper. For real data sets, please follow the description in our paper. You can also find the test data set in the library.
