Taxicabs equipped with real-time location sensing devices are increasingly becoming popular. Such location traces are a rich source of information and can be used for congestion pricing, taxicab placement, and improved city planning. An important problem to enable these application is to identify human mobility patterns from the taxicab traces, which translates to being able to identify pickup and dropoff points for a particular trip. In this paper, we show that while past approaches are effective in detecting hotspots using location traces, they are largely ineffective in identifying trips (pairs of pickup and dropoff points). We propose the use of a graph theory concept - stretch factor in a novel manner to identify trip(s) made by a taxicab and show that a Hidden Markov Model based algorithm can identify trips (using real datasets from taxicab deployments in Shanghai and partially simulated datasets from Stockholm) with precision and recall of 90-94%, a significant improvement over past approaches that result in a precision and recall of about 50-60%.

Ubiquitous and pervasive applications may present critical requirements from the point of view of functional correctness, reliability, availability, security, and safety. Unlike traditional safety-critical applications, the behavior of ubiquitous and pervasive applications is affected by the movements and location of users and resources. In this article, we first present emerging formal methods for the description of both entities and their behavior in pervasive computing environments; then, we introduce this special issue. Despite many previous works that have focused on modeling the entities, relatively few have concentrated on modeling or verifying behaviors; and almost none has dealt with combining techniques proposed in these two aspects. The articles accepted in this special issue cover some of the topics aforementioned and constitute a representative sample of the latest development of formal methods in pervasive computing environments.

An emerging class of end-user programming is the assembly of flow-based applications from a set of reusable components. Testing has become a major challenge, as a very large number of flows can be assembled from a set of components with the expectation of functioning correctly. Faults in assembled flows can create dissatisfaction among users and thereby potentially undermine this end-user programming paradigm We approach this problem as a flow-selection problem, and are interested in ways of testing a subset of flows that provide a high likelihood of revealing faults. We describe a number of flow-selection strategies, which run in the context of a flow pattern, a specification mechanism that constrains the space of assemble-able flows. We evaluate the different strategies on real-world flow patterns in terms of efficiency, i.e., the reduction of flows to test, and effectiveness, measuring of how well the strategies can catch faults.

Vehicle GPS data is an essential "raw" material for a broad range of applications such as traffic management and control, routing, and navigation. To become useful, the data has to be related to the underlying road network by means of map matching algorithms, which are often computationally expensive. In addition, GPS data is not accurate and often needs to be cleaned to remove erroneous observations. In this paper, we describe how map matching can be run on IBM's System S, which provides a platform to run stream processing applications in a scalable manner. We show how various features of System S, including a component based programming model, data pipelining and parallelization of computation, help us to scale the map-matching and data cleaning processes, both as the rate of incoming GPS data increases and as the size of the underlying road network increases. We provide results of performance evaluations, where we show our system can match GPS data arriving at a rate of 1 million points per second onto a map with 1 billion links.

A stream processing flow can be represented as a directed graph that describes how streaming data is obtained from one or more sources, processed by one or more components, and finally sent to one or more sinks. In this paper, we show how stream processing flows can be used to support location based services for a variety of end-users. In particular, we show how these flows can be customized for specific end-user requests from a set of reusable software components. For this, we use a language called Cascade that we had proposed in previous work for describing commonly used patterns of flows. The patterns cover different possible variations of the flows, including variations in the structure of the flow, the components in the flow and the possible parameterizations of these components. We provide examples of flows composed in the domain of intelligent transportation services.

With the widespread adoption of location tracking technologies like GPS, the domain of intelligent transportation services has seen growing interest in the last few years. Services in this domain make use of real-time location-based data from a variety of sources, combine this data with static location-based data such as maps and points of interest databases, and provide useful information to end-users. Some of the major challenges in this domain include i) scalability, in terms of processing large volumes of real-time and static data; ii) extensibility, in terms of being able to add new kinds of analyses on the data rapidly, and iii) user interaction, in terms of being able to support different kinds of one-time and continuous queries from the end-user. In this paper, we demonstrate the use of IBM InfoSphere Streams, a scalable stream processing platform, for tackling these challenges. We describe a prototype system that generates dynamic, multi-faceted views of transportation information for the city of Stockholm, using real vehicle GPS and road-network data. The system also continuously derives current traffic statistics, and provides useful value-added information such as shortest-time routes from real-time observed and inferred traffic conditions. Our performance experiments illustrate the scalability of the system. For instance, our system can process over 120000 incoming GPS points per second, combine it with a map containing over 600,000 links, continuously generate different kinds of traffic statistics and answer user queries.

