Location Leveling

Location Leveling

1 Introduction[1]

Location Based Services (LBS) isan emerging application of mobile data services [K06, SDK01a, XZL06]. Using LBS, users with location-aware MobileUnits (MUs)can query about their surroundings anywhere and anytime through Wireless Service Providers (WSPs) and Information Content Providers (ICPs).However, unlike traditional data information services built on wired networks,to successfully deploy such services requires more than just adding delivery functionality and scalability on the top of the supporting infrastructure. While this ubiquitous computing paradigm provides a great convenience for information access, its constraintshave poseda variety of challengesin query processing of location-based services [XZL06]. Moreover as a growing number of traditional systemsareadapted to becomewireless, systems become more and more complex. Middleware solutionshave been proven to be a great benefit in incorporation of delivery featureswith ubiquitous system platforms, system extensibility, targeted wireless devices, back-end legacy systems, data storage, and workflow needs. In this paper we explore a middleware solution to query processing inlocation-based services.

Processing aLocation Dependent Query (LDQ) [SDK01a, SDK01b, SD02] is the key to the LBS. Individuals using MUs,including laptops and PDAs,may access data located at ICPs using database queries. The responses to the mobile queries depend on the location of the user. The LDQ query processing is complicated by the possible heterogeneous location representations and mismatch of the location granularities between WSPs and ICPs. This so calledLocation Granularity Mismatchmay negatively affect location dependent queries (LDQ), and consequently LBSs. Consider the LDQ “Find the closest restaurant” in a LBS. There are at least two data accesses needed to complete this query. In the first access, the location of the MU is obtained from theLoCation Service (LCS)at the WSP. Then the location value is bound to the original query and aLocation Aware Query (LAQ) “Find the restaurants in <default or assigned range>centered at <current location provided by WSP>” is formed. The LAQ is then sent through wireless delivery channels to ICPs. The ICP returnsa response of “A list of restaurants in <the given rangecentered at <current location represented by ICPs>”. A more detailed discussion of LDQ processing can be found in the literature [SDK01a, SDK01b, SD02]. Here two issues are raised beyond simply data delivery. First, the location representations of WSP and ICP may be heterogeneous and mismatched. ExamplesareCellID provided by WSPs and street address by ICPs. Direct translation to a common representation such as longitude/latitude pair has been proposed as a solution in previous work. However this method is not sufficient when legacy systems are incorporated. When direct translation is applied, the common representation will need to be indexed for efficient search. But it is obviously not an optimal solution. Also the inherent restriction of longitude/latitude pair does not allow topologic information, such as river in-between, in mountain, and the 3rd floor in the mall. Secondly the granularities of location representations may not be identical. CellID and address may not be equivalent in location granularity. If the term “closest” is interpreted to be within five miles, the query could be interpreted to be “within 5 miles” of a specific latitude/longitude or cell or zip code and the responses to the query would be different.

Thus a reconciliation solution must be made for this location mismatchfor location dependent query processing.This paper presents a data model, Location Leveling (LL,) that solves the problem in a general pervasive mobile computing environment as a middleware conciliation solution.

