Quality-driven approximate methods for integrating GIS data

ABSTRACT

GIS data distributed in local, state, federal, and private data clearinghouses are being made accessible through the efforts of organizations such as Federal Geographic Data Committee (FGDC) and GeoData.gov. Many database applications, such as disaster management, transportation, and national infrastructure protection, need to access GIS information from such various data sources. In this paper we study how to answer keyword-based spatial queries approximately using information from heterogeneous GIS sources. An example query specifies the region of Orange County and keywords "junior schools," which asks for geospatial objects relevant to junior schools in Orange County. The answers to such a query provided by different sources differ widely in their content and quality. It is computationally expensive to access all the datasets to retrieve all the relevant objects. We develop approximate algorithms for answering such queries based on the local analysis of the query region using space-partitioning techniques. Our methods rank datasets in a partition based on parameters such as their spatial coverage and content matching the query keywords. The quality of the answers keeps improving progressively as we do deeper local analysis. We develop an efficient traversal strategy to maximize the quality refinement within a given time limit. We conducted experiments to evaluate the proposed techniques.

REFERENCES

• 1: DBXplorer: A System for Keyword-Based Search over Relational Databases, Proceedings of the 18th International Conference on Data Engineering, p.5, February 26-March 01, 2002
• 2: A. Balmin, V. Hristidis and Y. Papakonstantinou. ObjectRank: Authority-based keyword search in databases. In Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004.
• 3: M.K. Beard and V. Sharma. Multidimensional ranking in digital spatial libraries. Special Issue of Metadata. Journal of Digital Libraries, Vol.1, No. 1, 1997.
• 4: Omar Boucelma , Mehdi Essid , Zoé Lacroix , Julien Vinel , Jean-Yves Garinet , Abdelkader Bétari, VirGIS: Mediation for Geographical Information Systems, Proceedings of the 20th International Conference on Data Engineering, p.855, March 30-April 02, 2004
• 5: Ching-Chien Chen , Craig A. Knoblock , Cyrus Shahabi , Yao-Yi Chiang , Snehal Thakkar, Automatically and accurately conflating orthoimagery and street maps, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032231]
• 6: Ching-Chien Chen , Craig A. Knoblock , Cyrus Shahabi , Yao-Yi Chiang , Snehal Thakkar, Automatically and accurately conflating orthoimagery and street maps, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032231]
• 7: Mehdi Essid , Omar Boucelma , François-Marie Colonna , Yassine Lassoued, Query processing in a geographic mediation system, Proceedings of the 12th annual ACM international workshop on Geographic information systems, November 12-13, 2004, Washington DC, USA [doi>10.1145/1032222.1032239]
• 8: Federal Geographic Data Committee (FGDC), www.fgdc.gov.
• 9: Hector Garcia-Molina , Yannis Papakonstantinou , Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey Ullman , Vasilis Vassalos , Jennifer Widom, The TSIMMIS Approach to Mediation: Data Models and Languages, Journal of Intelligent Information Systems, v.8 n.2, p.117-132, March/April 1997 [doi>10.1023/A:1008683107812]
• 10: Geospatial-one-stop, www.geodata.gov.
• 11: S. Gobel and P. Klein. Ranking mechanisms in meta-data information systems for geo-spatial data. In Proceedings of EOGEO, Ispra, Italy, 2002.
• 12: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: V. Hristidis, L. Gravano and Y. Papakonstantinou. Efficient IR-style keyword search over relational databases. In Proceedings of the 29th VLDB Conference, Berlin, Germany, 2003.
• 14: Iosif Lazaridis , Sharad Mehrotra, Progressive approximate aggregate queries with a multi-resolution tree structure, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.401-412, May 21-24, 2001, Santa Barbara, California, United States
• 15: J. Radke, T. Cova, M.F. Sheridan, A. Troy, M. Lan and R. Johnson. Application challenges for geographic information science: implications for research, education, and policy for emergency preparedness and response. URISA Journal, Vol. 12, No. 2, Spring 2000.
• 16: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 17: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 18: A. Singhal. Modern information retrieval: a brief overview. IEEE Data Engineering Bulletin, Special Issue on Text and Databases, Vol. 24, No. 4, December 2001.
• 19: S.K. Thomas, S.L. Cutter, M. Hodgson, M. Gutekunst, and S. Jones. Use of spatial data and geographic technologies in response to the September 11 terrorist attack. Quick Response Report #153, Natural Hazards Center, University of Colorado, 2002.
• 20: The RESCUE Project, http://www.itr-rescue.org/.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Spatial databases and GIS

General Terms:
Algorithms, Management

Keywords:
GIS data integration, approximate methods, heterogeneous data sources