In this paper, we tackle the problem of helping domain experts to construct, parameterize and deploy mashups of data and code. We view a mashup as a data processing flow, that describes how data is obtained from one or more sources, processed by one or more components, and finally sent to one or more sinks. Our approach allows specifying patterns of flows, in a language called Cascade. The patterns cover different possible variations of the flows, including variations in the structure of the flow, the components in the flow and the possible parameterizations of these components. We present a tool that makes use of this knowledge of flow patterns and associated metadata to allow domain experts to explore the space of possible flows described in the pattern. The tool uses an AI planning approach to automatically build a flow, belonging to the flow pattern, from a high-level goal, specified as a set of tags. We describe examples from the financial services domain to show the use of flow patterns in allowing domain experts to construct a large variety of mashups rapidly.

As the use of electronic medical records (EMRs) becomes more widespread, so does the need for effective information discovery within them. Recently proposed EMR standards are XML-based. A key characteristic in these standards is the frequent use of ontological references, i.e., ontological concept codes appear as XML elements and are used to associate portions of the EMR document with concepts defined in a domain ontology. A rich corpus of work addresses searching XML documents. Unfortunately, these works do not make use of ontological references to enhance search. In this paper we present the XOntoRank system which addresses the problem of ontology-aware keyword search of XML documents with a particular focus on EMR XML documents. Our current prototypes and experiments use the health level seven (HL7) clinical document architecture (CDA) Release 2.0 standard of EMR representation and the systematized nomenclature of human and veterinary medicine (SNOMED) ontology, although the presented techniques and results are applicable to any EMR hierarchical format and any ontology that defines concepts and relationships.

The configuration and runtime management of distributed systems is often complex due to the presence of a large number of configuration options and dependencies between interacting sub-systems. Inexperienced users usually choose default configurations because they are not aware of the possible configurations and/or their effect on the systems' operation. In doing so, they are unable to take advantage of the potentially wide range of system capabilities. Furthermore, managing inter-dependent sub-systems frequently involves performing a set of actions to get the overall system to the desired final state. In this paper, we propose a new approach for configuring and managing distributed systems based on AI planning. We use a goal-driven, tag-based user interaction paradigm to shield users from the complexities of configuring and managing systems. The key idea behind our approach is to package different configuration options and system management actions into reusable modules that can be automatically composed into workflows based on the user's goals. It also allows capturing the inter-dependencies between different configuration options, management actions and system states. We evaluate our approach in a case study involving three inter-dependent sub-systems. Our initial experiences indicate that this planning-based approach holds great promise in simplifying configuration and management tasks.

As the use of electronic medical records (EMRs) becomes more widespread, so does the need for effective information discovery on them. Recently proposed EMR standards are XML-based, having as a key characteristic the frequent use of ontological references, i.e., ontological concept codes appear as XML elements and are used to associate portions of the EMR document with concepts defined in a domain ontology. In this paper we present the XOntoRank system which tackles the problem of ontology-aware keyword search on XML documents with a particular focus on EMR XML documents. Our running examples and experiments use the Health Level Seven (HL7) clinical document architecture (CDA) Release 2.0 standard of EMR representation and the systematized nomenclature of human and veterinary medicine (SNOMED) ontology, although the presented techniques and results are applicable to any EMR hierarchical format and any ontology that defines concepts and relationships.

The Web services research community has proposed a number of approaches for service composition, ranging from manual to semi-automatic to completely automatic. However, it is often difficult to take independently developed services and compose them, since they may not work together correctly. For service composition to occur, the services in question must be designed and developed in a manner that facilitates their composition. In this paper, we propose a novel approach for service design and composition that combines top-down and bottom-up elements. Our approach is driven by faceted, tag-based functional requirements provided by end-users. These requirements describe, at a high-level, the families of compositions that end-users desire. The requirements kick off a top-down service development lifecycle, where enterprise architects and service developers design, develop and test workflows and services, possibly reusing existing flows and services in the process. At runtime, end-users can specify goals, which are satisfied through a bottom-up composition of flows from the available services. The composed flows include those explicitly designed by the architects as well as new ones that are assembled in a serendipitous manner from the available services. With examples from a case study in the financial services domain, we demonstrate our approach for designing and developing services that can be composed into myriad workflows based on end-user goals.

