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...[ Read more ]

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.