4. Egocentric Spatial Queries

It is believed that over 80% of all useful data have a spatial component (Maitra and Andersen 2003) that can be linked to a GIS. If data are not inherently spatial, they most likely have a geographic footprint linking the data to space and time (Beard and Sharma 1997). For example, objects referred by most nouns (persons, places, or things) exist at some place at a certain time. Goodchild (1998) defines a geo-library as a “library filled with georeferenced information,” which is based upon the notion that information can have a geographic footprint. Within such a setting, georeferenced information is broad in scope to include such things as photographs, videos, music, and literature that can be given a locational variable. Most of these spatial data are stored in relational databases that are organized in a panoptic or “birds eye view” format (Raper 2002). This panoptic view format can create difficulties for humans, who have a perspective view that makes their outlook of the world very narrow; therefore, spatial database systems must have a way to translate between the user’s egocentric and the data’s allocentric reference frame.

With today’s technology, users of information systems extract egocentric views of data through queries. Spatial databases provide query results in a panoptic view, which is useful for GISs. In order for the data to be translated to the users’ point of view, however, it is necessary for the users to provide their egocentric references. For example, “I am at the corner of 84th Street and 2nd Avenue facing north. Which direction should I turn to get to the Empire State Building?” This chapter develops a spatial data model that implicitly exploits spatial sensors gathering the user’s egocentric spatial reference frame, so that the user does not have to explicitly input it. Such a query model is needed for advanced location-based services.

The description of the egocentric spatial data model is broken down into three parts: (1) the syntax of the egocentric abstract data type and its use within SQL, (2) the semantics of what the model does and, (3) the execution model of how the system process the egocentric queries.

4.1. Syntax of An Egocentric Spatial Data Model

A data model for egocentric queries is comprised of two components: a data representation structure and data manipulation operations. For example, Codd’s (1970) relational model uses tables to represent the data and the data manipulation is based on mathematical foundations expressed by two formal languages; relation calculus and algebra. In a spatial data model for egocentric queries the spatial data objects are the user’s time-of-query position and orientation. Before a description can be given of how the user’s position and orientation are used to create the egocentric abstract data type, we examine how and why the relational data model has been extended using abstract data types to account for such complex mobile queries by structuring data as objects.

4.1.1. Spatial Data Types For Mobile Queries

In order for a database to process egocentric spatial queries, the database needs to support a data type containing the user’s egocentric spatial reference frame. This data type provides the basis for modeling here and there. Providing a data model with an insight into here and there is essential for egocentric queries, because in order for the data management system to process the queries the system needs to be able to relate the user’s and the data’s reference frames. The term egocentric queries is used for location-based mobile services, in which the user’s spatial reference frame information adds value to the service as a whole (Frost and Sullivan 2003). This term refers to mobile situations where much of the informational needs of users relate to their surroundings (Golledge 1999). The user’s position and orientation are used to create the egocentric ADT, as described in the next section.

4.1.2. The Egocentric Spatial Abstract Data Types

The egocentric spatial ADT is used in the same way as other ADTs. For example, when a town data object is represented in a data base management system this data object could have attributes; name of type variable character, population of type integer, and geo of type geometry as shown in this SQL block:

> Create        Table town(
> name        varchar(30),
> pop        int(30),
> year-inc    int(4),
> geo        geometry);

The egocentric ADT is very similar to geometry ADT. In fact the egocentric ADT inherits properties from the geometry ADT. This inheritence allows the egocentric ADT to be topologically related to the geometry ADT. For instance, a traveler data object could have attributes; name of type variable character, and address of type variable character. The difference between the town’s data object and the traveler’s egocentric data object is town has the attribute geo of type geometry traveler has attribute ego of type egocentric. As shown in this SQL block:

> Create    Table traveler(
> name    varchar(30),
> address    varchar(45),
> DoB    datetime,
> ego    egocentric);

