Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Mining Cell Transition Data

Cell transition data is obtained from a cellular phone that switches its current serving cell tower. The data consists of a sequence of transition events, which are pairs of cell identifiers and transition times. The focus of this thesis is applying data mining methods to such data, developing new algorithms, and extracting knowledge that will be a solid foundation on which to build location-aware applications. In addition to a thorough exploration of the features of the data, the tools and methods developed in this thesis provide solutions to three distinct research problems. First, we develop clustering algorithms that produce a reliable mapping between cell transitions and physical locations observed by users of mobile devices. The main clustering algorithm operates in online fashion, and we consider also a number of offline clustering methods for comparison. Second, we define the concept of significant locations, known as bases, and give an online algorithm for determining them. Finally, we consider the task of predicting the movement of the user, based on historical data. We develop a prediction algorithm that considers paths of movement in their entirety, instead of just the most recent movement history. All of the presented methods are evaluated with a significant body of real cell transition data, collected from about one hundred different individuals. The algorithms developed in this thesis are designed to be implemented on a mobile device, and require no extra hardware sensors or network infrastructure. By not relying on external services and keeping the user information as much as possible on the user s own personal device, we avoid privacy issues and let the users control the disclosure of their location information.

Place Identification : A Comparative Study

Place identification is the methodology of automatically detecting spatial regions or places that are meaningful to a user by analysing her location traces. Following this approach several algorithms have been proposed in the literature. Most of the algorithms perform well on a particular data set with suitable choice of parameter values. However, tuneable parameters make it difficult for an algorithm to generalise to data sets collected from different geographical locations, different periods of time or containing different activities. This thesis compares the generalisation performance of our proposed DPCluster algorithm along with six state-of-the-art place identification algorithms on twelve location data sets collected using Global Positioning System (GPS). Spatial and temporal variations present in the data help us to identify strengths and weaknesses of the place identification algorithms under study. We begin by discussing the notion of a place and its importance in location-aware computing. Next, we discuss different phases of the place identification process found in the literature followed by a thorough description of seven algorithms. After that, we define evaluation metrics and compare generalisation performance of individual place identification algorithms and report the results. The results indicate that the DPCluster algorithm performs superior to all other algorithms in terms of generalisation performance.

Service Experience in an Innovation Context

Service researchers and practitioners have repeatedly claimed that customer service experiences are essential to all businesses. Therefore comprehension of how service experience is characterised in research is an essential element for its further development through research. The importance of greater in-depth understanding of the phenomenon of service experience has been acknowledged by several researchers, such as Carú and Cova and Vargo and Lusch. Furthermore, Service-Dominant (S-D) logic has integrated service experience to value by emphasising in its foundational premises that value is phenomenologically (experientially) determined. The present study analyses how the concept of service experience has been characterised in previous research. As such, it puts forward three ways to characterise it in relation to that research: 1) phenomenological service experience relates to the value discussion in S-D logic and interpretative consumer research, 2) process-based service experience relates to understanding service as a process, and 3) outcome-based service experience relates to understanding service experience as one element in models linking a number of variables or attributes to various outcomes. Focusing on the phenomenological service experience, the theoretical purpose of the study is to characterise service experience based on the phenomenological approach. In order to do so, an additional methodological purpose was formulated: to find a suitable methodology for analysing service experience based on the phenomenological approach. The study relates phenomenology to a philosophical Husserlian and social constructionist tradition studying phenomena as they appear in our experience in a social context. The study introduces Event-Based Narrative Inquiry Technique (EBNIT), which combines critical events with narratives and metaphors. EBNIT enabled the analysis of lived and imaginary service experiences as expressed in individual narratives. The study presents findings of eight case studies within service innovation of Web 2.0, mobile service, location aware service and public service in the municipal sector. Customers’ and service managers’ stories about their lived private and working lifeworld were the foundation for their ideal service experiences. In general, the thesis finds that service experiences are (1) subjective, (2) context-specific, (3) cumulative, (4) partially socially constructed, (5) both lived and imaginary, (6) temporally multiple-dimensional, and (7) iteratively related to perceived value. In addition to customer service experience, the thesis brings empirical evidence of managerial service experience of front-line managers experiencing the service they manage and develop in their working lifeworld. The study contributes to S-D logic, service innovation and service marketing and management in general by characterising service experience based on the phenomenological approach and integrating it to the value discussion. Additionally, the study offers a methodological approach for further exploration of service experiences. The study discusses managerial implications in conjunction with the case studies and discusses them in relation to service innovation.

