HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5807
Title: K-nearest-neighbor queries with non-spatial predicates on range attributes
Authors: Wong, Wing Sing
Issue Date: 2005
Abstract: Spatial databases have interesting real-life applications with high demands in the area of geographic information system (GIS), transport monitoring, network monitoring and VLSI (chip design). Most of the existing work on spatial databases does not consider range attributes of the spatial entities. However, in real-life spatial applications, spatial entities are queried based not only on spatial constraints but also on conditions imposed on non-spatial attributes that may contain ranges of values instead of single values. One natural and useful query is to "find the 10 nearest restaurants, with expenditure from US$40 to US$60". This query is like a traditional 10-nearest-neighbor query, but there is an additional constraint that the "expenditure is from US$40 to US$60," which is the non-spatial aspect of the spatial entities (restaurants). It is noticed that the non-spatial condition is a range, which makes the question more interesting. Current approaches would find the nearest-neighbor result first (filter step) and then examine their non-spatial attribute to verify that the result matches the non-spatial constraint (refinement step). The results returned by this traditional approach are sorted only in ascending order of their distances. However, a better approach would be to compute a composite score based on distance and the degree of range overlap according to the user's preference and to sort the results in ascending order of these composite scores. In this thesis, a solution to support nearest-neighbor queries with non-spatial range predicates is described. Simulation result shows that the proposed solution reduces the I/O and CPU cost compared to a naìˆve approach.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2005
x, 61 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 2005 WongW
URI: http://hdl.handle.net/1783.1/5807
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.