There are three relational tables necessary for the egocentric spatial data model: (1), the egocentric table represents the user’s time-of-query position and orientation, (2) the userSESSION table represents data regarding the sensor’s and data’s accuracy for the querying session, and (3) the userCONTEXT table represents data about the user’s querying traits such as arm used to point (Figure 4.1). These tables are created before hand by the ADT developers. Most of the data are supplied automatically and implicitly by the sensors and metadata about the geospatial dataset, though some attribute for example, the user’s contextual profile are added by the system’s users explicitly.

Figure 4.1: ER diagram of the relational tables composing the egocentric ADT.

The egocentric table models the user’s current geographic position, orientation, and time. In most cases, here will be based on stable GPS or cellular triangulation readings. The egocentric table also accepts orientation angles as input, which represents the user’s current orientation. In many instances the determination of there will be based on the system receiving stable angles from magnetometer, gyroscope and accelerometer based sensors. An example of the egocentric table is shown in the following SQL block:

>  CREATE TABLE egocentric(
>    24, -- ego_id NUMBER PRIMARY KEY,
>    1, -- session_id NUMBER FOREIGN KEY,
>    45.5432156,  -- x-coordinate
>    68.5443433,  -- y-coordinate
>    13.1674934,  -- z-coordinate
>    89.528,  -- yaw angle in degrees    
>    21.367,  -- pitch angle in degrees
>    04-27-2003 10:39:52.32, -- date-time
> );

The concept of there is a method of the egocentric ADT to calculate an object the user is selecting at a distance away from here. Since a system cannot calculate what a user means by there if it does not know what the user means by here, the method of there uses many of the same aspects of the egocentric ADT as the here method. Both here and there utilize the position coordinates x, y, and z. In addition, there uses the compass angle (or yaw) and in many cases the vertical angle (or pitch) in order to decide in which direction and what angel up from the horizon the geospatial objects are that the user is interested.

An important issue to consider when determining the best candidate to satisfy the here and there queries is the context and validity of the attributes that define the egocentric reference frame. For instance, an ontology-based approach (Fonseca et al. 2002) may be used to decide the granularity of the query results based on the accuracy and precision of the sensed spatial attributes, as well as the geographic context of the query.  This ontology-based system is considered future work for extending the userSESSION table, which represents accuracy of the sensors and data. The data of the userSESSION table can be used chose the best granularity level of an egocentric query. For example, a hiker in the Swiss Alps might point at a village and ask, “What is that?” If this hiker is using a consumer grade GPS and orientation sensor the hiker should get a different response at a different granularity level than a soldier using military grade GPS and orientation sensors. For example, the consumers might learn that they pointed at the village Degen, whereas the soldier might learn that he or she pointed at the St. Sebastian church in Degen. With consumer grade sensors it might be more difficult to discern what a user is pointing at, so the response must be at a coarser granularity. Though sensed position, orientation, precision, and accuracy should not be considered the only contextual data used to decide the informational needs of the user, these attributes are valuable as they can be gathered implicitly.

The userSESSION table is used to provide context for a user’s query session. It is also necessary to add validity to the sensed data within the egocentric table. The userSESSION table represents the stored position, orientation, and temporal accuracy information about the query session. The userSESSION table is updated when some querying aspect changes, for example, when the user decides to use information about his or her elevation from one of many different sources. In some cases it is probably better to utilize the user’s elevation value from the digital terrain model, or objects on the model like a building. In other cases it might be best to use the elevation sensed by the GPS, for example if the user is not on the ground. One user can have many query sessions, because it is possible for him or her to use different query configurations. The next SQL block shows the kind of data in the userSESSION table:

> CREATE TABLE userSESSION(
> 1, -- session_id NUMBER PRIMARY KEY,
> 2, -- user_id NUMBER FOREIGN KEY,
> 30, -- x y positional accuracy in feet
> 40, -- z positional accuracy in feet
> 5, -- orientation accuracy in angle degrees
> 5, -- temporal accuracy in seconds
> 1, -- use sensed z Boolean
>);

The third table necessary for the egocentric spatial data model is the userCONTEXT table, which represents the stored data regarding the user’s query context, for example, the hand used for query-by-pointing. Knowing which hand the user points with is necessary to compensate between the angle the user sees they are pointing and the angle the pointing device is actually pointing. Whereas the userSESSION table represents contextual data about the sensed spatial attributes in the egocentric table, the userCONTEXT table provides personal contextual information about the user. In the following SQL block we create the attribute pointing_hand. This stores personal information about how the user performs the query-by-pointing tasks, which is necessary for accurate results.

