Skip to main content
Fachgebiete
Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Weitere Formate
Webinare Technik
Webinare Wirtschaft
Kongresse
Veranstaltungskalender
Podcasts
Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen beantragen
Erweiterte Suche
Anmelden
nach oben
The VLDB Journal

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

Erschienen in: The VLDB Journal 5/2019

10.07.2019 | Regular Paper

Evaluating pattern matching queries for spatial databases

verfasst von: Yixiang Fang, Yun Li, Reynold Cheng, Nikos Mamoulis, Gao Cong

Erschienen in: The VLDB Journal | Ausgabe 5/2019

Einloggen, um Zugang zu erhalten

Abstract

In this paper, we study the spatial pattern matching (SPM) query. Given a set D of spatial objects (e.g., houses and shops), each with a textual description, we aim at finding all combinations of objects from D that match a user-defined spatial patternP. A pattern P is a graph whose vertices represent spatial objects, and edges denote distance relationships between them. The SPM query returns the instances that satisfy P. An example of P can be “a house within 10-min walk from a school, which is at least 2 km away from a hospital.” The SPM query can benefit users such as house buyers, urban planners, and archeologists. We prove that answering such queries is computationally intractable and propose two efficient algorithms for their evaluation. Moreover, we study efficient solutions to address two related problems of the SPM: (1) find top-k matches that are close to a query location and (2) return partial matches for a query pattern. Experiments and case studies on real datasets show that our proposed solutions are highly effective and efficient.
Vorheriger Artikel Location prediction in large-scale social networks: an in-depth benchmarking study
Nächster Artikel Efficient two-dimensional Haar synopsis construction for the maximum absolute error measure

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

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 90 Tage mit der neuen Mini-Lizenz testen!

Jetzt informieren

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 90 Tage mit der neuen Mini-Lizenz testen!

Jetzt informieren

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 90 Tage mit der neuen Mini-Lizenz testen!

Jetzt informieren
Fußnoten
1
The user can input the lower/upper bounds of the intervals based on his experience and expertise. Alternatively, the system can be designed to give suggestions, based on, for instance, the previous users’ inputs or query results.
 
2
In context without ambiguity, we simply call it a pattern.
 
3
To avoid ambiguity, we use “node” to mean “IR-tree node,” and “vertex” to mean “vertex” of the spatial pattern in this paper.
 
