Skip to main content
SpringerLink
Log in

Determining topological relationship of fuzzy spatiotemporal data integrated with XML twig pattern

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

How to determine topological relationships is one of the most important operations on fuzzy spatiotemporal data. The proposed strategies impose strict restrictions on structure and data types of fuzzy spatiotemporal data, and fall short in their abilities to handle fuzzy attributes extension and fuzzy time extension. To overcome these limitations, in this paper, we first establish a fuzzy spatiotemporal data model based on XML. Then, we propose strategies of transforming two general fuzzy spatiotemporal data trees into one binary fuzzy spatiotemporal data tree. In succession, an effective algorithm to match the desired twigs is proposed after extending the region coding scheme to compatible with fuzzy spatiotemporal data. Our approach adopts XML twig pattern technique to determine topological relationship continuously so that it can reduce unnecessary execution time of querying the desired nodes. More importantly, we use a pointer array to eliminate unnecessary execution time of twig matching. Finally, the experimental results demonstrate the performance advantages of our approach.

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

Access this article

Log in via an institution

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

Similar content being viewed by others

References

  1. Al-Khalifa S, Jagadish HV, Koudas N, Patel JM, Srivastava D, Wu Y (2002) Structural joins: a primitive for efficient XML query pattern matching. In: Proceedings of the IEEE international conference on data engineering, pp 141–152

    Google Scholar 

  2. Azough A, Delteil A, Hacid MS, Marchi FD (2009) Fuzzy conceptual graphs for handling uncertainty in semantic video retrieval. In: Proceedings of the 11th IEEE international symposium on multimedia, pp 324–329

    Google Scholar 

  3. Balbiani P, Condotta JF (2002) Spatial reasoning about points in a multidimensional setting. Appl Intell 17(3):221–238

    Article  MATH  Google Scholar 

  4. Bao L, Qin XL, Zhang J, Li QY (2006) Reasoning the spatiotemporal relations between time evolving indeterminate regions. In: Lecture notes in computer science, vol 3930. Springer, Berlin, pp 448–458

    Google Scholar 

  5. Benferhat S, Ben-Naim J, Papini O, Würbel E (2010) An answer set programming encoding of prioritized removed sets revision: application to GIS. Appl Intell 32(1):60–87

    Article  Google Scholar 

  6. Bennett B, Cohn AG (2002) Multi-dimensional modal logic as a framework for spatio-temporal reasoning. Appl Intell 17(3):239–251

    Article  MATH  Google Scholar 

  7. Bruno N, Koudas N, Srivastava D (2002) Holistic twig joins: optimal XML pattern matching. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 310–321

    Google Scholar 

  8. Buckles BP, Petry FE (1982) A fuzzy representation of data for relational databases. Fuzzy Sets Syst 7(3):213–226

    Article  MATH  Google Scholar 

  9. Claramunt C, Theriault M (1995) Managing time in GIS: an event-oriented approach. In: Proceedings of the international workshop on temporal databases: recent advances in temporal databases, pp 142–161

    Google Scholar 

  10. Cobb MA, Petry FE (1998) Modeling spatial relationships within a fuzzy framework. J Am Soc Inf Sci 49(3):253–266

    Article  Google Scholar 

  11. Cohn AG, Gotts NM (1996) The ‘egg-yolk’ representation of regions with indeterminate boundaries. In: Burrough PA, Frank AU (eds) Geographic objects with indeterminate boundaries. Taylor & Francis, London, pp 171–187

    Google Scholar 

  12. Deng SS, Xia LH, Wang F (2009) Analysis of spatio-temporal characteristics of urban land cover and its landscape pattern: a case study in NanHai district of Foshan city. In: Joint urban remote sensing event, pp 1–9

    Google Scholar 

  13. Du Z, Jeong YS, Jeong MK, Kong SG (2012) Multidimensional local spatial autocorrelation measure for integrating spatial and spectral information in hyperspectral image band selection. Appl Intell 36(2):542–552

    Article  Google Scholar 

  14. Gabelaia D, Kontchakov R, Kurucz A, Wolter F, Zakharyaschev M (2005) Combining spatial and temporal logics: expressiveness vs. complexity. J Artif Intell Res 23(4):167–243

    MathSciNet  MATH  Google Scholar 

  15. Gaurav A, Alhajj R (2006) Incorporating fuzziness in XML and mapping fuzzy relational data into fuzzy XML. In: Proceedings of the 2006 ACM symposium on applied computing, pp 456–460

    Chapter  Google Scholar 

  16. Guesgen HW (2002) Reasoning about distance based on fuzzy sets. Appl Intell 17(3):265–270

    Article  MATH  Google Scholar 

  17. Jiang H, Lu H, Wang W (2004) Efficient processing of XML twig queries with OR-predicates. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data, pp 274–285

    Google Scholar 

  18. Jin PQ, Wan SH, Yue LH (2008) A semantic framework for spatiotemporal data representation. In: Proceedings of the 3rd international IEEE conference on signal-image technologies and Internet-based system, pp 10–17

    Google Scholar 

  19. Kimelfeld B, Sagiv Y (2007) Matching twigs in probabilistic XML. In: Proceedings of the 33rd international conference on very large data bases, pp 27–38

    Google Scholar 

  20. Koubarakis M (2002) Querying temporal constraint networks: a unifying approach. Appl Intell 17(3):297–311

    Article  MATH  Google Scholar 

  21. Koyuncu M, Yazici A (2003) IFOOD: an intelligent fuzzy object-oriented database architecture. IEEE Trans Knowl Data Eng 15(5):1137–1154

    Article  Google Scholar 

  22. Lewis L, Buford J, Jakobson G (2009) Inferring threats in urban environments with uncertain and approximate data: an agent-based approach. Appl Intell 30(3):220–232

    Article  Google Scholar 

  23. Li YW, Wang GR, Xin JC, Zhang E, Qiu Z (2009) Holistically twig matching in probabilistic XML. In: Proceedings of the 25th international conference on data engineering, pp 1640–1656

    Google Scholar 

  24. Ma ZM, Liu J, Yan L (2010) Fuzzy data modeling and algebraic operations in XML. Int J Intell Syst 25(9):925–947

    MATH  Google Scholar 

  25. Ma ZM, Liu J, Yan L (2011) Matching twigs in fuzzy XML. Inf Sci 181(1):184–200

    Article  MathSciNet  MATH  Google Scholar 

  26. Ma ZM, Yan L (2007) Fuzzy XML data modeling with the UML and relational data models. Data Knowl Eng 63(3):972–996

    Article  MathSciNet  Google Scholar 

  27. Mehrotra R, Sharma A (2009) Evaluating spatio-temporal representations in daily rainfall sequences from three stochastic multi-site weather generation approaches. Adv Water Resour 32(6):948–962

    Article  Google Scholar 

  28. Mihalcea R (2012) CSCE 3110 data structures & algorithm analysis. University of North Texas. http://www.cs.unt.edu/~rada/CSCE3110

  29. Obeid N (2005) A formalism for representing and reasoning with temporal information, event and change. Appl Intell 23(2):109–119

    Article  MathSciNet  Google Scholar 

  30. Oliboni B, Pozzani G (2008) Representing fuzzy information by using XML schema. In: Proceedings of the 19th international conference on database and expert systems application, pp 683–687

    Google Scholar 

  31. Open GIS Consortium Inc. (OGC) (2001) Geography Markup Language (GML). http://www.opengis.net/gml/01-029/GML2.html

  32. Papadakis N, Plexousakis D, Christodolou Y (2012) The ramification problem in temporal databases: a solution implemented in SQL. Appl Intell 36(4):749–767

    Article  Google Scholar 

  33. Pauly A, Schneider M (2005) Topological predicates between vague spatial objects. In: Proceedings of the 9th international conference on advances in spatial and temporal databases, pp 418–432

    Chapter  Google Scholar 

  34. Peuquet D, Duan N (1995) An event-based spatiotemporal data model for temporal analysis of geographical data. Int J Geogr Inf Syst 9(1):7–24

    Article  Google Scholar 

  35. Pfoser D, Jensen C (1999) Capturing the uncertainty of moving-object representations. In: Proceedings of the 6th international symposium on spatial databases, pp 111–132

    Google Scholar 

  36. Pfoser D, Tryfona N (1998) Requirements, definitions, and notations for spatiotemporal application environments. In: Proceedings of the 6th ACM symposium on geographic information systems, pp 124–130

    Chapter  Google Scholar 

  37. Pfoser D, Tryfona N (1999) Capturing fuzziness and uncertainty of spatiotemporal objects. In: Proceedings of the 6th international symposium on spatial, pp 111–132

    Google Scholar 

  38. Rizzolo F, Vaisman AA (2008) Temporal XML: modeling, indexing, and query processing. VLDB J 17(5):1179–1212

    Article  Google Scholar 

  39. Salamat N, Zahzah EH (2010) Fusion of fuzzy spatial relations. Hybrid Artif Intel Syst 6076:294–301

    Article  Google Scholar 

  40. Salamat N, Zahzah EH (2010) Fuzzy spatio-temporal relations analysis. In: Proceedings of the seventh international conference on information technology, pp 301–306

    Google Scholar 

  41. Senellart P, Abiteboul S (2007) On the complexity of managing probabilistic XML data. In: Proceedings of the 26th ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems, pp 283–292

    Google Scholar 

  42. Sözer A, Yazici A, Oğuztüzün H, Petry FE (2010) Querying fuzzy spatiotemporal databases: implementation issues. In: Uncertainty approach for spatial data modeling and processing. Springer, Berlin Heidelberg, pp 97–116

    Chapter  Google Scholar 

  43. Sözer A, Yazici A, Oğuztüzün H, Tas O (2008) Modeling and querying fuzzy spatiotemporal databases. Inf Sci 178(19):3665–3682

    Article  Google Scholar 

  44. Stefanakis E (2001) A unified framework for fuzzy spatio-temporal representation and reasoning. In: Proceedings of the 20th international cartographic conference, pp 2678–2687

    Google Scholar 

  45. Summary of meteorological and tidal observations in Hong Kong in 2011 (2012). http://www.weather.gov.hk/publica/pubsmo.htm

  46. Tang X, Fang Y, Kainz W (2006) Fuzzy topological relations between fuzzy spatial objects. In: Lecture notes in computer science, vol 4223. Springer, Berlin, pp 324–333

    Google Scholar 

  47. Tang X, Kaina W (2002) Analysis of topological relations between fuzzy regions in a general fuzzy topological space. In: Proceedings of symposium on geospatial theory, processing and applications, pp 1–15

    Google Scholar 

  48. Tossebro E, Nygard M (2002) Uncertainty in spatiotemporal databases. In: Proceedings of the 2nd biennial international conference on advances in information systems, pp 43–53

    Chapter  Google Scholar 

  49. Turowski K, Weng U (2002) Representing and processing fuzzy information—an XML-based approach. Knowl-Based Syst 15(1–2):67–75

    Article  Google Scholar 

  50. Verma NK, Pal NR (2010) Prediction of satellite images using fuzzy rule based Gaussian regression. In: Proceedings of the 39th IEEE conference on applied imagery pattern recognition workshop, pp 1–8

    Google Scholar 

  51. Yan L, Ma ZM, Liu J (2009) Fuzzy data modeling based on XML schema. In: Proceedings of the 2009 ACM symposium on applied computing, pp 1563–1567

    Chapter  Google Scholar 

  52. Yi SZ, Huang B, Chan WT (2002) Spatio-temporal information integration in XML. Future Gener Comput Syst 20(7):1157–1170

    Google Scholar 

  53. Zadeh LA (1965) Fuzzy sets. Inf Control 8(3):338–353

    Article  MathSciNet  MATH  Google Scholar 

  54. Zadeh LA (1978) Fuzzy sets as a basis for theory of possibility. Fuzzy Sets Syst 1(1):3–28

    Article  MathSciNet  MATH  Google Scholar 

  55. Zadeh LA (2008) Is there a need for fuzzy logic? Inf Sci 178(13):2751–2779

    Article  MathSciNet  MATH  Google Scholar 

  56. Zadeh LA (2005) Toward a generalized theory of uncertainty (gtu)-an outline. Inf Sci 172(1–2):1–40

    Article  MathSciNet  MATH  Google Scholar 

  57. Zhan FB, Lin H (2003) Overlay of two simple polygons with indeterminate boundaries. Trans GIS 7(1):67–81

    Article  Google Scholar 

  58. Zhang C, Naughton JF, DeWitt DJ, Luo Q, Lohman GM (2001) On supporting containment queries in relational database management systems. In: Proceedings of the ACM SIGMOD international conference on management of data, pp 425–436

    Google Scholar 

Download references

Acknowledgements

The authors wish to thank the anonymous referees for their valuable comments and suggestions, which improved the technical content and the presentation of the paper. This work was supported by the National Natural Science Foundation of China (60873010, 61073139 and 61202260), and in part by the Program for New Century Excellent Talents in University (NCET-05-0288).

Author information

Authors and Affiliations

  1. College of Information Science & Engineering, Northeastern University, Shenyang, 110819, China

    Luyi Bai & Z. M. Ma

  2. School of Software, Northeastern University, Shenyang, 110819, China

    Li Yan

Authors
  1. Luyi Bai
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Li Yan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Z. M. Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Z. M. Ma.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bai, L., Yan, L. & Ma, Z.M. Determining topological relationship of fuzzy spatiotemporal data integrated with XML twig pattern. Appl Intell 39, 75–100 (2013). https://doi.org/10.1007/s10489-012-0395-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-012-0395-3

Keywords

Search

Navigation