Change search
ReferencesLink to record
Permanent link

Direct link
Keyword Search on Spatial Network Databases: Road network indexing for efficient query processing
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Computer and Information Science.
2011 (English)MasteroppgaveStudent thesis
Abstract [en]

Given a spatial location and a set of keywords, a spatial keyword query locates spatio-textual objects based on both the location of the objects, and the textual relevance of the query keywords to the description of the objects. Spatial keyword queries can be used to answer challenging questions such as finding the nearest spatio-textual object relevant for the query keywords "restaurant sushi". Our focus in this project is on a new type of spatial keyword query that takes a road network into account during query processing. These queries are based on the fact that the distance between two objects in the real-world are constrained by the pre-defined paths that comprise the road network. Different from traditional spatial keyword queries that employ the Euclidean distance, the spatial keyword query on road networks assumes the shortest path between the query location and the objects. Unfortunately, no approach currently exists that supports processing of spatial keyword queries on road networks. In this thesis we address the challenging problem of locating spatio-textual objects in a road network given a spatial location and a set of keywords. We first propose a baseline framework that combines existing state-of-the-art approaches to support processing of keyword-based spatial queries such as range and k-nearest neighbour on road networks. Then, we present a novel framework termed Road Network Indexing (RNI) that permits efficient processing of such queries by indexing the spatio-textual objects in each road segment using inverted files. Moreover, we present algorithms to evaluate keyword k-nearest neighbour and keyword range queries on both the baseline and the RNI framework. Finally, we show through an experimental evaluation using real-world datasets, that our RNI framework performs nearest neighbour queries on road networks in around one order of magnitude faster than the baseline approach in terms of response time and I/O.

Place, publisher, year, edition, pages
Institutt for datateknikk og informasjonsvitenskap , 2011. , 80 p.
Keyword [no]
ntnudaim:5756, MTDT datateknikk, Data- og informasjonsforvaltning
URN: urn:nbn:no:ntnu:diva-13689Local ID: ntnudaim:5756OAI: diva2:441757
Available from: 2011-09-19 Created: 2011-09-19

Open Access in DiVA

fulltext(1090 kB)619 downloads
File information
File name FULLTEXT01.pdfFile size 1090 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(47 kB)45 downloads
File information
File name COVER01.pdfFile size 47 kBChecksum SHA-512
Type coverMimetype application/pdf

By organisation
Department of Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 619 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 75 hits
ReferencesLink to record
Permanent link

Direct link