Literatur
1.
Zhang, D., et al.: Keyword search in spatial databases: towards searching by document. In: ICDE, pp. 688–699. IEEE (2009)
2.
Guo, T., Cao, X., Cong, G.: Efficient algorithms for answering the m-closest keywords query. In: SIGMOD, pp. 405–418. ACM (2015)
3.
Deng, K., Li, X., Lu, J., Zhou, X.: Best keyword cover search. TKDE 27(1), 61–73 (2015)
4.
Choi, D., Pei, J., Lin, X.: Finding the minimum spatial keyword cover. In: ICDE, pp. 685–696. IEEE (2016)
5.
Niemelä, J.: Ecology and urban planning. Biodivers. Conserv. 8(1), 119–131 (1999) CrossRef
6.
Schnaiberg, J., Riera, J., Turner, M.G., Voss, P.R.: Explaining human settlement patterns in a recreational lake district: Vilas county, Wisconsin, USA. Environ. Manag. 30(1), 24–34 (2002) CrossRef
7.
8.
9.
Papadias, D., et al.: Algorithms for querying by spatial structure. In: VLDB, pp. 546–557 (1998)
10.
Mamoulis, N., Papadias, D.: Multiway spatial joins. TODS 26(4), 424–475 (2001) CrossRef
11.
Zou, L., Chen, L., Özsu, M.T.: Distance-join: pattern match query in a large graph database. PVLDB 2(1), 886–897 (2009)
12.
Carletti, V., et al.: Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with VF3. In: TPAMI (2017)
13.
Wu, Y., Patel, J.M., Jagadish, H.: Structural join order selection for XML query optimization. In: ICDE, pp. 443–454. IEEE (2003)
14.
Fang, Y., Cheng, R., Wang, J., Budiman, Cong, G., Mamoulis, N.: SpaceKey: exploring patterns in spatial databases. In: ICDE, pp. 1577–1580. IEEE (2018)
15.
Fang, Y., Cheng, R., Cong, G., Mamoulis, N., Li, Y.: On spatial pattern matching. In: ICDE, pp. 293–304. IEEE (2018)
16.
Li, Y., Fang, Y., Cheng, R., Zhang, W.: Spatial pattern matching: a new direction for finding spatial objects. SIGSPATIAL Spec 11(1), 3–12 (2019) CrossRef
17.
18.
Chen, L., Cong, G., Jensen, C.S., Wu, D.: Spatial keyword query processing: an experimental evaluation. In: PVLDB, pp. 217–228 (2013)
19.
Wu, D., Yiu, M.L., Cong, G., Jensen, C.S.: Joint top-k spatial keyword query processing. TKDE 24(10), 1889–1903 (2012) CrossRef
20.
Papadias, D., Mamoulis, N., Theodoridis, Y.: Processing and optimization of multiway spatial joins using r-trees. In: PODS (1999)
21.
Jin, J., An, N., Sivasubramaniam, A.: Analyzing range queries on spatial data. In: ICDE, pp. 525–534 (2000)
22.
Chen, F., Wu, X.: Perfect pipelining for streaming large file in peer-to-peer networks. In: Theoretical Computer Science, pp. 27–38 (2014)
23.
24.
25.
26.
Zhang, S., Yang, J., Jin, W.: Sapper: subgraph indexing and approximate matching in large graphs. PVLDB 3(1–2), 1185–1194 (2010)
27.
Zhu, G., et al.: Treespan: efficiently computing similarity all-matching. In: SIGMOD, pp. 529–540. ACM (2012)
28.
Thomas, L.T., Valluri, S.R., Karlapalem, K.: Margin: maximal frequent subgraph mining. TKDD 4(3), 10 (2010) CrossRef
29.
30.
Fang, Y., Cheng, R., Li, X., Luo, S., Hu, J.: Effective community search over large spatial graphs. PVLDB 10(6), 709–720 (2017)
31.
Fang, Y., Cheng, R., Tang, W., Maniu, S., Yang, X.: Scalable algorithms for nearest-neighbor joins on big trajectory data. TKDE 28(3), 785–800 (2016)
32.
Fang, Y., Wang, Z., Cheng, R., Li, X., Luo, S., Hu, J., Chen, X.: On spatial-aware community search. TKDE 31(4), 783–798 (2019)
33.
Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. VLDB 2(1), 337–348 (2009)
34.
Zhang, C., Zhang, Y., Zhang, W., Lin, X.: Inverted linear quadtree: efficient top-k spatial keyword search. TKDE 28(7), 1706–1721 (2016)
35.
Huang, W., Li, G., Tan, K.-L., Feng, J.: Efficient safe-region construction for moving top-k spatial keyword queries. In: CIKM, pp. 932–941. ACM (2012)
36.
Zhang, C., Zhang, Y., Zhang, W., Lin, X., Cheema, M.A., Wang, X.: Diversified spatial keyword search on road networks. In: EDBT, pp. 367–378 (2014)
37.
Mahmood, A.R., Aref, W.G., Aly, A.M., Tang, M.: Atlas: on the expression of spatial-keyword group queries using extended relational constructs. In: SIGSPATIAL, p. 45. ACM (2016)
38.
Cao, X., Cong, G., Jensen, C.S., Ooi, B.C.: Collective spatial keyword querying. In: SIGMOD, pp. 373–384. ACM (2011)
39.
Liu, J., Deng, K., Sun, H., Ge, Y., Zhou, X., Jensen, C.S.: Clue-based spatio-textual query. PVLDB 10(5), 529–540 (2017)
40.
Brinkhoff, T., Kriegel, H.-P., Seeger, B.: Efficient processing of spatial joins using r-trees. In: SIGMOD, pp 237–246 (1993)
41.
Mamoulis, N., Papadias, D.: Integration of spatial join algorithms for processing multiple inputs. SIGMOD 28(2), 1–12 (1999) CrossRef
42.
Gallagher, B.: Matching structure and semantics: a survey on graph-based pattern matching. AAAI FS 6, 45–53 (2006)
43.
Tong, H., Faloutsos, C., Gallagher, B., Eliassi-Rad, T.: Fast best-effort pattern matching in large attributed graphs. In: KDD, pp. 737–746 (2007)
44.
Tang, M., et al.: Similarity group-by operators for multi-dimensional relational data. TKDE 28(2), 510–523 (2016)
45.
Mongiovi, M., et al.: Sigma: a set-cover-based inexact graph matching algorithm. J. Bioinform. Comput. Biol. 8(02), 199–218 (2010) CrossRef
46.
Tian, Y., et al.: Tale: a tool for approximate large graph matching. In: ICDE, pp. 963–972. IEEE (2008)
Metadaten
Titel
Evaluating pattern matching queries for spatial databases
verfasst von
Yixiang Fang
Yun Li
Reynold Cheng
Nikos Mamoulis
Gao Cong
Publikationsdatum
10.07.2019
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 5/2019
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-019-00550-3

Weitere Artikel der Ausgabe 5/2019

The VLDB Journal 5/2019 Zur Ausgabe

Regular Paper

SRX: efficient management of spatial RDF data

Regular Paper

Eccentricities on small-world networks

Regular Paper

On the performance and convergence of distributed stream processing via approximate fault tolerance

Regular Paper

Fast and accurate stream processing by filtering the cold

Regular Paper

Efficient two-dimensional Haar synopsis construction for the maximum absolute error measure

Regular Paper

Location prediction in large-scale social networks: an in-depth benchmarking study

Premium Partner