Vision based indoor positioning in a retail environment

Modern smart phones often come with a significant amount of computational power and an integrated digital camera making them an ideal platform for intelligents assistants. This work is restricted to retail environments, where users could be provided with for example navigational in- structions to desired products or information about special offers within their close proximity. This kind of applications usually require information about the user's current location in the domain environment, which in our case corresponds to a retail store. We propose a vision based positioning approach that recognizes products the user's mobile phone's camera is currently pointing at. The products are related to locations within the store, which enables us to locate the user by pointing the mobile phone's camera to a group of products. The first step of our method is to extract meaningful features from digital images. We use the Scale- Invariant Feature Transform SIFT algorithm, which extracts features that are highly distinctive in the sense that they can be correctly matched against a large database of features from many images. We collect a comprehensive set of images from all meaningful locations within our domain and extract the SIFT features from each of these images. As the SIFT features are of high dimensionality and thus comparing individual features is infeasible, we apply the Bags of Keypoints method which creates a generic representation, visual category, from all features extracted from images taken from a specific location. A category for an unseen image can be deduced by extracting the corresponding SIFT features and by choosing the category that best fits the extracted features. We have applied the proposed method within a Finnish supermarket. We consider grocery shelves as categories which is a sufficient level of accuracy to help users navigate or to provide useful information about nearby products. We achieve a 40% accuracy which is quite low for commercial applications while significantly outperforming the random guess baseline. Our results suggest that the accuracy of the classification could be increased with a deeper analysis on the domain and by combining existing positioning methods with ours.

The ozone transfer between atmosphere and vegetation. A study on Scots pine in the field

