Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
GeoInformatica
Published in: GeoInformatica 1/2022

12-11-2021

Reverse keyword-based location search on road networks

Authors: Zijun Chen, Xin Wang, Wenyuan Liu

Published in: GeoInformatica | Issue 1/2022

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Reverse top-k keyword-based location query (RTkKL), aims to find the maximum spatial region such that the query object is contained in the result of any top-k spatial keyword query with users’ queried keywords and any location in the region as arguments. Existing efforts on RTkKL find the objects in the Euclidean space. In this paper, we study the problem of reverse top-k keyword-based location query on road networks. We propose two methods. One is based on mark vertex, and the other is based on bisector. For the mark vertex based method, we identify the mark vertex according to the definition of RTkKL on road networks. Based on the mark vertex, we will get the mark segments in the result. For the bisector-based method, we find the border points for the query q and some objects. With Dijkstra algorithm, we start from the query point q. For each closed edge, whose two adjacent vertices have been extracted from the min heap, we would search the border points on the edge, and count the border points for the adjacent vertex. For each method, we propose effective pruning strategy to reduce the search range and computation cost. Finally, experiments demonstrate the efficiency of the proposed algorithm.
previous article A survey of location-based social networks: problems, methods, and future research directions
next article Temporal aggregation bias and Gerrymandering urban time series

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Attique M, Afzal M, Ali F, Mehmood I, Ijaz MF, Cho H-J (2020) Geo-social top-k and skyline keyword queries on road networks. Sensors 20(3):798CrossRef
2.
Benetis R, Jensen C S, Karčiauskas G, Šaltenis S (2002) Nearest neighbor and reverse nearest neighbor queries for moving objects. In: Proceedings of the international database engineering & applications symposium, Edmonton, Canada, pp 44–53
3.
Borutta F, Nascimento M A, Niedermayer J, Kröger P (2014) Monochromatic RkNN queries in time-dependent road networks. In: Proceedings of the third ACM SIGSPATIAL international workshop on Mobile geographic information systems, Dallas/Fort Worth, TX, USA, pp 26–33
4.
Cary A, Wolfson O, Rishe N (2010) Efficient and scalable method for processing top-k spatial Boolean queries. In: Proceedings of the 22nd international conference on scientific and statistical database management, Heidelberg, Germany, pp 87–95
5.
Cheema M A, Lin X, Zhang W, Zhang Y (2011) Influence zone: efficiently processing reverse k nearest neighbors queries. In: Proceedings of the 27th international conference on data engineering, Hannover, Germany, pp 577–588
6.
Choudhury FM, Culpepper JS, Sellis T, Cao X (2016) Maximizing bichromatic reverse spatial and textual k nearest neighbor queries. Proceedings of the VLDB Endowment 9(6):456–467CrossRef
7.
Cong G, Jensen CS, Wu D (2009) Efficient retrieval of the top-k most relevant spatial web objects. Proceedings of the VLDB Endowment 2(1):337–348CrossRef
8.
9.
Dong Y, Tang J, Wu S, Tian J, Chawla N V, Rao J, Cao H (2012) Link Prediction and recommendation across heterogeneous social networks. In: Proceedings of the 12th IEEE International Conference on Data Mining, Brussels, Belgium, pp 181–190
10.
Felipe I D, Hristidis V, Rishe N (2008) Keyword search on spatial databases. In: Proceedings of the 24th international conference on data engineering, Cancún, Mexico, pp 656–665
11.
Gao Y, Zheng B, Chen G, Lee W-C, Lee K C K, Li Q (2009) Visible reverse k-nearest neighbor queries. In: Proceedings of the 25th international conference on data engineering, Shanghai, China, pp 1203–1206
12.
Gao Y, Zheng B, Chen G, Lee W-C, Lee KCK, Li Q (2009) Visible reverse k-nearest neighbor query processing in spatial databases. IEEE Trans Knowl Data Eng 21(9):1314–1327CrossRef
13.
Gao Y, Qin X, Zheng B, Chen G (2015) Efficient reverse top-k Boolean spatial keyword queries on road networks. IEEE Trans Knowl Data Eng 27(5):1205–1218CrossRef
14.
Guo L, Shao J, Aung HH, Tan K-L (2015) Efficient continuous top-k spatial keyword queries on road networks. Geoinformatica 19(1):29–60CrossRef
15.
Hopcroft J, Lou T, Tang J (2011) Who will follow you back? Reciprocal relationship prediction. In: Proceedings of the 20th ACM conference on information and knowledge management, Glasgow, United Kingdom, pp 1137–1146
16.
Kolahdouzan M, Shahabi C (2004) Voronoi-based K nearest neighbor search for spatial network databases. In: Proceedings of the thirtieth international conference on very large data bases, Toronto, Canada, pp 840–851
17.
Korn F, Muthukrishnan S (2000) Influence sets based on reverse nearest neighbor queries. In: Proceedings of the 2000 ACM SIGMOD international conference on Management of Data, Dallas, Texas, USA, pp 201–212
18.
Korn F, Muthukrishnan S, Srivastava D (2002) Reverse nearest neighbor aggregates over data streams. In: Proceedings of the 28th international conference on very large data bases, Hong Kong, pp 814–825
19.
Lee KCK, Zheng B, Lee W-C (2008) Ranked reverse nearest neighbor search. IEEE Trans Knowl Data Eng 20(7):894–910CrossRef
20.
Li F, Cheng D, Hadjieleftheriou M, Kollios G, Teng S-H (2005) On trip planning queries in spatial databases. In: Proceedings of the 9th international symposium on advances in spatial and temporal databases. Angra dos Reis, Brazil, pp 273–290
21.
Li J, Li Y, Shen P, Xia X, Zong C, Xia C (2018) Reverse k nearest neighbor queries in time-dependent road networks. In: Proceedings of 20th IEEE international conference on high performance computing and communications; 16th IEEE international conference on Smart City; 4th IEEE international conference on data science and systems, Exeter, United Kingdom, pp 1064–1069
22.
Lian X, Chen L (2009) Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data. VLDB J 18(3):787–808CrossRef
23.
Liu Q, Gao Y, Chen G, Zheng B, Zhou L (2016) Answering why-not and why questions on reverse top-k queries. VLDB J 25:867–892CrossRef
24.
Liu Q, Feng Z, Xie X, Xu J, Lin X, Jensen C S (2018) iZone: Efficient influence zone evaluation over geo-textual data. In: Proceeding of the 34th IEEE international conference on data engineering, Paris, France, pp 1645–1648
25.
Liu Q, Zhu Z, Xu J, Gao Y (2021) MaxiZone: Maximizing influence zone over geo-textual data. IEEE Trans Knowl Data Eng. 33(10):3381–3393
26.
Lou T, Tang J, Hopcroft J, Fang Z, Ding X (2013) Learning to predict reciprocity and triadic closure in social networks. ACM Trans Knowl Discov Data 7(2):5:1–5:25CrossRef
27.
Lu J, Lu Y, Cong G (2011) Reverse spatial and textual k nearest neighbor search. In: Proceedings of the ACM SIGMOD international conference on Management of Data, Athens, Greece, pp 349–360
28.
Luo C, Li J, Li G, Wei W, Li Y, Li J (2016) Efficient reverse spatial and textual k nearest neighbor queries on road networks. Knowl-Based Syst 93:121–134CrossRef
29.
Stanoi I, Agrawal D, Abbadi A E (2000) Reverse nearest neighbor queries for dynamic databases. In: Proceedings of 2000 ACM SIGMOD workshop on research issues in data mining and knowledge discovery, Dallas, Texas, USA, pp 44–53
30.
Tao Y, Papadias D, Lian X (2004) Reverse kNN search in arbitrary dimensionality. In: Proceedings of the thirtieth international conference on very large data bases, Toronto, Canada, pp 744–755
31.
Wang S, Bao Z, Culpepper JS, Sellis T, Cong G (2018) Reverse k nearest neighbor search over trajectories. IEEE Trans Knowl Data Eng 30(4):757–771CrossRef
32.
Wu W, Yang F, Chan C-Y, Tan K-L (2008) FINCH: evaluating reverse k-nearest-neighbor queries on location data. Proceedings of the VLDB Endowment 1(1):1056–1067CrossRef
33.
Xie X, Yiu ML, Cheng R, Lu H (2014) Scalable evaluation of trajectory queries over imprecise location data. IEEE Trans Knowl Data Eng 26(8):2029–2044CrossRef
34.
Xie X, Lin X, Xu J, Jensen C S (2017) Reverse keyword-based location search. In: Proceeding of the 33rd IEEE international conference on data engineering, San Diego, CA, USA, pp 375–386
35.
Yang C, Lin K-I (2001) An index structure for efficient reverse nearest neighbor queries. In: Proceedings of the 17th international conference on data engineering, Heidelberg, Germany, pp 485–492
36.
Yang S, Cheema MA, Lin X, Zhang Y, Zhang W (2017) Reverse k nearest neighbors queries and spatial reverse top-k queries. VLDB J 26(2):151–176CrossRef
37.
Yiu ML, Papadias D, Mamoulis N, Tao Y (2006) Reverse nearest neighbors in large graphs. IEEE Trans Knowl Data Eng 18(4):540–553CrossRef
38.
Zhang J, Fang Z, Chen W, Tang J (2015) Diffusion of “following” links in microblogging networks. IEEE Trans Knowl Data Eng 27(8):2093–2106
39.
Zhao P, Fang HS, Sheng VS, Li Z, Xu J, Wu J, Cui Z (2017) Monochromatic and bichromatic ranked reverse Boolean spatial keyword nearest neighbors search. World Wide Web 20(1):39–59CrossRef
40.
Zhao J, Gao Y, Chen G, Jensen C S, Chen R, Cai D (2017) Reverse top-k geo-social keyword queries in road networks. In: Proceedings of the 33rd IEEE international conference on data engineering, San Diego, CA, USA, pp 387–398
41.
Zhong Z, Lin X, He L (2020) Answering range-based reverse kNN and why-not reverse kNN queries. Front Comput Sci 14(1):233–235CrossRef
Metadata
Title
Reverse keyword-based location search on road networks
Authors
Zijun Chen
Xin Wang
Wenyuan Liu
Publication date
12-11-2021
Publisher
Springer US
Published in
GeoInformatica / Issue 1/2022
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-021-00440-3

Other articles of this Issue 1/2022

GeoInformatica 1/2022 Go to the issue

OriginalPaper

GeoBalance: workload-aware partitioning of real-time spatiotemporal data

OriginalPaper

Contextual location recommendation for location-based social networks by learning user intentions and contextual triggers

OriginalPaper

Efficient computation of map algebra over raster data stored in the k2-acc compact data structure

OriginalPaper

CIME: Context-aware geolocation of emergency-related posts

OriginalPaper

Porting disk-based spatial index structures to flash-based solid state drives

OriginalPaper

A survey of location-based social networks: problems, methods, and future research directions