›› 2009, Vol. 24 ›› Issue (6): 1109-1124.

• Distributed Computing and Systems • Previous Articles     Next Articles

Approximating Geographical Queries

Arianna D'Ulizia1, Fernando Ferri1, Anna Formica2, and Patrizia Grifoni1   

  1. 1Institute of Research on Population and Social Policies, National Research Council, Rome, 00185, Italy
    2Institute for System Analysis and Computer Science, National Research Council, Rome, 00185, Italy
  • Received:2009-01-12 Revised:2009-07-22 Online:2009-11-05 Published:2009-11-05
  • About author:
    Arianna D'Ulizia received the M.S. degree in computer science engineering from the University of Rome "La Sapienza'' in 2005 and the Ph.D. degree in computer science and automation from the "Roma Tre'' University in 2009. She is currently a researcher at the Institute of Research on Population and Social Policies of the National Research Council of Italy. She is the author of more than 25 papers on international conferences and books. She is mainly interested in human computer interaction, multimodal interaction, visual languages, geographical query languages, risk governance, and knowledge management in virtual communities.
    Fernando Ferri received the M.S. degree in electronics engineering in 1990 and the Ph.D. degree in medical informatics in 1993 both from the University of Rome "La Sapienza''. He is a senior researcher at the National Research Council of Italy since 2001. From 1996 to 2001 he was a researcher at the National Research Council of Italy. From 1993 to 2000 he was a professor of "Sistemi di Elaborazione'' at the University of Macerata. He is the author of more than 120 papers in international journals, books and conferences. He was responsible for several projects funded by Italian Ministry of University and Research and European Commission. His main methodological areas of interest are: human-computer interaction, visual languages, visual interfaces, sketch-based interfaces, and multimodal interfaces and languages, data and knowledge bases, geographic information systems, Web technologies, social networks and risk governance.
    Anna Formica received the full-honors M.S. degree in mathematics from the University of Rome "La Sapienza'' in 1989. Currently, she is a researcher at the Istituto di Analisi dei Sistemi ed Informatica (IASI) "Antonio Ruberti'' of the Italian National Research Council, Rome, where she works with the Information Systems and Knowledge Bases group, and the Laboratory for Enterprise Knowledge and Systems (LEKS). She serves as referee of several international journals and conferences and she took part in various research projects of the European Framework Programs and bilateral projects with international institutions. Her current research interests are Semantic Web, similarity reasoning, formal specification and validation of domain ontologies.
    Patrizia Grifoni received the M.S. degree in electronics engineering in 1990. From 1994 to 2000 she was a professor of "Elaborazione digitale delle immagini'' at the University of Macerata. She is a researcher at the National Research Council of Italy since 1993. She is the author of more than 80 papers in international journals, books and conferences. She was responsible for several projects funded by Italian and International Institutions. Her scientific interests have evolved from query languages for statistical and geographic databases to the focal topics related to human-computer interaction, multimodal interaction and languages, visual languages, visual interfaces, sketch-based interfaces, Web technologies, social networks and risk governance.

This article proposes a graph-theoretic methodology for query approximation in Geographic Information Systems, enabling the relaxation of three kinds of query constraints: topological, semantic and structural. An approximate query is associated with a value corresponding to the degree of similarity with the original query. Such a value is computed for topological constraints on the basis of the topological distance between configurations, for semantic constraints using the information content approach, and for structural constraints revisiting the maximum weighted matching problem in bipartite graphs. Finally, the high correlation of our proposal with human judgment is demonstrated by an experiment.