Ozone (O3) is a reactive gas present in the troposphere in the range of parts per billion (ppb), i.e. molecules of O3 in 109 molecules of air. Its strong oxidative capacity makes it a key element in tropospheric chemistry and a threat to the integrity of materials, including living organisms. Knowledge and control of O3 levels are an issue in relation to indoor air quality, building material endurance, respiratory human disorders, and plant performance. Ozone is also a greenhouse gas and its abundance is relevant to global warming. The interaction of the lower troposphere with vegetated landscapes results in O3 being removed from the atmosphere by reactions that lead to the oxidation of plant-related components. Details on the rate and pattern of removal on different landscapes as well as the ultimate mechanisms by which this occurs are not fully resolved. This thesis analysed the controlling processes of the transfer of ozone at the air-plant interface. Improvement in the knowledge of these processes benefits the prediction of both atmospheric removal of O3 and its impact on vegetation. This study was based on the measurement and analysis of multi-year field measurements of O3 flux to Scots pine (Pinus sylvestris L.) foliage with a shoot-scale gas-exchange enclosure system. In addition, the analyses made use of simultaneous CO2 and H2O exchange, canopy-scale O3, CO2 and H2O exchange, foliage surface wetness, and environmental variables. All data was gathered at the SMEAR measuring station (southern Finland). Enclosure gas-exchange techniques such as those commonly used for the measure of CO2 and water vapour can be applied to the measure of ozone gas-exchange in the field. Through analysis of the system dynamics the occurring disturbances and noise can be identified. In the system used in this study, the possible artefacts arising from the ozone reactivity towards the system materials in combination with low background concentrations need to be taken into account. The main artefact was the loss of ozone towards the chamber walls, which was found to be very variable. The level of wall-loss was obtained from simultaneous and continuous measurements, and was included in the formulation of the mass balance of O3 concentration inside the chamber. The analysis of the field measurements in this study show that the flux of ozone to the Scots pine foliage is generated in about equal proportions by stomatal and non-stomatal controlled processes. Deposition towards foliage and forest is sustained also during night and winter when stomatal gas-exchange is low or absent. The non-stomatal portion of the flux was analysed further. The pattern of flux in time was found to be an overlap of the patterns of biological activity and presence of wetness in the environment. This was seen to occur both at the shoot and canopy scale. The presence of wetness enhanced the flux not only in the presence of liquid droplets but also during existence of a moisture film on the plant surfaces. The existence of these films and their relation to the ozone sinks was determined by simultaneous measurements of leaf surface wetness and ozone flux. The results seem to suggest ozone would be reacting at the foliage surface and the reaction rate would be mediated by the presence of surface wetness. Alternative mechanisms were discussed, including nocturnal stomatal aperture and emission of reactive volatile compounds. The prediction of the total flux could thus be based on a combination of a model of stomatal behaviour and a model of water absorption on the foliage surfaces. The concepts behind the division of stomatal and non-stomatal sinks were reconsidered. This study showed that it is theoretically possible that a sink located before or near the stomatal aperture prevents or diminishes the diffusion of ozone towards the intercellular air space of the mesophyll. This obstacle to stomatal diffusion happens only under certain conditions, which include a very low presence of reaction sites in the mesophyll, an extremely strong sink located on the outer surfaces or stomatal pore. The relevance, or existence, of this process in natural conditions would need to be assessed further. Potentially strong reactions were considered, including dissolved sulphate, volatile organic compounds, and apoplastic ascorbic acid. Information on the location and the relative abundance of these compounds would be valuable. The highest total flux towards the foliage and forest happens when both the plant activity and ambient moisture are high. The highest uptake into the interior of the foliage happens at large stomatal apertures, provided that scavenging reactions located near the stomatal pore are weak or non-existent. The discussion covers the methodological developments of this study, the relevance of the different controlling factors of ozone flux, the partition amongst its component, and the possible mechanisms of non-stomatal uptake.

Food and Indoor Air Isolated Bacillus Non-Protein Toxins: : Structures, Physico-Chemical Properties and Mechanisms of Effects on Eukaryotic Cells

We report here the structures and properties of heat-stable, non-protein, and mammalian cell-toxic compounds produced by spore-forming bacilli isolated from indoor air of buildings and from food. Little information is available on the effects and occurrence of heat-stable non-protein toxins produced by bacilli in moisture-damaged buildings. Bacilli emit spores that move in the air and can serve as the carriers of toxins, in a manner similar to that of the spores of toxic fungi found in contaminated indoor air. Bacillus spores in food cause problems because they tolerate the temperatures applied in food manufacture and the spores later initiate growth when food storage conditions are more favorable. Detection of the toxic compounds in Bacillus is based on using the change in mobility of boar spermatozoa as an indicator of toxic exposure. GC, LC, MS, and nuclear magnetic resonance NMR spectroscopy were used for purification, detection, quantitation, and analysis of the properties and structures of the compounds. Toxicity and the mechanisms of toxicity of the compounds were studied using boar spermatozoa, feline lung cells, human neural cells, and mitochondria isolated from rat liver. The ionophoric properties were studied using the BLM (black-lipid membrane) method. One novel toxin, forming ion channels permeant to K+ > Na+ > Ca2+, was found and named amylosin. It is produced by B. amyloliquefaciens isolated from indoor air of moisture-damaged buildings. Amylosin was purified with an RP-HPLC and a monoisotopic mass of 1197 Da was determined with ESI-IT-MS. Furthermore, acid hydrolysis of amylosin followed by analysis of the amino acids with the GS-MS showed that it was a peptide. The presence of a chromophoric polyene group was found using a NMR spectroscopy. The quantification method developed for amylosin based on RP-HPLC-UV, using the macrolactone polyene, amphotericin B (MW 924), as a reference compound. The B. licheniformis strains isolated from a food poisoning case produced a lipopeptide, lichenysin A, that ruptured mammalian cell membranes and was purified with a LC. Lichenysin A was identified by its protonated molecules and sodium- and potassium- cationized molecules with MALDI-TOF-MS. Its protonated forms were observed at m/z 1007, 1021 and 1035. The amino acids of lichenysin A were analyzed with ESI-TQ-MS/MS and, after acid hydrolysis, the stereoisomeric forms of the amino acids with RP-HPLC. The indoor air isolates of the strain of B. amyloliquefaciens produced not only amylosin but also lipopeptides: the cell membrane-damaging surfactin and the fungicidal fengycin. They were identified with ESI-IT-MS observing their protonated molecules, the sodium- and potassium-cationized molecules and analysing the MS/MS spectra. The protonated molecules of surfactin and fengycin showed m/z values of 1009, 1023, and 1037 and 1450, 1463, 1493, and 1506, respectively. Cereulide (MW 1152) was purified with RP-HPLC from a food poisoning strain of B. cereus. Cereulide was identified with ESI-TQ-MS according to the protonated molecule observed at m/z 1154 and the ammonium-, sodium- and potassium-cationized molecules observed at m/z 1171, 1176, and 1192, respectively. The fragment ions of the MS/MS spectrum obtained from the protonated molecule of cereulide at m/z 1154 were also interpreted. We developed a quantification method for cereulide, using RP-HPLC-UV and valinomycin (MW 1110, which structurally resembles cereulide) as the reference compound. Furthermore, we showed empirically, using the BLM method, that the emetic toxin cereulide is a specific and effective potassium ionophore of whose toxicity target is especially the mitochondria.