In the realm of component-based software systems, pursuers of the holy grail of automated application composition face many significant challenges. In this paper we argue that, while the general problem of automated composition in response to high-level goal statements is indeed very difficult to solve, we can realize composition in a restricted context, supporting varying degrees of manual to automated assembly for specific types of applications. We propose a novel paradigm for composition in flow-based information processing systems, where application design and component development are facilitated by the pervasive use of faceted, tag-based descriptions of processing goals, of component capabilities, and of structural patterns of families of application. The facets and tags represent different dimensions of both data and processing, where each facet is modeled as a finite set of tags that are defined in a controlled folksonomy. All data flowing through the system, as well as the functional capabilities of components are described using tags. A customized AI planner is used to automatically build an application, in the form of a flow of components, given a high-level goal specification in the form of a set of tags. End-users use an automatically populated faceted search and navigation mechanism to construct these high-level goals. We also propose a novel software engineering methodology to design and develop a set of reusable, well-described components that can be assembled into a variety of applications. With examples from a case study in the Financial Services domain, we demonstrate that composition using a faceted, tag-based application design is not only possible, but also extremely useful in helping end-users create situational applications from a wide variety of available components.

The field of pervasive computing has seen a lot of exciting innovations in the past few years. However, there are currently no mechanisms for describing the properties and capabilities of pervasive computing environments in a formal manner. This makes it difficult to prove the correctnesss of a pervasive computing environment, i.e. to verify that the environment satisfies certain desired properties. In this paper, we propose a formal model for describing pervasive computing environments based on ambient calculus and the associated ambient logic. The model allows us to state and verify several properties of these environments such as "anywhere anyhow services", "mobility of devices and applications" and "context-aware adaptation ". The model allows us to describe the resources present in an environment, the operations that can be performed in the environment, and how users can use the resources in th environment to perform different kinds of activities. As a case study, we shall describe some of the resources and operations supported by the Gaia middleware using this model, and verify an example property of a pervasive computing environment supported by Gaia.

We consider a fundamental flow maximization problem that arises during the evaluation of multiple overlapping queries defined on a data stream, in a heterogenous parallel environment. Each query is a conjunction of boolean filters, and each filter could be shared across multiple queries. We are required to design an evaluation plan that evaluates filters against stream items in order to determine the set of queries satisfied by each item. The evaluation plan specifies for each item: (i) the subset of filters evaluated for this item and the order of their evaluations, and (ii) the processor on which each filter evaluation occurs. Our goal is to design an evaluation plan which maximizes the total throughput (flow) of the stream handled by the plan, without violating the processor capacities.

We consider the problem of evaluating multiple overlapping queries defined on data streams, where each query is a conjunction of multiple filters and each filter may be shared across multiple queries. Efficient support for overlapping queries is a critical issue in the emerging data stream systems, and this is particularly the case when filters are expensive in terms of their computational complexity and processing time. This problem generalizes other well-known problems such as pipelined filter ordering and set cover, and is not only NP-Hard but also hard to approximate within a factor of o(log n) from the optimum, where n is the number of queries. In this paper, we present two near-optimal approximation lgorithms with provably-good performance guarantees for the evaluation of overlapping queries. We present an edge-coverage based Greedy algorithm which achieves an approximation ratio of (1 + log(n) + log(α)), where n is the number of queries and α is the average number of filters in a query. We also present a randomized, fast and easily parallelizable Harmonic algorithm which achieves an approximation ratio of 2β, where β is the maximum number of filters in a query. We have implemented these algorithms in a prototype system, and evaluated their performance using extensive experiments in the context of multimedia stream analysis. The results show that our Greedy algorithm consistently outperforms other known algorithms under various settings and scales well as the numbers of queries and filters increase.

With the emergence of Yahoo Pipes and several similar services, data mashup tools have started to gain interest of business users. Making these tools simple and accessible ton users with no or little programming experience has become a pressing issue. In this paper we introduce MARIO (Mashup Automation with Runtime Orchestration and Invocation), a new tool that radically simplifies data mashup composition. We have developed an intelligent automatic composition engine in MARIO together with a simple user interface using an intuitive "wishful search" abstraction. It thus allows users to explore the space of potentially composable data mashups and preview composition results as they iteratively refine their "wishes", i.e. mashup composition goals. It also lets users discover and make use of system capabilities without having to understand the capabilities of individual components, and instantly reflects changes made to the components by presenting an aggregate view of changed capabilities of the entire system. We describe our experience with using MARIO to compose flows of Yahoo Pipes components.