The userCONTEXT table could be linked to many userSESSION tables and each userSESSION table could be linked to many egocentric tables. Shown is an example of the SQL block to create the userCONTEXT table:

> CREATE TABLE userCONTEXT (
>  user_id NUMBER PRIMARY KEY,  
>  name VARCHAR2(32),
>  pointing_hand VARCHAR2(10)
> );

In the future the egocentric spatial data model should be extended with an ontological driven filter. This ontological filter would use the user’s preferences to choose the semantic information results. For example, the userCONTEXT table could store information about native language spoken, education level, and other interests.

The egocentric ADT is reference differently than spatial geomentry data objects are. Reference queries in GIS can be classified into three categories (Rigaux et al. 2002); (1) queries with alphanumeric criteria, (2) queries with a spatial criterion (i.e., an operation that applies to the spatial part of one or several geographic objects), and (3) interactive queries, which require participation from the user (e.g., to select a particular area by drawing a selection on a display device using a mouse). In the following examples we examine special cases of interactive spatial queries where, instead of users interacting with a computer display, users interact with the environment via their position and orientation. We refer to these types of queries as egocentric queries.

To access and manipulate the egocentric spatial data model a framework of query operations must be defined. The next section performs an analysis of high-level query operations formalizing queries as either here or there. This analysis lays the groundwork for the query execution model described as re-write rules in Chapter 5.

4.1.3. Egocentric Query Operations

In order to develop the query operations using the egocentric ADT, we first describe a framework to classify the types of egocentric spatial queries. This framework is created in a top-down design methodology, starting with the types of questions a user in-the-field might ask. An analysis of the high-level query operations develops an egocentric query classification. Each class has two variants, one query without thematic classification type, the other with the thematic type, such as buildings, specified. The two query operation classes are here, and there (Table 4.1).

Spatial Query    Spatial Operation
Where am I?
In what “x” am I?
What is that?
What “x” is that?    Here spatial operations
Here+ spatial operations
There spatial operations
There+ spatial operations

Table 4.1: Egocentric spatial query operations.

4.1.3.1. Here Operations

The spatial operation here functions with the spatial attributes centered on the position of the user’s egocentric coordinate system. For an egocentric here operation the fundamental SQL block is based on an interactive query-by-position situation. A query-by-position situation would be, “Where am I?” This query uses coordinates from a position sensor and provides information about geographic features relating to the user’s position. For example, a useful result would be, “You are in Room 336 of Boardman Hall.” This is different from a common desktop GIS, where within the query-by-selection situation the user’s primary task is to interact with geospatial information. In the desktop situation the user selects a feature via a computer mouse that generates a query resulting in thematic information about the object. A here query occurs in the field, where the user’s primary task is to interact with the environment and the interaction with a GIS is a secondary task. The user may not want to directly interact with the computing device via keyboard, mouse, or trackpad. An example of a query-by-position SQL block for the “Where am I?” question is:

> SELECT    *.name
> FROM    *
> WHERE    *.geo contains traveler.here;

In this example the user might be using a consumer grade GPS with a known accuracy of 30 feet. This means that the average theme object size needs to be greater than 30 feet, for example a building. This query is described in greater detail in the section on here queries re-write in Chapter 5. This process of transforming a user query into an executable statement is called query re-writing

4.1.3.2. Here+ Operations

In Here+ operations the user specifies the theme type he or she is interested in, for example, a town. This would change a query-by-position question from “Where am I?” to, “What town am I in?” The here+ query classification re-write is examined in Chapter An example of a here+ query-by-position SQL block is:

> SELECT    town.name
> FROM    town
> WHERE    town.geo overlaps traveler.here;

4.1.3.3. There Operations

