Location-based Skyline queries select the nearest objects to a point that best meet the user's preferences. Particularly, this chapter focuses on location-based Skyline queries over web-accessible data. Web-accessible may have geographical location and be geotagged with documents containing ratings by web users. Location-based Skyline queries may express preferences based on dynamic features such as distance and changeable ratings. In this context, distance must be recalculated when a user changes his position while the ratings must be extracted from external data sources which are updated each time a user scores an item in the Web. This chapter describes and empirically studies four solutions capable of answering location-based Skyline queries considering user's position change and information extraction from the Web inside an area search around the user. They are based on an M-Tree index and Divide & Conquer principle.
TopIntroduction
Skyline queries allow to filter large amounts of data returning a set of data that best meet the user’s preferences. Initially, the problem of computing the Skyline was known as Pareto curve or maximal vector computation (Bentley, Kung, Schkolnick, & Thompson, 1978; Kung, Luccio, & Preparata, 1975). Given a set of vectors, the problem of the maximal vector computation consists in identifying the set of non-dominated vectors; a vector dominates another vector if is better or equal in all coordinates and better in at least one coordinate.
Subsequently, Spatial Skyline Queries (SSQ) and location-based Skyline queries were introduced in (Kodama, Lijima, Guo, & Ishikawa, 2009; Sharifzadeh & Shahabi, 2006). SSQ (Sharifzadeh & Shahabi, 2006) allow spatial data and the user’s criteria are composed of the distances from spatial data (usually interesting places) to a set of points (usually users’ locations). Location-based Skyline queries (Kodama et al., 2009) select the nearest objects to a point (usually a user’s location) that best meet the user’s criteria. Particularly, this chapter focuses on location-based Skyline queries over web-accessible data. Under this scenario, data may change their values through time.
To illustrate the problem presented in this chapter, consider a tourist in Barcelona, Spain. He goes throughout the city to find the restaurant that best meets his preferences. The tourist’s preferred restaurants are those that have the shortest distance from his current location, and the best service quality, food and price; the restaurants must be within a range of 500 meters distance from his current position.
Location-based Skyline queries may be used to identify the restaurants preferred by the tourist. The Location-based Skyline is defined as the set of non-dominated points (restaurants); a point A dominates a point B based on a set of attributes C if A is better than B in all attributes of C, and is better in at least one attribute of the set C.
Figure 1 graphically shows the restaurants belonging to Location-based Skyline from the initial region R1. In Figure 1, the region inside the circle, R1, delimits an area of 500 meters established by the tourist; the location-based Skyline are highlighted inside the region R1. The middle point of R1 represents the tourist’s current location and the arrows indicate the direction in which the tourist will move.
Figure 1. Location based-Skyline from the region R1
Table 1 contains information on each restaurant. Each restaurant has an identifier (ID), the distance in meters (D) between the tourist’s current location and the restaurants, the service quality (S) and the food quality in relation to price (P). The values of S and P are between 0 and 100, where 100 indicate the highest quality.
Table 1. | ID | D | S | P |
| A | 460.3 | 80 | 88 |
| B | 462.5 | 95 | 82 |
| C | 318.9 | 76 | 78 |
| D | 451.8 | 92 | 77 |
| E | 403.2 | 90 | 85 |
| F | 440.5 | 88 | 83 |