Web data retrieval: solving spatial range queries using k-nearest neighbor searches

As Geographic Information Systems (GIS) technologies have evolved, more and more GIS applications and geospatial data are available on the web. Spatial objects in a given query range can be retrieved using spatial range query − one of the most widely used query types in GIS and spatial databases. However, it can be challenging to retrieve these data from various web applications where access to the data is only possible through restrictive web interfaces that support certain types of queries. A typical scenario is the existence of numerous business web sites that provide their branch locations through a limited “nearest location” web interface. For example, a chain restaurant’s web site such as McDonalds can be queried to find some of the closest locations of its branches to the user’s home address. However, even though the site has the location data of all restaurants in, for example, the state of California, it is difficult to retrieve the entire data set efficiently due to its restrictive web interface. Considering that k-Nearest Neighbor (k-NN) search is one of the most popular web interfaces in accessing spatial data on the web, this paper investigates the problem of retrieving geospatial data from the web for a given spatial range query using only k-NN searches. Based on the classification of k-NN interfaces on the web, we propose a set of range query algorithms to completely cover the rectangular shape of the query range (completeness) while minimizing the number of k-NN searches as possible (efficiency). We evaluated the efficiency of the proposed algorithms through statistical analysis and empirical experiments using both synthetic and real data sets.

Cyrus ShahabiEmail:

---

Wan D. Bae   is currently an assistant professor in the Mathematics, Statistics and Computer Science Department at the University of Wisconsin-Stout. She received her Ph.D. in Computer Science from the University of Denver in 2007. Dr. Bae’s current research interests include online query processing, Geographic Information Systems, digital mapping, multidimensional data analysis and data mining in spatial and spatiotemporal databases. Shayma Alkobaisi   is currently an assistant professor at the College of Information Technology in the United Arab Emirates University. She received her Ph.D. in Computer Science from the University of Denver in 2008. Dr. Alkobaisi’s research interests include uncertainty management in spatiotemporal databases, online query processing in spatial databases, Geographic Information Systems and computational geometry. Seon Ho Kim   is currently an associate professor in the Computer Science & Information Technology Department at the University of District of Columbia. He received his Ph.D. in Computer Science from the University of Southern California in 1999. Dr. Kim’s primary research interests include design and implementation of multimedia storage systems, and databases, spatiotemporal databases, and GIS. He co-chaired the 2004 ACM Workshop on Next Generation Residential Broadband Challenges in conjunction with the ACM Multimedia Conference. Sada Narayanappa   is currently an advanced computing technologist at Jeppesen. He received his Ph.D. in Mathematics and Computer Science from the University of Denver in 2006. Dr. Narayanappa’s primary research interests include computational geometry, graph theory, algorithms, design and implementation of databases. Cyrus Shahabi   is currently an Associate Professor and the Director of the Information Laboratory (InfoLAB) at the Computer Science Department and also a Research Area Director at the NSF’s Integrated Media Systems Center (IMSC) at the University of Southern California. He received his Ph.D. degree in Computer Science from the University of Southern California in August 1996. Dr. Shahabi’s current research interests include Peer-to-Peer Systems, Streaming Architectures, Geospatial Data Integration and Multidimensional Data Analysis. He is currently on the editorial board of ACM Computers in Entertainment magazine. He is also serving on many conference program committees such as ICDE, SSTD, ACM SIGMOD, ACM GIS. Dr. Shahabi is the recipient of the 2002 National Science Foundation CAREER Award and 2003 Presidential Early Career Awards for Scientists and Engineers (PECASE). In 2001, he also received an award from the Okawa Foundations.