Many egocentric there operations are based on an interactive query-by-pointing situation. Similar to the here aspect of the egocentric ADT, the there implements a pointing based spatial query-by-selection, which is an extension of the position based query-by-selection. For example, a basic query-by-selection might be “What object is that?” where this object is selected by clicking on it via a computer mouse on a digital map in a desktop-based Graphical User Interface (GUI). In an egocentric query-by-pointing the users are interacting with their surroundings instead of a computer GUI. An example of a query-by-pointing type question would by “What is that?” where that is a feature the user is pointing at. An instance of a there query-by-pointing SQL block is:

> SELECT    *.name
> FROM    *
> WHERE    *.geo overlaps travler.there;

Considerations for egocentric there operations are the query distance and result presentation format. In most instances it will probably be appropriate to sort the query results based on their distance from the point of query (Silberschatz et al. 1999). An example of a sorted question might be, “What is the closest feature this way?” where features are sorted by distance from here. An instance of a distance SQL block is:

> SELECT         *.name
> Order_BY     distance(*.geo, travler.here)
> FROM         *
> WHERE         *.geo overlaps traveler.there;

These query results can also be sorted by other attributes that are of interest to the user, such as size.

Another factor to consider is the extent of the query distance. The way the model is set up now it is theoretically possible for users to ask what buildings are in front of them and receive all the buildings along a geodetic great circle, where the last building listed would be the one right behind them. Though this probably would not happen because a database containing all the buildings on the planet does not exist. What is most likely to happen is for the query distance to be the extent of the viewable dataset. The extent of query distance, however, is based on context (Dey and Abowd 1999), such as the users’ position, whether they are on a mountain peak or at the bottom of a valley. Another distance context is based on theme type, that is, whether the user asks about buildings versus countries. Many users will probably not be interested in objects they cannot see. The visibility distance based on the earth’s curvature is about 30 miles, which also might be the boundary of the maximum query distance.

For there object selection operations the user’s positions is used as a starting point. From this point we form a geometric vector based on the yaw or northing angle and the pitch angle of the user’s orientation. Error propagation is used to convert this vector into a cone, which is used within an algorithm (terrain intersect model) that utilizes three-dimensional data of the environment. This algorithm determines what objects the geometric cone intersects with (e.g., building geometry). The identified object’s data are then augmented with additional information (e.g., name, date built or history). The object’s identification and the augmented information are what the there query of the egocentric provides as output.

4.1.3.4. There+ Operations

There+ operations, like here+ operations, are situations when the user specifies the thematic type he or she is interested in, for example, a mountain. This changes a query-by-pointing question from “What is this? to “What mountain is this?” An example of a there+ query-by-pointing SQL block is:

> SELECT    mountain.name
> FROM    mountain
> WHERE    mountain.geo overlaps traveler.there;

This section described the syntax of the egocentric spatial ADT. Showing an entity-relationship diagram of the data model and how the ADT is created and used within SQL In the next section a description is given of the semantic of what the egocentric ADT is doing.

4..2. Semantics of An Egocentric Spatial Data Model

Section Deleted

4.2.1. Here Semantics

Section Deleted

4.2.2. Here+ Semantics

Selection Deleted

4.2.3. There Semantics

Selection Deleted

4.2.4. here+ Semantics

Selection Deleted

4.3. Egocentric Spatial Subdivisions

Selection Deleted

4.4. Summary

This chapter described the data model for egocentric spatial queries. The first section portrays why and how ADTs are used to extend the standard relational data model. This description of ADTs was followed by the development of the three egocentric spatial ADTs necessary for egocentric spatial queries: egocentric, userSESSION, and userCONTEXT. Next the query operations using these egocentric ADTs are described. There are two types of egocentric spatial queries: here, and there. Each of these query types has two variations: first, when the user does not specify the thematic data classification and second when the user does provide the thematic classification. The four resulting egocentric query operations are here, here+, there, and there+. These query operations provide different results depending on how the spatial features are structured. An analysis of spatial subdivisions is provided to show how egocentric spatial queries operate in the different spatial organization schemes. The query operations are high-level relationships between the egocentric reference and the surrounding’s spatial data reference frame. The next chapter provides re-write rules for the query operations. These re-write rules alleviate the burden of users having to understand the process of egocentric spatial queries directly.