K-SPIN: efficiently processing spatial keyword queries on road networks

Tenindra Abeywickrama, Muhammad Aamir Cheema, Arijit Khan

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)


A significant proportion of all search volume consists of local searches. As a result, search engines must be capable of finding relevant results combining both spatial proximity and textual relevance with high query throughput. We observe that existing techniques answering these spatial keyword queries use keyword aggregated indexing, which has several disadvantages on road networks. We propose K-SPIN, a versatile framework that instead uses keyword separated indexing to delay and avoid expensive operations. At first glance, this strategy appears to have impractical pre-processing costs. However, by exploiting several useful observations, we make the indexing cost not only viable but also light-weight. For example, we propose a novel ρ-Approximate Network Voronoi Diagram (NVD) with one order of magnitude less space cost than exact NVDs. By carefully exploiting features of the K-SPIN framework, our query algorithms are up to two orders of magnitude more efficient than the state-of-the-art as shown in our experimental investigation on various queries, parameter settings, and real road network and keyword datasets.

Original languageEnglish
Pages (from-to)983-997
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number5
Publication statusPublished - 1 May 2020


  • Network Voronoi diagrams
  • Points of interest search
  • Road networks
  • Spatio-textual queries

Cite this