Structural similarity in geographical queries to improve query answering

ABSTRACT

The paper proposes a method for query approximation in Geographic Information Systems. In particular, the problem of matching a query with imprecise or missing data is analyzed and an approach for the relaxation of query constraints is proposed. Query approximation is performed by relaxing structural constraints, according to an extension of a previous proposal for evaluating concept similarity in an ontology management system [1] inspired by the maximum weighted matching problem in bipartite graphs. In our approach, we start from a weighted hierarchy of geographical objects evaluated using WordNet, a lexical database for the English language available on the Internet. If a concept contained in a query has no match in the database, the query is approximated using a structural similarity graph that connects all geographical concepts by the lowest structural distance. The aim of the proposed methodology is to relax structural query constraints, in order to obtain meaningful answers for imprecise or missing data.

REFERENCES

• 1: A. Formica, M. Missikoff. "Concept Similarity in SymOntos: an Enterprise Ontology Management Tool" The Computer Journal, 45(6), 583--594, 2002.
• 2: M. A. Rodriguez, M. J. Egenhofer. "Comparing Geospatial Entity Classes: an Asymmetric and Content-Dependent Similarity Measure" International Journal of Geographical Information Science 18(3), pp. 229--256, 2004
• 3: M. Andrea Rodríguez , Max J. Egenhofer, Determining Semantic Similarity among Entity Classes from Different Ontologies, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.442-456, February 2003 [doi>10.1109/TKDE.2003.1185844]
• 4: A. D'Ulizia, F. Ferri, P. Grifoni, M. Rafanelli. "Relaxing constraints on GeoPQL operators for improving query answering". DEXA'06, LNCS 4080, pp 728--737, 2006.
• 5: J. H. Lee, M. H. Kim, Y. J. Lee. "Information retrieval based on conceptual distance in is-a hierarchies" Journal of Documentation, Vol.49, n.2, pp. 188--207, 1989
• 6: R. Rada, H. Mili, E. Bicknell, M. Blettner. "Development and application of a metric on semantic nets" IEEE Transaction on Systems, Man, and Cybernetics, Vol.19, n. 1, pp. 17--30, 1989
• 7: P. Resnik. "Semantic similarity in a taxonomy: an information-based measure and its application to problems of ambiguity in natural language" Journal of Artificial Intelligence Research, Vol.11, pp. 95--130, 1999
• 8: Dekang Lin, An Information-Theoretic Definition of Similarity, Proceedings of the Fifteenth International Conference on Machine Learning, p.296-304, July 24-27, 1998
• 9: P. Resnik. "Using information content to evaluate semantic similarity in a taxonomy" Proceed. IJCAI 1995
• 10: Ana G. Maguitman , Filippo Menczer , Heather Roinestad , Alessandro Vespignani, Algorithmic detection of semantic similarity, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060765]
• 11: F. Ferri, A. Formica, P. Grifoni, M. Rafanelli. "Query approximation by semantic similarity in GeoPQL". In 2nd International Workshop on Semantic-based Geographical Information Systems (SeBGIS'06). Montpellier, France, October 2006.
• 12: K. S. Candan, J. W. Kim, H. Liu, and R. Suvarna. Structure-based mining of hierarchical media data, meta-data, and ontologies. In 5th Workshop on Multimedia Data Mining, Seattle, WA, August 2004.
• 13: T. Dalamagas, T. Cheng, K. J. Winkel, T. K. Sellis. "Clustering XML Documents by Structure". SETN'04, 112--121, 2004.
• 14: WordNet 2.1: A lexical database for the English language; http://www.cogsci.princeton.edu/cgi-bin/webwn, 2005.
• 15: S. Ross. "A First Course in Probability. Macmillan", 1976.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Linguistic processing

General Terms:
Algorithms

Keywords:
geographical query languages, relaxing constraints, structural similarity