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/2015

01-01-2015

Efficient continuous top-k spatial keyword queries on road networks

Authors: Long Guo, Jie Shao, Htoo Htet Aung, Kian-Lee Tan

Published in: GeoInformatica | Issue 1/2015

Log in

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

search-config
loading …

Abstract

With the development of GPS-enabled mobile devices, more and more pieces of information on the web are geotagged. Spatial keyword queries, which consider both spatial locations and textual descriptions to find objects of interest, adapt well to this trend. Therefore, a considerable number of studies have focused on the interesting problem of efficiently processing spatial keyword queries. However, most of them assume Euclidean space or examine a single snapshot query only. This paper investigates a novel problem, namely, continuous top-k spatial keyword queries on road networks, for the first time. We propose two methods that can monitor such moving queries in an incremental manner and reduce repetitive traversing of network edges for better performance. Experimental evaluation using large real datasets demonstrates that the proposed methods both outperform baseline methods significantly. Discussion about the parameters affecting the efficiency of the two methods is also presented to reveal their relative advantages.
previous article Recognizing text in raster maps
next article Partition-based range query for uncertain trajectories in road networks

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
Footnotes
1
In this paper, we use an undirected graph G(N,E) and transmit the direction of q explicitly. We cannot model the road network as a directed graph and get the direction of q from the directed graph. The reason is that if one road is bidirectional, the direction cannot be obtained.
 
2
Note that for the CkSK queries, the generators are the relevant objects in O r that match at least one of the query keywords in their descriptions.
 
Literature
1.
Anh VN, de Kretser O, Moffat A (2001) Vector-space ranking with effective early termination. In: SIGIR. pp 35–42
2.
Brinkhoff T (2002) A framework for generating network-based moving objects. GeoInformatica 6(2):153–180CrossRef
3.
Cheema MA, Brankovic L, Lin X, Zhang W, Wang W (2011) Continuous monitoring of distance-based range queries. IEEE Trans Knowl Data Eng 23(8):1182–1199CrossRef
4.
Chen L, Cong G, Jensen CS, Wu D (2013) Spatial keyword query processing: an experimental evaluation. In: VLDB. pp 217–228
5.
Chen Z, Shen HT, Zhou X, Yu JX (2009) Monitoring path nearest neighbor in road networks. In: SIGMOD conference. pp 591–602
6.
Cho HJ, Chung CW (2005) An efficient and scalable approach to cnn queries in a road network. In: VLDB. pp 865–876
7.
Cong G, Jensen CS, Wu D (2009) Efficient retrieval of the top-k most relevant spatial web objects. PVLDB 2(1):337–348
8.
Felipe ID, Hristidis V, Rishe N (2008) Keyword search on spatial databases. In: ICDE. pp 656–665
9.
Hu H, Xu J, Lee DL (2005) A generic framework for monitoring continuous spatial queries over moving objects. In: SIGMOD conference. pp 479–490
10.
Huang W, Li G, Tan KL, Feng J (2012) Efficient safe-region construction for moving top-k spatial keyword queries. In: CIKM. pp 932–941
11.
Kolahdouzan MR, Shahabi C (2004) Voronoi-based k nearest neighbor search for spatial network databases. In: VLDB. pp 840–851
12.
Kolahdouzan MR, Shahabi C (2005) Alternative solutions for continuous k nearest neighbor queries in spatial network databases. GeoInformatica 9(4):321–341CrossRef
13.
Nutanong S, Tanin E, Shao J, Zhang R, Ramamohanarao K (2012) Continuous detour queries in spatial networks. IEEE Trans Knowl Data Eng 24(7):1201–1215CrossRef
14.
Nutanong S, Zhang R, Tanin E, Kulik L (2008) The v∗-diagram: a query-dependent approach to moving knn queries. PVLDB 1(1):1095–1106
15.
Okabe A, Boots B, Sugihara K, Chiu SN (2000) Spatial tessellations: concepts and applications of Voronoi diagrams, 2nd edn. Wiley, ChichesterCrossRef
16.
Okabe A, Satoh T, Furuta T, Suzuki A, Okano K (2008) Generalized network voronoi diagrams: concepts, computational methods, and applications. Int J Geogr Inf Sci 22(9):965–994CrossRef
17.
Rocha-Junior JB, Gkorgkas O, Jonassen S, Nørvåg K (2011) Efficient processing of top-k spatial keyword queries. In: SSTD. pp 205–222
18.
Rocha-Junior JB, Nørvåg K (2012) Top-k spatial keyword queries on road networks. In: EDBT. pp 168–179
19.
Salton G, Buckley C (1988) Term-weighting approaches in automatic text retrieval. Inf Process Manage 24(5):513–523CrossRef
20.
Wu D, Yiu ML, Cong G, Jensen CS (2012) Joint top-k spatial keyword query processing. IEEE Trans Knowl Data Eng 24(10):1889–1903CrossRef
21.
Wu D, Yiu ML, Jensen CS, Cong G (2011) Efficient continuously moving top-k spatial keyword query processing. In: ICDE. pp 541–552
22.
Wu W, Guo W, Tan KL (2007) Distributed processing of moving k-nearest-neighbor query on moving objects. In: ICDE. pp 1116–1125
23.
Zhang C, Zhang Y, Zhang W, Lin X (2013) Inverted linear quadtree: efficient top k spatial keyword search. In: ICDE
24.
Zhang D, Chee YM, Mondal A, Tung AKH, Kitsuregawa M (2009) Keyword search in spatial databases: towards searching by document. In: ICDE. pp 688–699
25.
Zhang D, Tan KL, Tung AKH (2013) Scalable top-k spatial keyword search. In: EDBT. pp 359–370
26.
Zhou Y, Xie X, Wang C, Gong Y, Ma WY (2005) Hybrid index structures for location-based web search. In: CIKM. pp 155–162
27.
Zobel J, Moffat A (2006) Inverted files for text search engines. ACM Comput Surv 38(2)
Metadata
Title
Efficient continuous top-k spatial keyword queries on road networks
Authors
Long Guo
Jie Shao
Htoo Htet Aung
Kian-Lee Tan
Publication date
01-01-2015
Publisher
Springer US
Published in
GeoInformatica / Issue 1/2015
Print ISSN: 1384-6175
Electronic ISSN: 1573-7624
DOI
https://doi.org/10.1007/s10707-014-0204-8

Other articles of this Issue 1/2015

GeoInformatica 1/2015 Go to the issue

OriginalPaper

Recognizing text in raster maps

OriginalPaper

Partition-based range query for uncertain trajectories in road networks

OriginalPaper

Stacked space-time densities: a geovisualisation approach to explore dynamics of space use over time

OriginalPaper

Spatio-temporal compression of trajectories in road networks

OriginalPaper

Domain-driven co-location mining