Supporting range queries on Web data using k-nearest neighbor search

Wan D. Bae, Shayma Alkobaisi, Seon Ho Kim, Sada Narayanappa, Cyrus Shahabi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Citations (Scopus)

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.

Original languageEnglish
Title of host publicationWeb and Wireless Geographical Information Systems - 7th International Symposium, W2GIS 2007, Proceedings
PublisherSpringer Verlag
Pages61-75
Number of pages15
ISBN (Print)9783540769231
DOIs
Publication statusPublished - 2007
Event7th International Symposium on Web and Wireless Geographical Information Systems, W2GIS 2007 - Cardiff, United Kingdom
Duration: Nov 28 2007Nov 29 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4857 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other7th International Symposium on Web and Wireless Geographical Information Systems, W2GIS 2007
Country/TerritoryUnited Kingdom
CityCardiff
Period11/28/0711/29/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Supporting range queries on Web data using k-nearest neighbor search'. Together they form a unique fingerprint.

Cite this