Project Topics
Get Complete Project Material File(s) Now! »
Continuous query processing architecture
This section presents the general architecture proposed for the continuous processing of several types of location-dependent queries in indoor environments. First, the main principles and assumptions on how moving objects are handled and to what extent they are expected to cooperate. The principal components considered in the architecture are then introduced, with especial focus on route and distribution management issues.
Principles
Our approach assumes that moving objects cooperate with a given system by providing up-to-date location data when needed. Thus, a minimum intervention of a user device is required for query processing by communicating the location of the user to the system according to a certain location update policy [Wolfson et al., 1999a]. The mobile devices of the users are therefore not overloaded with additional query processing tasks. As soon as a location update is received from a moving object involved in a given query, the server starts the reevaluation process by considering the impact of such updates on the active queries. Accurate location data are assumed to be received in real-time from an indoor positioning system, based on recent technologies such as MEMS sensors, Wireless fingerprinting, and magnetic fields [Liu et al., 2007; Gu et al., 2009; Ray et al., 2010; IndoorAtlas, 2012].
For each location-dependent query, the following terms are used (as suggested in [Ilarri et al., 2006a]). A reference object denotes an object that represents the reference for a given location- dependent query (e.g., for a range query, the object that indicates the centre of the range). A target object represents an object of interest to a given outstanding query, and which belongs to a specific target class. It is worth noting that no constraints are imposed on the movements and directions of the reference and target objects. Accordingly, a reference object is assumed to be either in a static location or moving freely in a spatial network with dynamically changing edge weights. Similarly, a location-dependent query can request information about static or dynamic data, depending on whether the target objects are moving or not. For instance, a reference/target object could be a person or a point of interest -POI- (e.g., a room). Therefore, a unique combination of challenges arises, as the proposed architecture must be able to continuously process different kinds of location-dependent queries, and to take into account additional contextual information, such as the time-dependency and the user profiles (e.g., some areas may be restricted to specific kinds of users, such as the security personnel), as well as the hierarchical layout of the indoor environment.
The general query processing flow is illustrated in Figure 5.1. Navigation-related queries are processed in accordance with this flow, and are executed continuously while the request is not explicitly cancelled by the user. Unlike many query processing approaches that focus on specific types of queries and on specific scenarios, this architecture has the advantage of supporting many different types of queries without making any restrictive assumption. The features that are managed in the environment are: (i) mobile persons, each of them carries a mobile device that allows computing his/her current location and communicating it with other entities, and (ii) objects of interest, which contribute to enrich the context of the query and are used by the user to provide his/her preferences and constraints (e.g., by using a digital user interface). These features are managed by a set of fixed servers, each of them in charge of: (1) maintaining a part of the hierarchical spatial graph that represents the environment (i.e., a part of the graph covering a certain spatial area); (2) managing data and communicating with objects located within its area; and (3) executing queries or parts of queries whose data are locally available.
A LANGUAGE FOR CONTINUOUS LOCATION-DEPENDENT QUERIES IN INDOOR ENVIRONMENTS
Architecture overview
The main phases of the query processing architecture are illustrated in Figure 5.1 and can be described as follows:
Phase 1 and 2. A user interacts with the system interface to issue a query. The system transforms the query expressed in a natural or high-level language into an SQL-like format, as proposed in [Ilarri et al., 2006a]. We assume that an expert user can also directly issue an SQL-like query based
on the syntax described in Section 5.2.
Phase 3. Parsing a query implies lexical, syntactic, and semantic analysis of the query expressed in an SQL-like format in order to derive a valid internal representation (e.g., a query graph [Kossmann, 2000]).
Phase 4. A query plan is prepared that is composed of all the operations that are required to appropriately answer the user request. This not only includes typical relational operations (e.g., selection, projection, join, etc.), but also external calls to specific functions that implement new query operators that are defined and discussed in the next section. For optimization purposes, some typical transformations can take place, such as the removal of redundant predicates, the simplification of complex expressions, etc. In addition, for each constraint in the query, the reference object and its target classes are obtained. Furthermore, information regarding the location granules (discussed in the next section) of the reference and target objects is retrieved, if the use of location granules is specified in the query.
Phase 5. All navigation-related queries that need to expand routes either towards a specified target object (e.g., an optimal path search towards a destination) or in all directions with a maximum threshold (in the case of range queries), are directed to the route manager in charge of determining the candidate routes based on user-defined preferences and contextual data (e.g., information about user profiles and descriptions of objects of interest). The main tasks performed by the route manager are explained in Section 5.1.2.1.
Phase 6. Obtaining standard SQL queries from an SQL-like query is required, since data elements
are assumed to be stored in relational databases, which only accept standard SQL. A location-dependent query is broken up into standard queries and operations that are organised in an execution plan to optimise system resources. Not all the operators are necessarily translated to equivalent standard queries; for instance, operators related to route computation are directly handled at the algorithmic level. The candidate routes obtained by applying such operators could, however, be used as the input data to complete the construction of some standard queries.
Phase 7. In this phase, candidate routes along with an execution plan including standard queries and operations arrive at the query execution engine. Timestamped data about locations of relevant objects as well as other contextual data are associated with operations, so that the query engine can execute these queries appropriately. The continuous processing of a query means that the execution of simple queries and operations is kept alive until receiving an explicit request from the user to cancel that query. Therefore, the engine must repeatedly perform the following tasks: (1) update simple queries with the locations of relevant objects and with the new set of relevant routes, if needed; (2) execute standard queries; (3) correlate the results of the different subqueries; and finally (4) present the answer to the user.
Route management
Two main tasks are performed by the route manager in order to execute navigation-related queries: Task 1: Obtaining an initial answer. Depending on whether a target object is specified or not, different strategies are applied. A specified target implies expanding a directed tree routed at the node where the reference object is located, and oriented towards the target object. For a static shortest path problem, this can typically be solved using Dijkstra’s or A*’s algorithm [Dijkstra, 1959; Hart et al., 1968]. A more complex and challenging scenario for estimating the route cost and computing the optimal path arises when considering parameters such as dynamic edge weights, a hierarchical graph structure and, most importantly, the need for an incremental approach for continuous path search with moving reference and target objects.
Table of contents :
I CONTEXT-AWARE INDOOR NAVIGATION
1 Requirements for Context-Aware Indoor Navigation Systems
1.1 On the role of context in mobile computing
1.2 Challenges in context-dependent indoor data models
1.2.1 Service-oriented requirements
1.2.1.1 Localisation
1.2.1.2 Context-aware, adaptive navigation
1.2.1.3 Location-aware communication
1.2.1.4 Activity-oriented interactions
1.2.1.5 Spatial & behavioural analyses
1.2.2 Efficiency-related requirements
1.2.2.1 Modelling effort
1.2.2.2 Flexibility
1.2.2.3 Performance and scalability
1.3 Data management issues in location-aware services and queries
1.3.1 Location-based services and queries
1.3.2 Continuous and adaptive query processing paradigms
1.3.2.1 Managing moving objects
1.3.2.2 Continuous evaluation of location-dependent queries
1.3.3 Query languages for location-dependent queries
1.4 Discussion
1.5 Summary
II RELATED WORK
2 Spatial Models for Indoor Context-Aware Navigation Systems
2.1 Introduction
2.2 A taxonomy of indoor spatial models
2.2.1 Geometric-based approaches
2.2.1.1 Cell-based models
2.2.1.2 Boundary-based models
2.2.2 Symbolic-based approaches
2.2.2.1 Set-based symbolic models
2.2.2.2 Graph-based models
2.2.3 Discussion
2.2.3.1 Geometric-based approaches
2.2.3.2 Symbolic approaches
2.2.3.3 Application perspective
2.3 Towards hybrid spatial models
3 Continuous Location-Dependent Query Processing
3.1 Need for incremental and adaptive query processing
3.2 Architectures for location-dependent query processing
3.2.1 Continuous query processing in moving object databases
3.2.2 Approaches for location-dependent query processing over data streams
3.2.3 Approaches for managing and querying indoor moving objects
3.2.4 Towards context and preference-aware location-dependent queries
3.3 Continuous processing of navigation-related queries
3.3.1 Query processing in spatial network databases
3.3.2 Path queries
3.3.2.1 Multi-criteria & hierarchical path searches
3.3.2.2 Continuous path search algorithms
3.3.3 Range queries
3.3.4 Other kinds of location-dependent queries
3.3.4.1 Nearest neighbour queries
3.3.4.2 Reachability Queries and Reverse Range and kNN Queries
3.4 Languages for location-dependent queries
3.4.1 Query languages in moving object databases
3.4.2 Data types and operations for spatio-temporal data streams
3.4.3 Languages for querying preference-aware and context data
3.5 Conclusions
III DATA MODEL, QUERY LANGUAGE, ALGORITHMS, AND SYSTEM DESIGN
4 A Hierarchical and Context-Dependent Indoor Data Model
4.1 Need for a hierarchical and context-dependent data model
4.2 Modelling approach
4.2.1 Spatial component
4.2.1.1 Core spatial layer
4.2.1.2 Coarser spatial layers
4.2.2 Feature component
4.2.2.1 Principles
4.2.2.2 User profiles
4.2.2.3 Real-time event management
4.2.3 Action component
4.3 Conclusions
5 A Language for Continuous Location-Dependent Queries in Indoor Environ-ments
5.1 Continuous query processing architecture
5.1.1 Principles
5.1.2 Architecture overview
5.1.2.1 Route management
5.1.2.2 Distribution management
5.2 A language for continuous location-dependent queries
5.2.1 Principles
5.2.2 Query semantics
5.2.3 Managing and representing location granules
5.2.4 Motivating examples of location-dependent queries
5.3 Discussion
6 Algorithms for Continuous Path and Range Queries in Indoor Mobile Environ-ments
6.1 Hierarchical and incremental processing of continuous LDQs
6.2 Continuous processing of indoor path queries
6.2.1 Algorithm principles
6.2.2 Hierarchical and incremental path search algorithm
6.2.2.1 Hierarchical path search
6.2.2.2 Continuous query processing
6.3 Continuous processing of indoor range queries
6.3.1 Hierarchical range network expansion
6.3.2 Incremental algorithm for continuous range search
6.4 Discussion
7 A PostgreSQL Extension for Continuous Location-Dependent Query Processing
7.1 Comparative study of existing platforms for handling LDQs
7.2 System implementation
7.2.1 Overview
7.2.2 Optimization
7.3 Experimental evaluation
7.3.1 Experimental settings
7.3.2 Experimental results
7.3.3 System Scalability
7.3.4 Summary of the experiments
7.4 Conclusions
CONCLUSIONS AND FUTURE WORK
