Skip to main content
Log in

Popularity-aware collective keyword queries in road networks

  • Published:
GeoInformatica Aims and scope Submit manuscript

Abstract

This paper addresses a popularity-aware collective keyword (PAC-K) query in road networks. Given a road network with POIs (Points of Interest), which is modeled as a road network graph, where each node locating in a two-dimensional space represents a road intersection or a POI, and each edge with weight represents a road segment, the PACK query aims to find a group of popular POIs (i.e., a popular region) that cover the query’s keywords and satisfy the distance requirements from each node to the query node and between each pair of nodes, such that the sum of rating scores over these nodes for the query keywords is maximized. We show the problem of answering the PACK query is NP-Hard. To solve this problem, we present exact and heuristic solutions on small and large road networks, respectively. In particular, to improve query performance, we propose a rating score scaling technique to reduce the search space and a redundant computation reducing technique to reduce the excessive redundant computations in query processing. Extensive performance studies using two real datasets confirm the efficiency, accuracy, and scalability of the proposed solutions.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18
Fig. 19
Fig. 20
Fig. 21
Fig. 22
Fig. 23
Fig. 24

Similar content being viewed by others

Notes

  1. http://map.baidu.com/

  2. https://maps.google.com/

  3. http://www.yelp.com

  4. https://www.tripadvisor.com/

  5. https://www.flickr.com/

  6. http://www.dis.uniroma1.it/challenge9/download.shtml

  7. http://glaros.dtc.umn.edu/gkhome/metis/metis/overview

References

  1. Cao X, Chen L, Cong G, Xiao X (2012) Keyword-aware optimal route search. VLDB 5(11):1136–1147

    Google Scholar 

  2. Cao X, Cong G, Guo T, Jensen CS, Ooi BC (2015) Efficient processing of spatial group keyword queries. ACM Trans Database Syst 40(2):13

    Article  Google Scholar 

  3. Cao X, Cong G, Jensen CS, Ooi BC (2011) Collective spatial keyword querying SIGMOD, pp 373–384

  4. Cao X, Cong G, Jensen CS, Yiu ML (2014) Retrieving regions of interest for user exploration. VLDB 7(9):733–744

    Google Scholar 

  5. Chen G, Wu S, Zhou J, Tung A (2014) Automatic itinerary planning for traveling services. TKDE 26(3):514–527

    Google Scholar 

  6. Christoforaki M, He J, Dimopoulos C, Markowetz A, Suel T (2011) Text vs. space: efficient geo-search query processing CIKM, pp 423–432

  7. Cong G, Jensen CS, Wu D (2009) Efficient retrieval of the top-k most relevant spatial web objects. VLDB 2(1):337–348

    Google Scholar 

  8. Corwin E, Logar A (2004) Sorting in linear time-variations on the bucket sort. Journal of computing sciences in colleges

  9. De Felipe I, Hristidis V, Rishe N (2008) Keyword search on spatial databases ICDE, pp 656–665

  10. Gao Y, Liu Q, Miao X, Yang J (2016) Reverse k-nearest neighbor search in the presence of obstacles. Inf Sci 330:274–292

    Article  Google Scholar 

  11. Gao Y, Zhao J, Zheng B, Chen G (2016) Efficient collective spatial keyword query processing on road networks. IEEE Trans Intell Transp Syst 17(2):469–480

    Article  Google Scholar 

  12. Gao Y, Zheng B, Chen G, Li Q, Guo X (2011) Continuous visible nearest neighbor query processing in spatial databases. VLDB J 20(3):371–396

    Article  Google Scholar 

  13. Gionis A, Lappas T, Pelechrinis K, Terzi E (2014) Customized tour recommendations in urban areas WSDM, pp 313–322

  14. Guo T, Cao X, Cong G (2015) Efficient algorithms for answering the m-closest keywords query SIGMOD, pp 405–418

  15. He H, Wang H, Yang J, Yu PS (2007) Blinks: ranked keyword searches on graphs SIGMOD, pp 305–316

  16. Kargar M, An A (2011) Keyword search in graphs: Finding r-cliques. VLDB 4(10):681–692

    Google Scholar 

  17. Kurashima T, Iwata T, Irie G, Fujimura K (2010) Travel route recommendation using geotags in photo sharing sites CIKM, pp 579–588

  18. Li G, Feng J, Xu J (2012) Desks: Direction-aware spatial keyword search ICDE, pp 474–485

  19. Long C, Wong RC-W, Wang K, Fu AW-C (2013) Collective spatial keyword queries: a distance owner-driven approach SIGMOD, pp 689–700

  20. Lu J, Lu Y, Cong G (2011) Reverse spatial and textual k nearest neighbor search SIGMOD, pp 349–360

  21. Luo S, Luo Y, Zhou S, Cong G, Guan J, Yong Z (2014) Distributed spatial keyword querying on road networks EDBT, pp 235–246

  22. Qiao M, Qin L, Cheng H, Yu JX, Tian W (2013) Top-k nearest keyword search on large graphs. VLDB 6(10):901–912

    Google Scholar 

  23. Rocha-Junior JB, Nørvåg K (2012) Top-k spatial keyword queries on road networks EDBT, pp 168–179

  24. Floyd RW, 97 Algorithm (1962) Shortest path Communications of the ACM

  25. Shang S, Ding R, Yuan B, Xie K, Zheng K, Kalnis P (2012) User oriented trajectory search for trip recommendation EDBT, pp 156–167

  26. Yao B, Tang M, Li F (2011) Multi-approximate-keyword routing in gis data ACM SIGSPATIAL GIS, pp 201–210

  27. Zhang C, Zhang Y, Zhang W (2014) Diversified spatial keyword search on road networks EDBT, pp 367–378

  28. Zhang D, Chee YM, Mondal A, Tung A, Kitsuregawa M (2009) Keyword search in spatial databases: Towards searching by document ICDE, pp 688–699

  29. Zhang D, Tan K-L, Tung AK (2013) Scalable top-k spatial keyword search EDBT/ICDT, pp 359–370

  30. Zhang J, Meng X, Zhou X, Liu D (2012) Co-spatial searcher: Efficient tag-based collaborative spatial search on geo-social network DASFAA, pp 560–575

  31. Zheng K, Shang S, Yuan NJ, Yang Y (2013) Towards efficient search for activity trajectories ICDE, pp 230–241

  32. Zhu AD, Ma H, Xiao X, Luo S, Tang Y, Zhou S (2013) Shortest path and distance queries on road networks: towards bridging theory and practice SIGMOD, pp 857–868

Download references

Acknowledgments

We thank the reviewers for their valuable comments which significantly improved this paper. The work was supported in part by the following funding agencies of China: National Natural Science Foundation under grant 61502047.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Sen Su.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhao, S., Cheng, X., Su, S. et al. Popularity-aware collective keyword queries in road networks. Geoinformatica 21, 485–518 (2017). https://doi.org/10.1007/s10707-017-0299-9

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10707-017-0299-9

Keywords

Navigation