Efficient Content-based Routing, Mobility-aware Topologies, and Temporal Subspace Matching

Event-based systems are seen as good candidates for supporting distributed applications in dynamic and ubiquitous environments because they support decoupled and asynchronous many-to-many information dissemination. Event systems are widely used, because asynchronous messaging provides a flexible alternative to RPC (Remote Procedure Call). They are typically implemented using an overlay network of routers. A content-based router forwards event messages based on filters that are installed by subscribers and other routers. The filters are organized into a routing table in order to forward incoming events to proper subscribers and neighbouring routers. This thesis addresses the optimization of content-based routing tables organized using the covering relation and presents novel data structures and configurations for improving local and distributed operation. Data structures are needed for organizing filters into a routing table that supports efficient matching and runtime operation. We present novel results on dynamic filter merging and the integration of filter merging with content-based routing tables. In addition, the thesis examines the cost of client mobility using different protocols and routing topologies. We also present a new matching technique called temporal subspace matching. The technique combines two new features. The first feature, temporal operation, supports notifications, or content profiles, that persist in time. The second feature, subspace matching, allows more expressive semantics, because notifications may contain intervals and be defined as subspaces of the content space. We also present an application of temporal subspace matching pertaining to metadata-based continuous collection and object tracking.

Exploring privacy for ubiquitous computing: Tools, methods and experiments

Ubiquitous computing is about making computers and computerized artefacts a pervasive part of our everyday lifes, bringing more and more activities into the realm of information. The computationalization, informationalization of everyday activities increases not only our reach, efficiency and capabilities but also the amount and kinds of data gathered about us and our activities. In this thesis, I explore how information systems can be constructed so that they handle this personal data in a reasonable manner. The thesis provides two kinds of results: on one hand, tools and methods for both the construction as well as the evaluation of ubiquitous and mobile systems---on the other hand an evaluation of the privacy aspects of a ubiquitous social awareness system. The work emphasises real-world experiments as the most important way to study privacy. Additionally, the state of current information systems as regards data protection is studied. The tools and methods in this thesis consist of three distinct contributions. An algorithm for locationing in cellular networks is proposed that does not require the location information to be revealed beyond the user's terminal. A prototyping platform for the creation of context-aware ubiquitous applications called ContextPhone is described and released as open source. Finally, a set of methodological findings for the use of smartphones in social scientific field research is reported. A central contribution of this thesis are the pragmatic tools that allow other researchers to carry out experiments. The evaluation of the ubiquitous social awareness application ContextContacts covers both the usage of the system in general as well as an analysis of privacy implications. The usage of the system is analyzed in the light of how users make inferences of others based on real-time contextual cues mediated by the system, based on several long-term field studies. The analysis of privacy implications draws together the social psychological theory of self-presentation and research in privacy for ubiquitous computing, deriving a set of design guidelines for such systems. The main findings from these studies can be summarized as follows: The fact that ubiquitous computing systems gather more data about users can be used to not only study the use of such systems in an effort to create better systems but in general to study phenomena previously unstudied, such as the dynamic change of social networks. Systems that let people create new ways of presenting themselves to others can be fun for the users---but the self-presentation requires several thoughtful design decisions that allow the manipulation of the image mediated by the system. Finally, the growing amount of computational resources available to the users can be used to allow them to use the data themselves, rather than just being passive subjects of data gathering.

