Supporting Range Queries on Web Data Using k-Nearest Neighbor Search

Abstract. A large volume of geospatial data is available on the web through various forms of applications. However, access to these data is limited by certain types of queries due to restrictive Web interfaces. A typical scenario is the existence of numerous business web sites that provide the address of 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, the provided web interface makes it very difficult to retrieve this data set. We conceptualize this problem as a more general problem of running spatial range queries by utilizing only k-Nearest Neighbor (k-NN) queries. Subsequently, we propose two algorithms to cover the rectangular spatial range query by minimizing the number of k-NN queries as possible. Finally, we evaluate the efficiency of our algorithms through empirical experiments.