Spatial Preferences
Spatial preferences are a new type of base preference operating on spatial objects. Given a query geometry gq, data geometries di which are best matches according to the spatial relevance defined by the preference constructor are retrieved. The Preference SQL data model accordingly supports objects of datatype Geometry for di which are stored in an underlying PostgreSQL database with PostGIS support. The latest version of Preference SQL also supports spatial preferences for Oracle Spatial. The Preference SQL query model specifies geometries gq according to the KML standard.
Spatial Base Preference Constructors
As subconstructors of the SCORE preference, all spatial preferences also use a scoring function f=dist(g_q , d_i) to evaluate spatial relevance. This function can be specified in the preference constructor. The following functions are available:
- ST_Distance: minimum Euclidean Distance dist(g_q, d_i)
- ST_MaxDistance: maximum Euclidean Distance dist(g_q, d_i)
- net_dist: Road Network Distance dist(g_q, d_i)
NEARBY
(A, lon, lat, d, c, f, SV)
Given a spatial attribute A of type Geometry, the NEARBY constructor expresses a preference for values di of that attribute that are of shortest distance to the query point gq with WGS 84 coordinates (lon, lat) as specified by the constructor. To define this distance, the provided function f is used. If this optional parameter isn't present, the standard minimum Euclidean distance (see implementation details ) is used.
The images pictures a screenshot of a web application that lets users specify query points intuitively by setting markers on a map.
Example: Finding a restaurant close to the current user location.
WITHIN
(A, KML, d, c, f, SV)
Given a spatial attribute A of type Geometry, the WITHIN constructor expresses a preference for values d_i of that attribute that are located within the query polygon g_q specified by the KML string of the constructor. If no such objects exist then the objects with closest distance as measured by the provided f function are favored. As default function the minimum Euclidean distance is used.
The images pictures a screenshot of a web application that lets users specify query objects intuitively by drawing polygons on a map.
Example: Finding suitable hotels within a preferred city district.
ONROUTE
(A, KML, d, c, f, SV)
Given a spatial attribute A of type Geometry, the ONROUTE constructor expresses a preference for values d_i of that attribute that are located on a query linestring g_q specified by the KML string of the constructor. If no such objects exist then the objects di with closest distance as measured by the provided f function are favored. As default function the minimum Euclidean distance is used.
The images pictures a screenshot of a web application that lets users specify query objects intuitively by drawing linestrings on a map.
Example: Finding an apartment located alongside a popular part of a road.
BUFFER
(A, KML, d, c, f, SV)
Given a spatial attribute A of type Geometry, the BUFFER constructor expresses a preference for values d_i of that attribute that are NOT located within the query polygon g_q specified by the KML string of the constructor. However, objects d_i with closest distance as measured by the provided f function are favored. As default function the minimum Euclidean distance is used.
The images pictures a screenshot of a web application that lets users specify query objects intuitively by drawing polygons on a map.
Example: Finding an accommodation close to but not directly at a crowded place.
Dual Spatial Preferences
As for any other base preference, the complex DUAL constructor can be applied to a spatial preference to reverse the order of that preference. This has the following effects on the semantics of base preferences:
- NEARBY: points that are of maximum distance to the query point are preferred
- WITHIN: points with maximum distance to the query polygon are preferred
- ONROUTE: points with maximum distance to the query linestring are preferred
Impact of the d-parameter and c-parameter
With respect to the evaluation of spatial base preferences, values d_i of the database that are closest to g_q are considered as best matches. However, Location-Based Services often demand some tolerance in query results, especially when it comes to complex preference queries featuring multiple user wishes. Users e.g. would tolerate POI that are a little bit further away from the current location but perform better considering other attributes. Furthermore, the user location itself is error prone due to GPS impreciseness. Hence, Preference SQL provides a d-parameter and a c-parameter which are especially applicable in these scenarios.
Let's consider a NEARBY preference with and without d-parameter as illustrated in the following image.
Without d-parameter in figure a) only the closest data point d_i is returned with respect to this single base preference. In contrast, two data points are retrieved when using a d-parameter in figure b). In this example, Euclidean distance is used as distance function leading to concentric circles of width d.
The next images illustrates the effects of the d-parameter on a WITHIN preference.
In the figure below a polygon around the stadium of the University of Texas at Austin is used as query object g_q. For reasons of simplicity only 4 data points are considered that are representing restaurants. Perfect matches are located within the query polygon. Since no such data point d_i exists the food court at the West Mall would be returned if no d-parameter is specified. With a suitable d-parameter, restaurants on Guadalupe Street would also be retrieved and we might finally get a burrito from Chipotle there.
Finally, the d-parameter is also useful for ONROUTE preferences as the next scenario illustrates.
In the figure below a linestring representing parts of East 6th Street in Austin, TX, USA, is used as query object g_q. Looking for suitable parking spots along that part of the street it becomes obvious that no direct parking is possible. In this case, parking lots closest to this linestring are retrieved. A d-parameter can further be used to define equivalence classes.
The c-parameter specifies an upper boundary for equivalence classes. All classes that exceed that boundary are merged into one. This behavior is especially useful when it comes to spatial preferences. Let's consider a NEARBY preference with a d-parameter of 100. In this case we are looking for results that are preferably close to our current location. A perfect match would be located directly at our location. The next best matches are located within 1 and 100 meters of our location, then 101 to 200 meters, and so on. If results are more than 500 meters away we want them to be equally good / bad because we do not want to walk that far anyways. So we set the c-parameter to 6 and get the desired behavior.
Implementation
For distance calculations, Preference SQL uses the distance functions provided by PostGIS such as ST_Distance or ST_MaxDistance. Network distance is implemented as additional function based on pgRouting. Which distance function should be used for evaluation can be determined by an optional f function string that every spatial constructor accepts. If no value is provided, ST_Distance is used as default. Spatial objects are stored in SRID 3785, a spatial reference system that provides meter as units of measure. While NEARBY uses separate float parameters for the input of latitude and longitude of the desired point in the constructor, all other spatial base preferences take a KML string as argument. This string only needs a stripped KML representation of the desired object, in a form that is in compliance with ST_GeomFromKML. In this KML string, coordinates in WGS 84 format are used.
Complex Spatial Preferences
Spatial preferences can be combined with any other base preferences to form complex preference terms. This flexibility leads to a whole set of possible application areas. In Location-Based Services, often spatial objects that also satisfy some non-spatial criteria are of interest. The combination of several spatial preferences in combination with non-spatial preferences can be useful for Spatial Analysis problems such as location planning. Furthermore, the combination of NEARBY preferences via complex Pareto constructors points out another solution for basic Spatial Skylines. The notion of group queries as defined by spatial skylines can further be extended to complex Group Preference terms by combining complex user preferences via Pareto constructors.
Application Areas
As already pointed out, various application areas can be identified that draw immediate benefits from the application of spatial preferences.
Location-Based Services
In Location-Based Services (LBS) data points such as Points of Interest (POI) are are favored that are close to the current location and additionally fulfill some other criteria. This search query can be modeled via the NEARBY constructor in combination with non-spatial base preferences combined by complex constructors. The resulting complex Preference SQL query returns all data points that are best matches. In contrast to conventional SQL queries, no hard search radius is defined, so POIs that are further away but satisfy other search criteria might still be retrieved. Given the example of free parking lots close to 6th Street in Austin, TX, we might get parking lots that are relatively close to 6th Street but are definitely not free of charge on one hand and free parking lots that are further away of 6th Street on the other hand.
Spatial Analysis
Complex spatial preferences can be used to perform spatial analysis in domains such as location planning. Looking for a new location to build an apartment complex, spatial preferences as well as non-spatial preferences emerge. The location should e.g. be close to the inner city but as far away from any industrial complex as possible. It should further be within a certain city district, close to convenience stores, and if possible along a desirable part of the main street. Additionally, the price per square meter should be as low as possible and the area should be labeled as "desirable". This task incorporates spatial base preferences as well as numerical and categorical base preferences. These base preferences can further be arranged according to priorities with complex preference constructors. This preference term can then be used to display the locations of the database that are best matches for the specified problem.
Spatial Skylines
In the basic definition of Spatial Skylines a set of query points and a set of data points is given. While query points represent the current location of multiple individuals, data points stand for spatial objects of interest that are stored in the database. The task is to find those data points that are best matches for all provided query points. Application areas for Spatial Skylines range from simple restaurant finders to public transportation and military interests. NEARBY preferences in combination with complex Pareto constructors can be used for efficient Spatial Skyline computation. As an extension of the original problem, not only query points can be specified but even more complex query objects such as polygons and linestrings via WITHIN and ONROUTE base preferences.
Group Preferences
Spatial Skylines are already defining some sort of group preference. This preference can be modeled in an even more complex fashion. First, user preference terms are formed that incorporate all kinds of base preferences combined by complex preference constructors. These single users are then again combined via complex preference constructors to form the group preference term. By choosing different complex constructors even group hierarchies can be modeled. If the preference terms of two individuals are e.g. combined via a Pareto constructor then those two users are of equal importance. In contrast, by choosing Prioritization as complex constructor the first individual is becoming the leader of the two users involved. In this fashion, complex group preferences consisting of spatial and non-spatial base preferences can be constructed since Preference Algebra allows multiple preferences referring to the same attribute.