AndroMedia - Towards a Context-aware Mobile Music Recommender

Portable music players have made it possible to listen to a personal collection of music in almost every situation, and they are often used during some activity to provide a stimulating audio environment. Studies have demonstrated the effects of music on the human body and mind, indicating that selecting music according to situation can, besides making the situation more enjoyable, also make humans perform better. For example, music can boost performance during physical exercises, alleviate stress and positively affect learning. We believe that people intuitively select different types of music for different situations. Based on this hypothesis, we propose a portable music player, AndroMedia, designed to provide personalised music recommendations using the user’s current context and listening habits together with other user’s situational listening patterns. We have developed a prototype that consists of a central server and a PDA client. The client uses Bluetooth sensors to acquire context information and logs user interaction to infer implicit user feedback. The user interface also allows the user to give explicit feedback. Large user interface elements facilitate touch-based usage in busy environments. The prototype provides the necessary framework for using the collected information together with other user’s listening history in a context- enhanced collaborative filtering algorithm to generate context-sensitive recommendations. The current implementation is limited to using traditional collaborative filtering algorithms. We outline the techniques required to create context-aware recommendations and present a survey on mobile context-aware music recommenders found in literature. As opposed to the explored systems, AndroMedia utilises other users’ listening habits when suggesting tunes, and does not require any laborious set up processes.

Power Aware Real Time Scheduling in Constrained Devices

Real-time scheduling algorithms, such as Rate Monotonic and Earliest Deadline First, guarantee that calculations are performed within a pre-defined time. As many real-time systems operate on limited battery power, these algorithms have been enhanced with power-aware properties. In this thesis, 13 power-aware real-time scheduling algorithms for processor, device and system-level use are explored.

Phylogeny of a taxonomically difficult group and evolution of host location mechanism

The parasitic wasps are one of the largest insect groups and their life histories are remarkably variable. Common to all parasitic wasps is that they kill their hosts, which are usually beetles, butterflies and sometimes spiders. Hosts are often at a larval or pupal stage and live in concealed conditions, such as in plant tissue. Parasitic wasps have two main ways of finding their host. 1) They can detect chemical compounds emitted by damaged plant material or released by larvae living in plant tissue, and 2) detect the larvae by sound vibrations. Even though pupae are immobile and silent, and therefore do not cause vibration, parasitoids have, however, adapted to find passive developmental stages by producing vibration themselves by knocking the substrate with their antennae, and then detecting the echoes with their legs. This echolocation allows a parasitoid to locate its potential hosts that are deeply buried in wood. This study focuses on the relationships of the subfamily Cryptinae (Hymenoptera: Ichneumonidae) and related taxa, and the evolution of host location mechanism. There are no earlier studies of the phylogeny of the Cryptinae, and the position of related taxa are unclear. According to the earlier classification, which is entirely intuitional, the Cryptinae is divided into three tribes: Cryptini, Hemigasterini and Phygadeuontini. Further, these tribes are subdiveded into numerous subtribes. This work, based on molecular characters, shows that the cryptine tribes Cryptini, Phygadeuon¬tini and Hemigasterini come out largely as monophyletic groups, thus agreeing with the earlier classification. The earlier subtribal classification had no support. In addition, it is shown that modified antennal structures are associated with host usage of wood-boring coleopteran hosts. The cryptines have a clear modification series on their antennal tips from a simply tip to a hammer-like structure. The species with strongly modified antennae belong mostly to the tribe Cryptini and they utilise wood-boring beetles as hosts. Also, field observations on insect behaviour support this result.