We use an architectural model originally presented in [SDK01a] and shown in Figure 1. A middleware component called Location Dependent Services Manager (LDSM)is responsible for conciliating mismatches of the query, determining where to process the query, and compiling results from multiple ICPs prior to returning them to the user at the MU[MUsrequest mobile queries through the wireless network provided by WSPs. The queries are processed at fixed hosts, ICPs. A single query may be processed at multiple hosts and if requested several times could be executed at different sites. Here an ICPrefers to any type of information service providers including legacy systems. We make no restrictions or assumptions on the capabilities of content providers. Also we support the casesthat one query may be processed by multiple content providers. For example, a query: “Find the closest restaurants and hotels” may be processed by two different content providers. Each could use a different location granularity. We do not assume that an ICP is capableof providing the data at any specific granularity. Similarly, not every LCSat WSP side can provide all granularities the content providers support in their database.

This paper is organized as follows. We examine the location mismatch problem in detail in Section 2. Related work is surveyed in Section 3. The location leveling data model is presented in Section 4. The basic LL algorithms and comparisons to existing approaches aregiven in Section 5. Finally the work is summarized in Section 6.

2 Problem Definition

In this section we give formal definitions of the related concepts and the problem. We call the location value assigned by a LoCation Service (LCS) the Binding Location (BL), while the location value used in the content database the Data Location (DL). The BL and DL can take different representations and granularities. Location Leveling is responsible for location “transformation” from the BL to DL for each query. The results of the query andtheir precisions will be affected by the location granularity of the data stored and the transformation technique used. As an example, we use a query: “Find all hotels within five miles of ‘John’ ”. If the operator “within five miles” was interpreted to be a circular area with a radius of five miles centered at ’John’, then a different set of hotels would be given from those if it were interpreted to be rectangular. Moreover, given the same query, if the BL were at a latitude/longitude, a smaller set of hotels would be returned than those if it were a cell or zip code. The actual results depend on granularities of both sides.These issues are solely caused by location dependent queries in ubiquitous environment.

To conciliate the location mismatch in LDQ processing, wepropose a six-step location transformation, as illustrated in Figure 2. We will see thatthese steps aresufficiently general and flexible fora general ubiquitous environment. We briefly introduce the steps as follows:

• Step 1. Issue a query:A mobile or stationary user issues a query when he is actually at Point A.We denote this location at which the queryis issued via the MU client application the Query Location (QL).
• Step 2. Determine location dependency:Location dependency is determined by the type of the operators used, such as “closest” and “straight ahead”. If the query is location dependent, then location binding is required. Otherwiselocation binding is not needed and the query is transferred directly to the service provider.
• Step 3. Location Binding:LCS is queried about the location of the MU at this step. Location binding is the process of replacing the abstract QL location value with a more precise physical location called the Binding Location (BL). Any location representation is possibly used. The latitude/longitude granularity with a value PointB, or in CellID granularity with a value area1are typical examples.BL may be different fromQL.
• Step 4. Spatial Operator Interpretation:The location granularity is dependent on the interpretation of the spatial operator used in the query (such as “nearest”, “within a 5 mile radius”, etc.). .This step, then, converts the BL into a location area within which the query results are to be found. We call this locationthe Interpreted Location (IL). The query is no longer dependent on the location of the MU and then becomes a location aware query [SDK01b].
• Step 5. Location Leveling: Any location mismatch is resolved at this step. When the Data Location (DL) granularity is different from area2’s location granularity, Location Leveling is performed.
• Step 6. Query Submission:At this step, the modified query after LL is ready to besubmitted to the related content data providers.

In Figure 2, location granularities may appear in four different levels: Query Location, Binding Location, spatial operator Interpreted Location, and the Data Location. The step of location binding may sometimes be performed in cooperation with services provided by the location based services. As an example, query can be: “Find the hotels near where I will be in one hour”. Here, the BL is a projection of a future location based on movement direction and speed of the user. The location services would have to find the current location, and predict future location using sophisticated prediction techniques. This additional prediction process may not be performed by the location services but rather by the LDSM middleware. Although this extra work should not impact the actual location granularity, it could change the precise location to which the MU is associated.

Many different types of spatial operators may be used in these queries: distance based (within five miles), overlap (within my movement path), straight ahead, etc. When the spatial operator is examined, it may be required to change the BL. For simplicity, in this paper we usually assume the IL = BL.

We conclude this section with an example that highlights the various locations and issues presented.

Example 1. This example illustrates the process of the six step location transformation using two different BLs and two different operators. The two BLs are latitute/longitude pair and zipcode, and the two spatial operators are closest and straight ahead. We assume the “closest” operator is interpreted as a circular area with radius 5 miles from PointB, and the “straight ahead” operator is interpreted as a rectangular area with length 5 miles (longest edge of the rectangle is 5 miles) in the direction of movement. Table 1 summarizes the different location granularities used in each stage of the query translation process.

Suppose, we have a workspace W, that is partitioned into 5 zipcodes, {Z1, Z2, Z3, Z4, Z5}, and two states, {S1, S2}. For a query “Find the closest/straight ahead Hotels within 5 miles”, the four combinations of query interpretation using two different location bindings and two operator interpretations are shown in Figures 3 a), b), c) and d). The closest operator is interpreted as a circular region around the BL. For the latitude/longitude binding this is a circle and for the zipcode binding this is a region 5 miles around the zipcode Z5. The straight ahead operator results in a rectangular region in the area of movement for the latitude/longitude binding, but for the zipcode binding this is the area in front of the movement direction 5 miles around the Zipcode Z5. As the content provider provides information at the state level, the intersection of the IL with states gives an answer of hotels in state S1 for latitude/longitude binding, and those in S1 or S2 for zipcode binding.

3 Related Work

In this section we present related work in the areas of location dependent queries, location translation, and location modelingas found in previous literature.

3.1 Location Dependent Queries

We have examined the overall process and proposed an architecture to support the processing of location dependent queries [SDK01b, SDK01a]. In the work we differentiated 7 different types of location queries. Location Aware Queries (LAQ)results dependent on location but are independent of the user’s current location. An example of a LAQ would be: “Find all Italian restaurants in Dallas” Compare this to a LDQ: “Find the closest Italian restaurants” A LAQ does not require that the MU be bound to a location. Therefore, LAQs do not require any location translation or leveling process at all. A LDQ differs from the others in that a Location Related (LR)operator (such as near, closest) may be used. In addition, these queries do not specifically have a location attribute. An implied location, that to which the query is bound, is included.

Another related type of mobile query is referred to as a Moving Object Database Query (MODQ)[SWCD97, WXCJ98, Wol02]. These types of queries assume that not only is the query originator moving, but so is the object of which the query is being asked. An example of a MODQ is: “Find the closest automobiles manufactured by GMC” Here the automobiles are moving as is the MU from which the query is being requested. In fact the MODQ can be viewed as a generalized LDQ. Three types of special MODQs have been identified in [SWCD97]: instantaneous, continuous, and persistent. These may or may not actually be LDQs. However, the location leveling process would be needed by all of these types of queries. A major difference between LDQs and MODQs is that a location binding may have to be performed on both the MU from which the query is being asked as well as the object being queried. In the above example, the target automobiles will have to be bound to a location as will the MU. In this example, no LL is needed assuming that the same binding process and location granularity are used.