In this paper, we propose a novel way of modeling Web services using semantic graph transformations. Each operation supported by a Web service is associated with a semantic annotation that describes the input and output messages using RDF graph patterns. The terms used in these patterns are defined in OWL ontologies that describe the application domain. A key difference between our model and existing semantic Web service models like OWLS is that it describes the inputs and outputs in terms of instance-based graph patterns, rather than in terms of concepts. This allows associating a rich set of constraints on the input and output data in terms of relations between instances. We also propose a composition model for Web service operations, that describes the conditions for composing services into workflows. The composition model includes the notion of semantic propagation, i.e. the semantic description of the output message of an operation depends on the semantics of the input message. We have developed a planner that uses this model to compose services, automatically. The planner uses DLP reasoning to aid plan search. We present performance results for the planner.

Intelligence Transportation Systems are critical to improve the efficiency of modern transportation. A system that is flexible and powerful enough to handle diverse demands from a large user base, is still elusive. Studies have shown that developing and integrating the various components constitute a significant portion of the capital cost and complexity of such systems. In this paper, we present a stream processing infrastructure we call System S. System S enables the deployment of large scale applications. It supports a mechanism for sharing data sources, software components, and even intermediate results allowing a reduction in the cost of software integration, and ownership. We experiment the stream processing infrastructure with a Fleet Management Center, and demonstrate how the infrastructure can be used to address unique issues in traffic management.

Relational databases are widely used today as a mechanism for providing access to structured data. They, however, are not suitable for typical information finding tasks of end users. There is often a semantic gap between the queries users want to express and the queries that can be answered by the database. In this paper, we propose a system that bridges this semantic gap using domain knowledge contained in ontologies. Our system extends relational databases with the ability to answer semantic queries that are represented in SPARQL, an emerging Semantic Web query language. Users express their queries in SPARQL, based on a semantic model of the data, and they get back semantically relevant results. We define different categories of results that are semantically relevant to the users' query and show how our system retrieves these results. We evaluate the performance of our system on sample relational databases, using a combination of standard and custom ontologies.

Ubiquitous computing environments feature massively distributed systems containing a large number of devices, services and applications that help end-users perform various kinds of tasks. One way by which administrators and end-users can manage these environments is through the use of policies. In particular, obligation policies are used to specify what actions must or must not be performed by the environment on the occurrence of certain events. Obligation policies are often specified as event-condition-action (ECA) rules. However an important problem in ubiquitous computing systems is that different users and administrators may have conflicting policies for managing the system. Hence, a key challenge in policy-based management is detecting and resolving conflicts between multiple policy rules that get activated by a single event. Existing approaches are limited in power and scope mainly because they do not have semantic information about the effects of policy actions; hence, they cannot infer that two actions may conflict unless they are explicitly stated to be conflicting. In this paper, we propose an extended model of ECA called event-condition-action-post-condition (ECA-P), where developers and administrators can annotate actions with their effects. The ECA-P model allows inferring that actions may conflict based on conflicting post-conditions. Detected conflicts are resolved using meta-rules that specify preferred system states. The ECA-P framework also detects failures in policy execution by using postconditions to verify successful completion of policy actions. We present the details of the framework.

Pervasive Computing advocates the enhancement of physical spaces with computing and communication resources that help users perform various kinds of tasks. We call these enhanced physical spaces Active Spaces. Active Spaces are highly dynamic — the context and resources available in these evironments can change rapidly. The large number of entities present in these spaces and the dynamism associated with them make it difficult for developers to program these environments. It is not always clear at development time which resources are to be used for performing various kinds of tasks and how to use them. In this paper, we introduce a new high-level programming model for pervasive computing environments, Olympus. The main feature of this model is that developers can specify Active Space entities and common Active Space operations at an abstract, high level. Active Space entities (which include services, applications, devices, physical objects, locations and users) can be specified using high level descriptions. Our framework resolves these descriptions into actual Active Space entities based on constraints specified by the developer, ontological descriptions of entities, the resources available in the current space, space-level policies and the current context of the space. The programming model also provides the developers with operators for commonly used functions. Examples of operators include start, stop and move components. Thus, developers do not have to worry about how various tasks are performed in the space in which their program is to be deployed. These details are taken care of by the model and the developer is free to focus on the actual logic of the program. In this paper, we discuss the programming model, its implementation and several example Active Space programs that have been developed using this model.