Knowledge Transfer within Western Multinationals' Subsidiary Units in China and Finland - The Impact of Headquarter Control Mechanisms, Subsidiary Location and Social Capital (summary section only)

It is suggested that the ability and practices of how the multinational corporation (MNC) manages knowledge transfer among its geographically dispersed subsidiary units are crucial for the building and development of firm competitive advantage. However, cross-border transfer of valuable organizational knowledge is likely to be problematic and laborious, especially within diversified and differentiated MNCs. Using data collected from 164 western multinational companies’ subsidiary units located in China and Finland, this study aims to investigate cross-border knowledge transfer within the MNC. It explores a number of factors that influence the transfer of knowledge among units in the differentiated MNC. The study consists of five individual papers. Paper 1 investigates a range of organizational mechanisms that may positively influence a subsidiary’s propensity to undertake knowledge transfers to other parts of the corporation. Paper 2 explores the impact of subsidiary location on the motivational dispositions of knowledge receiving units to value and accept knowledge from subsidiaries located in economically less advanced countries. Paper 3 examines the influence of social capital variables on knowledge transfer in dyadic relationships between foreign-owned subsidiaries and their sister and patent units. Paper 4 provides some initial insights into potentially different effects of trust and shared vision in intra-organizational vs. inter-organizational relationships. Using a case study setting, Paper 5 explores means and mechanisms used in transferring human resource management practices to Western MNCs’ business units in China from a cultural perspective. The results of the study show that MNC management through choices regarding organizational controls can encourage and enhance corporate-internal knowledge transfer. It also finds evidence that more knowledge is transferred from subsidiaries located in an industrialized country (e.g., Finland) than subsidiaries located in a developing country (e.g., China). While the study has highlighted the importance of social capital in promoting knowledge transfer, it has also uncovered some new findings that the effect of trust and shared vision may be contingent upon different contexts. Finally, in Paper 5, a number of mechanisms used in transferring selected HRM practices and competences to the Chinese business units have been identified. The findings suggest that cultural differences should be taken into consideration in the choice and use of different transfer mechanisms.

Time and Location as Customer Perceived Value Drivers

Since the emergence of service marketing, the focus of service research has evolved. Currently the focus of research is shifting towards value co-created by the customer. Consequently, value creation is increasingly less fixed to a specific time or location controlled by the service provider. However, present service management models, although acknowledging customer participation and accessibility, have not considered the role of the empowered customer who may perform the service at various locations and time frames. The present study expands this scope and provides a framework for exploring customer perceived value from a temporal and spatial perspective. The framework is used to understand and analyse customer perceived value and to explore customer value profiles. It is proposed that customer perceived value can be conceptualised as a function of technical, functional, temporal and spatial value dimensions. These dimensions are suggested to have value-increasing and value-decreasing facets. This conceptualisation is empirically explored in an online banking context and it is shown that time and location are more important value dimensions relative to the technical and functional dimensions. The findings demonstrate that time and location are important not only in terms of having the possibility to choose when and where the service is performed. Customers also value an efficient and optimised use of time and a private and customised service location. The study demonstrates that time and location are not external elements that form the service context, but service value dimensions, in addition to the technical and functional dimensions. This thesis contributes to existing service management research through its framework for understanding temporal and spatial dimensions of perceived value. Practical implications of the study are that time and location need to be considered as service design elements in order to differentiate the service from other services and create additional value for customers. Also, because of increased customer control and the importance of time and location, it is increasingly relevant for service providers to provide a facilitating arena for customers to create value, rather than trying to control the value creation process. Kristina Heinonen is associated with CERS, the Center for Relationship Marketing and Service Management at the Swedish School of Economics and Business Administration