K-SPIN: efficiently processing spatial keyword queries on road networks (Extended Abstract)

Tenindra Abeywickrama, Muhammad Aamir Cheema, Arijit Khan

Research output: Chapter in Book/Report/Conference proceedingConference PaperOther


Given the prevalence and volume of local search queries, today's search engines are required to find results by both spatial proximity and textual relevance at high query throughput. Existing techniques to answer such spatial keyword queries employ a keyword aggregation strategy that suffers from certain drawbacks when applied to road networks. Instead, we propose the K-SPIN framework, which uses an alternative keyword separation strategy that is more suitable on road networks. While this strategy was previously thought to entail prohibitive pre-processing costs, we further propose novel techniques to make our framework viable and even light-weight. Thorough experimentation shows that K-SPIN outperforms the state-of-the-art by up to two orders of magnitude on a wide range of settings and real-world datasets.

Original languageEnglish
Title of host publicationProceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
EditorsDimitrios Gunopulos, Murat Kantarcioglu, S. Sudarshan
Place of PublicationPiscataway NJ USA
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages2
ISBN (Electronic)9781728129037
ISBN (Print)9781728129044
Publication statusPublished - 2020
EventIEEE International Conference on Data Engineering 2020 - Online, Virtual, Dallas, United States of America
Duration: 20 Apr 202024 Apr 2020
Conference number: 36th
https://ieeexplore.ieee.org/xpl/conhome/9093725/proceeding (Proceedings)
https://www.utdallas.edu/icde/ (Website)

Publication series

NameProceedings - International Conference on Data Engineering
PublisherThe Institute of Electrical and Electronics Engineers, Inc.
ISSN (Print)1084-4627
ISSN (Electronic)2375-026X


ConferenceIEEE International Conference on Data Engineering 2020
Abbreviated titleICDE 2020
Country/TerritoryUnited States of America
Internet address


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

Cite this