MOD Queries are part of the ongoing research in Moving Object Databases (MOD)[Wol02]. Not only is examining queries in the domain important, but so are many other aspects. Research areas include location modeling, trajectory prediction and usage, and new operators for queries[Wol02, TWHC04, XW03]. The trajectory management project is crucial for processing not onlyMOD queries but also LDQs. An accurate prediction of the future location of an MU is needed to bind the query to a future location. Although there is much work in the area of MODs we are not aware of any work in the translation of location granularities. Thus not only is much of the MOD research applicable to LDQs, but much of our LL work is applicable to processing MODQs.

3.2 Location Translation

Geocoding is an automated process that is used in Geographic Information Systems (GIS)to translate the implicit references, such as addresses, to explicit geographic references, such as latitude/longitude [EG03]. “Geocoding is the process of assigning geographic coordinates (latitude/longitude) to data” [Map00]. Typical geocoding algorithms parse a street address into several components and then use these components to find matches or near matches in a database [Map00]. We view Geocoding as a special case of location leveling.

The term location translation has been previously used to describe this leveling process [Sig00].However, translation provides very limited capabilities. The possible set of locations at both thequery and content provider sides is limited and known a priori. The translations are well defined andeither hard coded or described by a precise mapping function. We have seen this approach used by SignalSoftCorp in its “local.info” translations, which includes cell to latitude/longitude, latitude/longitude to zones,zones to URL, and latitude/longitude to common description (address) [Sig00]. With LocationLeveling, the different granularities are not known a priori. Thus, the Location Leveling processmust not only determine the BL and DL, but also figure out how to translate the query fromthe BL to DL. In addition, one LDQ could be decomposed into multiple queries to be executedat multiple content provider sites. Thus, multiple DLs may be used. As our approach is generaland applicable to any granularities, the translation can be viewed as a specialized subset of thecapabilities provided by location leveling algorithms.

3.3 Modeling

Leonhardt [Leo98] proposed a location model for a Location Service. The geometric -“coordinate system” representation of the locations and the symbolic - “names and their relationships”representation are integrated into his model as Semi-symbolic. Higher levels of abstraction are viewed as symbolic (names and relationships) and the lower levels are viewed in a geometric representation. We envision a similar location hierarchy independent of any location service. As described in [Leo98], location concepts are partially ordered by the “contains” relationship, reflecting the spatial inclusion of the associated geographical areas, and how they may overlap. We thus use a Location Directed Acyclic Graph (DAG), to represent the location concepts and their relationships.

Jose [Jos01] has indicated that location concept relationships can be either “Containment” or “Adjacency”. Containment is a unidirectional relation between location concepts, whereas adjacency is the immediate physical proximity. Jose [Jos01] assumes no partial containment in location hierarchies in integration of different location sources in a service based framework. We define both total and partial containment relationships in our work.

Location hierarchies are also considered concept hierarchies. Concept hierarchies are data or application specific since they define mapping rules between different levels of concepts. In the Concept Hierarchies categorization presented by Lu [Lu97], Schema type is defined as a partial order to reflect relationships among attributes. Therefore, one can also see the Location DAG as a “Schematic Concept Hierarchy”.

A query processing model that uses context hierarchies and summary databases is presented in [MMR98]. The model is designed for a mobile computing environment to facilitate the disconnectivity, low bandwidth and limited storage space problems. The paper also mentions a query conversion process to perform the summarization of the data that resembles our query translation steps in the LDSM. However, the work only considers the generalization or moving to a higher level concept in the graph location hierarchy and thus themodel can only represent coarser granularities.

Modeling the movement of objects using multiple granularities has been seen in [HE02]. Both spatial and temporal granularities are considered. They specifically look at an individual’s geospatial lifeline which can be viewed as a history of locations and corresponding timestamps where this individual has been. Different granularities can result due to different frequencies of sampling an individual’s location and the speed at which the location changes. More frequent sampling results in more detail and finer granules. The granularity of an individual’s lifeline can be refined or coarsened. The authors formally examine these issues, however, no algorithms to do the conversions are provided.

Location hierarchies have been seen as the aggregation levels in multidimensional data modeling. Aggregation in Multidimensional Data modeling can be considered the conversion from a fine level concept to a coarser level concept [AGS97]. From the coarser concept accessing the finer concepts brings the Specialization to the conversion process. Drill-down operation displays detail information for the aggregation levels that is for the specialization [AGS97].Aggregation semantics, granularity usage and imprecision in multidimensional data were defined in Pedersen’s studies [PJD99, Ped00, PJD01]. The partial containment relationship in multidimensional data has also drawn attention in the database community. A spatiotemporal data model has been studied in [KRSO01], where the semantics related to granularities are used in a conceptual model. A survey of multidimensional data models is presented in [ASS01].