Systematic Review of Indexing Spatial Skyline Queries for Decision Support

Introduction

With the fast advancement of portable handset gadgets, wireless communication, and growth of technologies during a decade, Location-based services (LBSs) have succeeded. In modern applications, users search for the points which have Spatial as well as Textual relevance. Users transferring data from location-aware mobile devices can query LBSs for focal points or Point of Interest (POIs) from any place and point. The skyline operator, first proposed by Börzsönyi et al. (Börzsönyi, S., Kossmann, D., & Stocker, K. (2001), aims at point of dominance and how a database system can be extended in order to compute the Skyline of a set of points. Example: A person visiting a city, searches for the places to stay nearby a tourist location. The places of user’s interest consist of some other keywords viz., cheap, vegetarian. The skyline operator takes the user’s interesting keywords and finds the places which meet the criteria cheap, vegetarian.

• Definition - Skyline Query: Given a set of foci { p₁, p₂, .., p_n} the skyline query restores a lot of foci P, called skyline points, with the end goal that any point p_i∈ P isn't dominated by some other point in the dataset. A point p₁ overwhelms another point p₂ if p₁ isn't more regrettable than p₂ in all measurements, and p₁ is superior to p₂, in any event of measurement. A point p₁ rules another point p₂ iff the measure of p₁ on any other is having less metric than the relating coordinate of p₂.

Among the selection of choices of location-based inquiries, one critical part is an area and text-based skyline request. These questions believe both the spatial and non-spatial characteristics of the POIs (Lee & K.C., 2011), (Lin, X., Xu, J., & Hu, H., 2013). Nearest neighbor (NN) search (Hjaltason, G. R., &Samet, H., 1999), (Roussopoulos, N., Kelley, S., & Vincent, F. 1995), invert NN search (Korn, F., &Muthukrishnan, S., 2000) are delegate ones. Over those spatial requests, nonspatial qualities of articles have to be considered for self-decision query criteria. Hence the Skyline queries with spatial context are raising its prominence in the recent days.

(Sharifzadeh, M., & Shahabi, C., 2006), introduced the spatial skyline queries. The spatial skyline queries retrieve the dominance points depending on the user’s location and the distances.

• Definition - Spatial Skyline Query(SSQ): Given a d-dimensional space, P = { p₁, p₂, .., p_n} is the set of points which is associated with D spatial distances, Q = { q₁, q₂, .., q_m} is the set of query points and the two points {p_i, p_i^’} ∈ d-dimensional space, then p_i dominates p_i^’ spatially in terms of the query points Q where D(p_i, q_j) ≤ D(p_i^’, q_j) for all q_j ∈ Q. A point p_i rules another point p_i^’ iff the spatial metric as well the skyline metric is satisfied.

• Example: A tourist just reached Airport, searching for the hotels = {H1, H2, H3, H4, H5, H6, H7} which are nearby Tourist Spot as shown in the Figure 1.

Figure 1.

Example of Hotel Search from Airport which is near to Tourist Spot

From Figure 1, H4 and H7 are the most interested hotels for the tourist. The spatial skyline algorithm should be able to rank the hotels in this order to present the POI of the user.