Pervasive computing environments augment physical spaces with a large number of devices and services that help users perform different kinds of tasks. Users in these environments interact with one or more Web services using various devices to achieve their goals. One of the problems in these environments is discovering and coordinating different Web services for achieving the user's goals. Users may not be aware of which services and devices are available in an unfamiliar environment and how to interact with them in order to achieve their goals. In order to simplify a user's interaction with the environment, we present a novel approach of modeling and managing a user's interaction with the environment based on workflows. We have built a prototype, using the popular business workflow language (BPEL) that models various processes in pervasive environments as workflows. We found that this approach improves the usability of these environments. It also increases flexibility in changing the model of interaction without having to touch individual services and applications. This approach is particularly useful in helping visitors in public spaces like malls, museums, supermarkets and hospitals.

This paper proposes a component-based programming approach to discovery. In this approach, individual discovery protocols, access models and authentication mechanisms are represented as software components called handlers. Handlers are registered with and coordinated by a software framework called a discovery agent. Configured with a battery of handlers, a discovery agent answers query and advertisement requests on behalf of mobile and other applications and applies authentication and access control policies. Based on its set of handlers, a diversity of request types and formats can be routed, translated, and fulfilled by a discovery agent. Discovery agents can easily be reconfigured, adapted, and extended as new underlying discovery protocols or client request types must be supported. A discovery agent can operate as a Web service, and can be deployed by an enterprise to service discovery requests on behalf of visiting clients. A discovery agent can also operate as a trusted co-module running on a device, and is useful for supporting mobile applications which move among environments and must accommodate a diversity of local discovery protocols.

Enabling people-to-people interaction across heterogeneous communication end-points enhances user experience and fosters people collaboration. This paper presents the design and implementation of a unified communication system, dubbed Mercury, that allows a user to interact with others using the most convenient device at the time. Mercury supports both two-way conversation and one-way messaging. It leverages the Session Initiation Protocol to manage communication sessions and exploits dynamic user context to proactively route and migrate calls. It allows for subscription to other users' unified reachability status and provides a soft ring feature via universal notification. Mercury has an extensible architecture that allows new device types to be easily incorporated into the system. Our prototype implementation integrates a variety of devices: telephones, Sametime instant messaging clients, email, and pagers.

Ubiquitous computing envisions an environment where physical and digital devices are seamlessly integrated. Users can access their applications and data anywhere in the environment. Applications are not bound to any single device and can migrate with the user to different environments. Therefore, application mobility is an important aspect of ubiquitous computing. We consider the problem of migrating applications across different ubiquitous computing environments (i.e. across different rooms, buildings or even cities). Migration is a tough problem because different environments have different resources (devices or services) available. The context of the environments may be different as well. Hence, mobile applications must adapt to changing contexts and resource availabilities as they migrate from one environment to the next. We introduce the notion of polymorphic applications, where applications can change their structure in order to adapt to different environments. While the structure of polymorphic applications can change during migration, the functionality and the state of the application are preserved as far as possible. This enables users to perform the same tasks as they move from one environment to the next, seamlessly. We make use of ontologies to ensure that the initial and final structures of a migrating application are semantically similar in terms of functionality and behavior. This paper describes our framework for enabling mobile polymorphic applications.

Ubiquitous computing has fueled the idea of constructing sentient, information-rich "smart spaces" that extend the boundaries of traditional computing to encompass physical spaces, embedded devices, sensors, and other machinery. To achieve this, smart spaces need to capture situational information so that they can detect changes in context and adapt themselves accordingly. However, without considering basic security issues ubiquitous computing environments could be rife with vulnerabilities. Ubiquitous computing environments impose new requirements on security. Security services, like authentication and access control, have to be non-intrusive, intelligent, and able to adapt to the rapidly changing contexts of the spaces. We present a ubiquitous security mechanism that integrates context-awareness with automated reasoning to perform authentication and access control in ubiquitous computing environments.

Essentially all distributed systems, applications, and services at some level boil down to the problem of managing distributed shared state. Unfortunately, while the problem of managing distributed shared state is shared by many applications, there is no common means of managing the data-every application devises its own solution. We have developed Khazana, a distributed service exporting the abstraction of a distributed persistent globally shared store that applications can use to store their shared state. Khazana is responsible for performing many of the common operations needed by distributed applications, including replication, consistency management, fault recovery, access control and location management. Using Khazana as a form of middleware, distributed applications can be quickly developed from corresponding uniprocessor applications through the insertion of Khazana data access and synchronization operations.