Advanced Algorithms for Spatial-Temporal Interactions in Distributed GIS Environments

Lin Liu*, Raj Bhatnagar**
*Department of Geography

**Department of Department of Electrical and Computer Engineering and Computer Science

University of Cincinnati

Cincinnati, OH 45221

Contact Information

Lin Liu
Department of Geography

University of Cincinnati

Cincinnati, OH 45221-0131

Phone: (513) 556-3429, Fax : (513) 556-3370
Email: lin.liu@uc.edu

URL: http://www.geography.uc.edu/~linliu

 

Raj Bhatnagar
Department of Electrical and Computer Engineering and Computer Science

University of Cincinnati

Cincinnati, OH 45221

Phone: (513) 556-4932, Fax : (513) 556-7326
Email: Raj.Bhatnagar@uc.edu

URL: http://www.ecece.uc.edu/~rbhatnagar

WWW PAGE

URL: http://www.geography.uc.edu/~linliu/NSF02-03.html

List of Supported Students and Staff (optional)

Xuguang Wang, Xingyou Zhang, Ph.D. students in Department of Geography
Shalini Batra, an M.S. student and Ahmed Khedr, a Ph.D. student in Department of Electrical and Computer Engineering and Computer Science

Project Award Information

Keywords

Data mining, GIS, distributed environments, spatial-temporal interactions

Project Summary

Many algorithms and applications in geographic information systems (GIS) have been designed with the assumption that all the required data is available at a single computer site. Some of these algorithms require tremendous amounts of data to be handled by the algorithms. Typically, all this data is available in a number of databases residing at different nodes of a computer network. One could transfer all the databases to one single computer site and then run the algorithms with the combined databases. However, data storage capacity, privacy and ownership of data, compatibility of different database formats, etc. are some considerations which prohibit the transfer of many databases to one single site. In the emerging networked knowledge infrastructure it is now possible to link the databases by communication networks and perform computations in a distributed mode.  That is, we must design algorithms that can decompose their computations to suit the network locations of various components of data, execute sub-computations at participating nodes, and compose the results to form the results. Such decomposition is made complicated by the arbitrary manner in which the data attributes may be distributed and partially overlapping across the nodes participating in a computation. The pattern of distribution and overlap may be different for each instance of computation depending on the nodes participating in each instance of the computation. This research focuses on the study of spatial interactions in distributed database environments.

Publications and Products (for the past year)

·         Raj Bhatnagar and Wen Niu. Mining Temporal Databases for Subsequence Patterns. Proceedings of the SIAM Data Mining Conference held in San Francisco, May 2003.

·         Raj Bhatnagar, Goutham Kurra and Wen Niu. Mining High Dimensional Data for Classifier Knowledge. To appear in the proceedings of the KDD 2003 conference to be held in Washington DC, 2003.

·         Liu, L., X. Zhang, S. Sivaganesan. “Spatial Interaction Modeling of US Interstate Migration Flows: A Bayesian Approach,” accepted for publication in the proceedings of GeoInformatics ‘2003, Toronto, June 25-28. 2003. (conference cancelled due to SARS)

·         Liu, L., X. Wang. “Simulating Street Robbery Using Cellular Automata and Routine Activity Theory,” accepted for publication in the proceedings of GeoInformatics ‘2003, Toronto, June 25-28. 2003. (conference cancelled due to SARS)

Project Impact

The impact of the project include:

Goals, Objectives, and Targeted Activities

For the past 12 months, the foci of the project have been the following:

In the upcoming year, the project will be focused on the following tasks:

Project References

URL: http://www.geography.uc.edu/~linliu/NSF02-03.html

Area Background

The project crosses the boundaries of multiple disciplines that include computer science and geography, among others. Within computer science, this project is particularly related to the areas of inductive learning, database systems, and algorithm design. It is important to point out that our network algorithm does not require any shared memory, it is therefore different from most parallel algorithms that are based on shared memory. Within geography, this project is closely related to web-based geographic information systems (GIS) and spatial-temporal interactions. Web GIS has primarily been used as a data warehouse which allows simple querying. Analysis of datasets that are partitioned and reside on multiple nodes of a computer network has not been possible without downloading all the data sets to a single site. Spatial-temporal interaction related phenomena are the focus of this project. Specifically we study migration and crime because both are driven by interaction and they vary in space and time.

Area References

Barbosa, Valmir C. An Introduction to Distributed Algorithms, MIT Press, 1996.

Taaffe, E.J., H. L. Gauthier and M.E. O’Kelly. Geography of Transportation. Prentice Hall. 1996.

Potential Related Projects

This project may lead to future collaborative projects with Criminal Justice Division at University of Cincinnati for mining distributed crime data. There is an on-going project between the two units on studying the spatial-temporal patterns of police traffic stops in Cincinnati.

Exploration of decomposable algorithms for mining distributed genomic databases. Initial investigation in collaboration with College of Medicine has already started. 

  *All award information can be found on the on the NSF on-line Awards
Abstracts system, http://www.fastlane.nsf.gov/a6/A6Start.htm.
 

Back to the IDM '02 homepage