Toward Approximate GML Search and Retrieval

Joe TEKLI   Richard CHBEIR   Fernando FERRI & Patrizia GRIFONI
SOE, Dept. of Electrical & Computer Eng.
Lebanese American University
36 Byblos, LEBANON
  UPPA Laboratory, IUT of Bayonne
University of Pau and Adour Countries
64600 Anglet, FRANCE

National Italian Reseach Council
via Nizza 128, 00198 Roma, ITALY

  {fernando.ferri, patrizia.grifoni} @ irpps.cnr.it



    The amount of geographic data on the Internet is becoming huge and widely accessible to users who are generally non-computer scientists. On one hand, users usually search data without a deep knowledge of the spatial domain at hand, thus formulating queries resulting in a reduction of result quality. In this context, techniques for approximate and ranked querying become crucial. Such techniques require, in one way or another, the evaluation of query/data similarity. On the other hand, GML [1] is emerging as the new standard for representing geographic information. Following GML, a geographic entity consists of a hierarchically structured self describing piece of geographic information, incorporating structurally and semantically rich data in one entity.
    In this study, we address the problem of approximate and ranked querying for GML data, and proposed a method for GML query evaluation [2]. Our method consists of two main contributions. First, we propose a tree model for representing GML queries and data collections. Then, we provide a GML retrieval framework based on the concept of tree edit distance [3, 4] as an efficient means for comparing rigorously structured data . Our method allows the evaluation of both structural [5] and semantic similarities [6, 7] in GML data, enabling the user to tune the querying process according to her needs. The user can also choose to perform either template or minimum constraint querying. Following the latter strategy, only elements required by the query tree are taken into account in similarity evaluation. Preliminary experimental tests are promising.

    Hereunder, we provide links to the XS3 experimental prototype, in which our GML approximate querying method was implemented, as well as the experimental data and results utilized in our preliminary experimental evaluation.


    1. Geography Mark-up Language (GML), Open Geospatial Consortium, http://www.opengeospatial.org/standards/gml , visited on the 20 th of November, 2009.
    2. Tekli J., Chbeir R., Ferri F., and Grifoni P., Toward Approximate GML Retrieval Based on Structural and Semantic Characteristics. In proc. of the International Conference on Web Engineeering (ICWE), 2010, pp. 16-34
    3. Tekli J.; Chbeir R. and Kokou Yetongnon, Extensible User-based Grammar Matching. In Proc. of ER'09, 2009. LNCS 5829. pp. 294-314.
    4. Tekli J., Chbeir R., and Yetongnon K., Efficient XML Structural Similarity Detection using Sub-tree Commonalities. In Proc. of SBBD & SIGMOD DiSC, 2007. pp. 116-130.
    5. Nierman A. and Jagadish H. V., Evaluating structural similarity in XML documents. In Proc. of ACM SIGMOD WebDB, pp. 61-66, 2002.
    6. Lin D., An Information-Theoretic Definition of Similarity. Proceedings of ICML, 1998. pp. 296-304.
    7. Wu Z. and Palmer M., Verb Semantics and Lexical Selection. 32nd Meeting of the Associations of Comp. Linguistics, 1994. pp. 133-138.