[1] Ferri F, Rafanelli M. GeoPQL: A geographical pictorial query language that resolves ambiguities in query interpretation. Journal of Data Semantics III, Springer-Verlag Publ., LNCS 3534, 2005, pp.50–80.
[2] Egenhofer M J. Query processing in spatial-query-by-sketch. Journal of Visual Languages Computing, 1997, 8(4): 403–424.
[3] Bruns H T, Egenhofer M. Similarity of spatial scenes. In Proc the Seventh International Symposium on Spatial Data Handling, Kraak M J, Molenaar M (eds.), Delft, The Netherlands: Taylor & Francis, August 12–16, 1996, pp.31–42.
[4] Popper K R. The Logic of Scientific Discovery, London: Hutchinson, 1959.
[5] Egenhofer M J. Reasoning about binary topological relations. In Proc. the 2nd International Symposium on Large Spatial Databases (SSD1991), Z¨urich, Switzerland, August 28– 30, 1991, LNCS 525, pp.143–160.
[6] Egenhofer M J, Franzosa R D. Point-set topological spatial relations. International Journal of Geographical Information Systems, 1991, 5(2): 161–174.
[7] Egenhofer M J, Sharma J. Topological relations between regions in R2 and Z2. In Proc. the 3rd International Symposium on Large Spatial Databases (SSD1993), Singapore, June 23–25, 1993, LNCS 692, pp.316–336.
[8] D’Ulizia A, Ferri F, Grifoni P, Rafanelli M. Relaxing constraints on GeoPQL operators for improving query answering. In Proc. the 17th International Conference on Database and Expert Systems Applications (DEXA2006), Krakow, Poland, Sept. 4–8, 2006, LNCS 4080, pp.728–737.
[9] WorldNet 2.1: A lexical database for the English language. 2005, http://www.cogsci.princeton.edu/cgi-bin/webwn.
[10] Lin D. An information-theoretic definition of similarity. In Proc. the 15th Int. Conference on Machine Learning (ICML 1998), Madison, USA, July 24–27, 1998, pp.296–304.
[11] Resnik P. Using information content to evaluate semantic similarity in a taxonomy. In Proc. the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI 1995), Montr′eal, Qu′ebec, Canada, August 20–25, 1995, pp.448–453.
[12] Resnik P. Semantic similarity in a taxonomy: An informationbased measure and its application to problems of ambiguity in natural language. Journal of Artificial Intelligence Research, 1999, 11: 95–130.
[13] Storey V C. Understanding semantic relationships. VLDB Journal, 1993, 2(4): 455–488.
[14] Galil Z. Efficient algorithms for finding maximum matching in graphs. ACM Computing Surveys, 1986, 18(1): 23–38.
[15] G¨uting R H. Geo-relational algebra: A model and query language for geometric database systems. In Proc. the International Conference on Extending Database Technology, Advances in Database Technology (EDBT1988), Schmidt J W, Ceri S, Missikoff M (eds.), Venice, Italy, March 14–18, 1988, pp.506–527.
[16] Lbath A, Aufaure-Portier M A, Laurini R. Using a visual language for the design and query in GIS customization. International IEEE Conference on Visual Information Systems (VISUAL 1997), San Diego, USA, Dec. 15–17, 1997, pp.197– 204.
[17] Ross S. A First Course in Probability. Macmillan, 1976.
[18] Francis WN, Kucera H. Frequency Analysis of English Usage. Houghton Mifflin, Boston, 1982.
[19] Fellbaum C. A semantic network of English: The mother of all WordNets. Computers and the Humanities, 1998, 32(2/3): 209–220.
[20] Jiang J J, Conrath D W. Semantic similarity based on corpus statistics and lexical taxonomy. In Proc. ROCLING X, Taipei, China, August 22–24, 1997.
[21] Rada R, Mili H, Bicknell E, Blettner M. Development and application of a metric on semantic nets. IEEE Transaction on Systems, Man, and Cybernetics, 1989, 19(1): 17–30.
[22] Wu Z, Palmer M. Verb semantics and lexical selection. In Proc. the 32nd Annual Meeting of the Associations for Computational Linguistics, Las Cruces, USA, June 27–30, 1994, pp.133–138.
[23] Miller G A, Charles W G. Contextual correlates of semantic similarity. Language and Cognitive Processes, 1991, 6(1): 1–28.
[24] Schwering A. Approaches to semantic similarity measurement between geo-spatial data — A survey. Transactions in Geographic Information Science, Wilson J P, Fotheringham A S, Hunter G J (eds.), Blackwell Publishing, 2008, 12(1): 5–29.
[25] Janowicz K. Kinds of contexts and their impact on semantic similarity measurement. In Proc. the 5th IEEE Workshop on Context Modeling and Reasoning (CoMoRea 2008) at the 6th IEEE International Conference on Pervasive Computing and Communication (PerCom 2008), Hong Kong, China, IEEE Computer Society, March 17–21, 2008, pp.441–446.
[26] Bozkaya T, ¨Osoyoglu Z M. Indexing large metric spaces for similarity search queries. ACM Transactions on Database Systems, 1999, 24(3): 361–404.
[27] Barbara D, Dumouchel W, Faloutsos C, Haas P J, Hellerstein J M, Ioannidis Y E, Jagadish H V, Johnson T, Ng R T, Poosala V, Ross K A, Sevcik K C. The New Jersey data reduction report. IEEE Data Engineering Bulletin, 1997, 20(4): 3–45.
[28] Han J, Kamber M. Data Mining: Concepts and Techniques. Academic Press, 2001.
[29] Egenhofer M J, Sharma J, Mark D M. A Critical Comparison of the 4-Intersection and 9-Intersection Models for Spatial Relations: Formal Analysis. In Proc. Autocarto 11, Minneapolis, USA, McMaster R, Armstrong M (eds.), Oct. 30–Nov. 1 1993, pp.1–11.
[30] Rodriguez A, Egenhofer M, Blaser A D. Query pre-processing of topological constraints: Comparing a composition-based with neighborhood-based approach. In Proc. the 8th International Symposium on Advances in Spatial and Temporal Databases (SSTD2003), Santorini Island, Greece, July 24– 27, 2003, pp.362–379.
[31] Dylia F, Moratz R. Exploiting qualitative spatial neighborhoods in the situation calculus. In Proc. International Conference on Spatial Cognition, Bremen, Germany, Sept. 24–28, 2006, LNCS 3343, pp.304–322.
[32] Lee J H, Kim M H, Lee Y J. Information retrieval based on conceptual distance in is-a hierarchies. Journal of Documentation, 1989, 49(2): 188–207.
[33] Rodriguez A, Egenhofer M. Comparing geospatial entity classes: An asymmetric and context-dependent similarity measure. International Journal of Geographical Information Science (IJGIS), 2004, 18(3): 229–256.
[34] Maguitman A G, Menczer F, Roinestad H, Vespignani A. Algorithmic detection of semantic similarity. In Proc. the International World Wide Web Conference Committee (WWW2005), Chiba, Japan, 2005, pp.107–116.
[35] Frakes W B, Baeza-Yates R. Information Retrieval, Data Structure and Algorithms. Prentice Hall, 1992.
[36] Formica A, Missikoff M. Concept similarity in SymOntos: An enterprise ontology management tool. The Computer Journal, 2002, 45(6): 583–594.
[37] Formica A. Similarity of XML-schema elements: A structural and information content approach. The Computer Journal, 2008, 51(2): 240–254.
[38] Ferri F, Formica A, Grifoni P, Rafanelli M. Evaluating semantic similarity using GML in Geographic Information Systems. In Proc. the OTM’05 Workshops, Agia Napa, Cyprus, Springer-Verlag Publ., 2005, LNCS 3762, pp.1009–1019.

No related articles found!
Full text



[1] Chen Fang; Shi Baile;. A Conservative Multiversion Locking-Graph Scheduler Algorithm[J]. , 1991, 6(2): 161 -166 .
[2] Liao Xianzhi; Jin Lan;. Rendezvous Facilities in a Distributed Computer System[J]. , 1995, 10(2): 188 -192 .
[3] Fu Yuxi;. Reaction Graph[J]. , 1998, 13(6): 510 -530 .
[4] Zhou Chaochen;. An Overview of Duration Calculus[J]. , 1998, 13(6): 552 .
[5] LI Xiaoshan;. Decidability of Mean Value Calculus[J]. , 1999, 14(2): 173 -180 .
[6] Cliff Reader. AVS Intellectual Property Rights (IPR) Policy[J]. , 2006, 21(3): 306 -309 .
[7] Xin-Fu Wang and De-Bin Zhao. Performance Comparison of AVS and H.264/AVC Video Coding Standards[J]. , 2006, 21(3): 310 -314 .
[8] Wen Zheng, Jun-Hai Yong, and Jean-Claude Paul. Visual Simulation of Multiple Unmixable Fluids[J]. , 2007, 22(1): 156 -160 .
[9] Pierre Bourque, Serge Oligny, Alain Abran, and Bertrand Fournier. Developing Project Duration Models in Software Engineering[J]. , 2007, 22(3): 348 -357 .
[10] Yu-Bao Liu, Jia-Rong Cai, Jian Yin, and Ada Wai-Chee Fu. Clustering Text Data Streams[J]. , 2008, 23(1): 112 -128 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved