Pedestrian-focused modeling of urban environments is difficult due to a lack of publicly available realistic datasets, and the time and labor-intensive manual processes required to make one, creating barriers to effective evaluation and analysis. In this paper, we introduce GIO.G, a Generator for Indoor-Outdoor Graphs, designed to address these challenges and enhance pedestrian-focused simulation in urban environments. GIO.G offers configurable parameters such as building characteristics, urban density, and foot traffic congestion levels, enabling users to explore a wide range of scenarios with precision and scalability. Through a series of scenarios, we highlight GIO.G’s unique features and showcase GIO.G’s versatility and effectiveness in generating realistic Indoor-Outdoor Graphs.

Energy efficiency has become a primary optimization objective due to the global energy crisis and high levels of CO2emissions. Climate and energy targets have been leading to a growing utilization of solar photovoltaic power generation in residential buildings. As the number of IoT devices drastically increases, their automation through an intelligent home energy management system can provide energy and peak demand savings. The planning optimization of devices can be very challenging due to the unsophisticated user-defined preference rules. Existing solutions face convergence difficulties due to the management of multiple IoT devices tackling multiobjective problems. In this paper, we propose an innovative IoT data system, coined GreenCap, which utilizes a Green Planning evolutionary algorithm for load shifting of IoT-enabled devices, considering the integration of renewable energy sources, multiple constraints, peak-demand times, and dynamic pricing. We have implemented a complete prototype system available on Raspberry Pi and linked with openHAB framework. Our experimental evaluation with extensive real traces shows that the GreenCap prototype system efficiently generates a sustainable plan obtaining high levels of user comfort 92-99% along with ≈52% of self-consumption, while reducing ≈35% of the imported energy from the grid and ≈40% of CO2emissions.

In this demonstration paper, we present an innovative IoT data platform, coined GreenCap, which utilizes a Green Planning evolutionary algorithm for load shifting of IoT-enabled devices in smart environments that feature renewable energy sources. Particularly, GreenCap deploys a hybrid genetic algorithm with domain-specific local search heuristics, which results in a Memetic Algorithm (MA) that offers users an energy efficient allocation plan of their IoT devices, based on their personal preference rules (e.g., operate AC from 10am - 1pm). Our system allocates operations in the daily time-slots considering devices’ energy bounds to minimize the imported energy from the grid, exploit self-consumption and maximize users’ comfort. We demonstrate GreenCap using a complete prototype system available on Raspberry Pi, developed in Laravel using MariaDB and linked to openHAB framework. In our demonstration scenario, attendees will be able to observe through mobile devices the benefits of GreenCap by simulating its execution with real data for one week, using pre-configured or custom rules.

Accessibility and usability have been key concerns in the design of computer interfaces through which users interact with applications and systems. Recently, chatbots have gained popularity with service providers for improvements in this area. In this paper, we present our experience in designing and implementing CAPRIO’s inclusive chatbot-based interface for pedestrian path recommendations. Our CAPRIO system provides inclusive usability by extracting user preferences in a non-intrusive dialog and using them to build a more accurate model for the user’s intent. It uses the Microsoft Bot Framework (MBF) and NLP modeling to support text and voice dialog.

The exposure to viral airborne diseases is higher in crowded and congested spaces, the COVID-19 pandemic has revealed the need of pedestrian recommendation systems that can recommend less congested paths which minimize exposure to infectious crowd diseases in general. In this paper, we introduce ASTRO-C, an extension of previous work ASTRO, which optimizes for minimum congestion. To our knowledge, ASTRO-C is the only solution to this problem of constraint-satisfying, indoor-outdoor, congestion-based path finding. Our experimental evaluation using randomly generated Indoor-Outdoor graphs with varying constraints matching various real-world scenarios, show that ASTRO-C is able to recommend paths with, on average a 0.62X reduction in average congestion, while on average, total travel time increases by 1.06X and never exceeds 1.10X compared to ASTRO.

Accessibility and usability have been key concerns in the design of computer interfaces through which users interact with an application or a system. In developing CAPRIO, our personalized path recommendation system, usability was a design principle for its interface and accessibility was central in its path-finding algorithm, which currently considers user mobility constraints. Motivated by the recent discussions on algorithm biases as well as diversity and inclusion, we have examined the meaning of accessibility under the lens of inclusion and its role in enhancing CAPRIO's development. In this vision paper we discuss how a system like CAPRIO can become fully inclusive that it benefits users from all backgrounds.

In this demo paper, we present the new module of our HealthDist system that performs contact tracing in a privacy-preserving manner and considers the COVID-19 exposure risk. This is achieved by answering a new spatio-temporal query, dubbed ST-Aggregate Join, which calculates the COVID-19 exposure risk of an individual on their devices. It utilizes a special-purpose access structure to record the trajectories of users on their devices and optimize the ST-Aggregate Join processing. We demonstrate interactively using a smartphone application how our system can provide effective contact tracing within a university campus. We also illustrate how our new module is working through an intuitive web interface that shows the exposure risk of a person by coloring the trajectory of the infected person and the person(s) in high risk in a preloaded real dataset.

CAPRIO is an indoor-outdoor pedestrian path rec-ommendation system that optimizes for shortest distance. Its path-finding algorithm, ASTRO, takes into account a set of user-provided congestion constraints and as such can recommend paths that can reduce the risk of COVID-19 exposure. In this paper, we extend ASTRO to consider the changes on congestion when providing path recommendations for overlapping requests. Our new algorithm, called ASTRO-K, can provide K alternative paths that satisfy the congestion constraints of all the path requests within a short time-window. Our experimental eval-uation is conducted using two real-world datasets and shows that ASTRO-K can reduce the total average congestion of the recommended paths up to 4.5X with the trade-off of up to 7% increased total path time.

Since the onset of the Covid-19 pandemic, an over-whelming amount of related data has been released. In an attempt to gain insights from that data, multiple public data visualization dashboards have been deployed. Differently from such dashboards, which mainly support basic data filtering and visualization of separate datasets, in this work, we propose CovidLens, which: 1) integrates various Covid-19 indicators and is centred around the Google Community Mobility Report dataset, 2) supports similarity search for finding similar and correlated patterns and trends across the integrated datasets, and 3) automatically recommends insightful visualizations that unlocks valuable insights into the pandemic effects. To that end, we will be presenting the employed dataset, together with the design, implementation, and multiple usage scenarios of our proposed CovidLens.

Online analytics, in most advanced scientific, business, and social media applications, rely heavily on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs).ACQscontinuously aggregate streaming data and periodically produce results such asmaxoraverageover a given window of the latest data. It has been shown that it is beneficial to useIncremental Evaluation(IE) for re-using calculations performed over parts of theACQwindow, and to share them inmulti-query(MQ) environments among certain sets ofACQs. In this work, we re-examine how the principle of sharing is applied inIEtechniques as well as inMQoptimizers. We provide an extensive taxonomy ofIEtechniques and a new approach of using the state-of-the-artIEtechniques as part ofMQoptimizers in a way that reduces the execution plan costs by up to 270,000x. We evaluate all of our solutions both theoretically and experimentally using both real and synthetic datasets.

Internet of Things (IoT) devices have penetrated massively into smart environments (e.g., smart-homes, smart-cars or more generally smart-anything). Besides data collection, many IoT devices also enable the execution of Rule Automation Workflows (RAW), which span from simple predicate statements to procedural workflows capturing a smart actuation pipeline. RAW aim to meet the convenience (comfort) level of users under specific conditions (e.g., raise room temperature to 22 C if cold), but unfortunately cannot express long-term objectives of users (e.g., consume less than 400 kWh in December). In this paper, we present an innovative system, coined IoT Meta-Control Firewall (IMCF), which internally deploys an AI-inspired Energy-Planner (EP) algorithm that exploits domain-specific operators to balance the trade-off between convenience and energy consumption in satisfying the RAW pipelines of users. IMCF filters the RAW pipelines in a way that these do not conflict with the long-term objectives of users (like a network firewall). Our experimental evaluation with extensive real traces from an apartment, a house, and campus dorms shows that IMCF achieves very high levels of user convenience while remaining within the target energy consumption budgets expressed by users.

The COVID-19 pandemic poses new challenges in providing safe pedestrian navigation information that helps to reduce the risk of severe illness due to the highly contagious nature of the virus. In this paper, we present an innovative system, dubbed HealthDist, which utilizes the context (e.g., weather conditions), location (e.g., crowded areas) and user's preferences to support safe mobility. It consists of four modules that allow efficient contact tracing, social distancing, and isolation. HealthDist's modular design reduces the time and resources needed to provide accurate localization for measuring density in common spaces and measuring potential infection exposure, and recommend outdoor and indoor paths satisfying the user's preferences. HealthDist's initial deployment within a university campus demonstrated its capability to provide real time navigation information that reduces the COVID-19 exposure risk while at the same time satisfying the constraints defined by the user.

In this demo paper, we feature HealthDist, an innovative system that is an additional asset in the fight against the COVID-19 pandemic. HealthDist utilizes context (e.g., weather conditions), location (e.g., crowded areas), and user preferences to provide safe pedestrian paths which decrease the exposure to the virus causing COVID-19. Its modular design, consisting of four components, reduces the time and resources needed to provide accurate localization and indoor-outdoor path recommendations that satisfy the user's preferences. We demonstrate interactively using smartphones how HealthDist can provide real time navigation information within a university campus and illustrate the reduction of the COVID-19 exposure risk while satisfying the constraints defined by the user.Video: http://bit.ly/3bMicbs

Effectively and accurately forecasting the congestion in indoor spaces has become particularly important during the pandemic in order to reduce the risk of exposure to airborne viruses. However, there is a lack of readily available indoor congestion data to train such models. Therefore, in this demo paper we propose EPICGen , an experimental platform for indoor congestion generation to support congestion forecasting in indoor spaces. EPICGen consists of two components: (i) Grid Overlayer , which models the floor plans of buildings; and (ii) Congestion Generator , a realistic indoor congestion generator. We demonstrate EPICGen through an intuitive map-based user interface that enables end-users to customize the parameters of the system and visualize generated datasets.

Driven by the increasing gap between the exponential growth of data and the limited human ability to comprehend them, recently, a novel interactive data exploration approach called Explore-by-Examples has generated a lot of attention for its capabilities to bridge this gap and to help the user obtain high-value content from the data that are often hidden using the traditional search methods. However, despite their effectiveness in extracting valuable information, existing Explore-by-Examples systems focus solely on structured data, which represents a small portion of the data available today. In this work, we present a novel data exploration framework, namely ExNav (Exploration Navigator), which enables the user to effortlessly explore the world of unstructured data for insights that are often unreachable from traditional search and exploration methods. In particular, we exploit the space of advanced machine learning, data embedding, and active learning algorithms to design effective exploration and space pruning approaches tailored for unstructured datasets. Our experimental evaluation using multiple real-world unstructured datasets (i.e., text, image, and graph) show that ExNav can reduce users' effort by up to 9x while still achieving the same accuracy as the state-of-the-art alternative. Moreover, ExNav is also able to identify relevant data items that are often undetectable by current techniques, even when a large number of samples are explored.

Stream Processing Engines (SPEs) are used for realtime and continuous processing with stateful operations. This type of processing poses numerous challenges due to its associated complexity, unpredictable input, and need for timely results. As a result, users tend to overprovision resources, and online scaling is required in order to overcome overloaded situations. Current attempts for expediting stateful processing are impractical, due to their inability to uphold the quality of results, maintain performance, and reduce memory requirements. In this paper, we present the SPEAr system, which can expedite processing of stateful operations automatically by trading accuracy for performance. SPEAr detects when it can accelerate processing by employing online sampling and accuracy estimation at no additional cost. We built SPEAr on top of Storm and our experiments indicate that it can reduce processing times by more than an order of magnitude, use more than an order of magnitude less memory, and offer accuracy guarantees in real-world benchmarks.

The CAPRIOv2.0 system is the evolution of CAPRIO, our context-aware path recommendation system that has as its primary objectives the minimum outdoor exposure and distance of the recommended path. CAPRIOv2.0 offers enhanced indoor context-awareness in terms of accessibility and congestion. In this demonstration, we exhibit CAPRIOv2.0 and present its novel graph representation that integrates accessibility, congestion, indoor, and outdoor information to discover paths satisfying accessibility, outdoor exposure, and distance constraints of an individual. We further present a new spatial model index, called SMI-tree, which enables CAPRIO v2.0 to quickly forecast the congestion in corridors and hallways. Individuals can interactively engage with the CAPRIOv2.0 GUI using any of their devices to appreciate how our proposed structures and algorithms can provide an alternative context-aware path by combining outdoor, indoor, congestion and accessibility information.Video https://db.cs.pitt.edu/caprio/v2.

During extreme weather conditions and natural disasters caused by meteorological phenomena, it is imperative to enable navigation that minimizes the outdoor section of recommended paths. Existing indoor-outdoor navigation and localization systems have evolved to support queries like the shortest distance, either outdoor or indoor, with additional constraints. However, most of them work in isolation and do not take into consideration the external natural conditions, like the weather, that an individual may experience walking outside during a polar vortex or heatwave. In this paper, we present CAPRIO, a context-aware path recommendation system whose objectives are two-fold: (i) minimizing outdoor exposure; and (ii) minimizing the distance of the recommended path. We propose a novel graph representation that integrates indoor and outdoor information to discover paths that satisfy outdoor exposure and distance constraints. We measure the efficiency of the proposed solution using two real datasets collected from the University of Pittsburgh and University of Cyprus campuses. We show that we can achieve comparable distance to the state-of-the-art in minimizing outdoor exposure.

Traffic congestion has a significant negative impact on the accelerating pace of daily human activities. Traffic jams increase the transportation costs for goods and humans. They are also amongst the leading factors for pollution in the atmosphere and consequently increase health risks for the population. One way to reduce the amount of emissions produced by vehicles in traffic jams is to mitigate traffic congestion and promote the usage of public transportation. In this paper, we propose a solution that establishes on-demand, virtual bus lanes to prioritize public transportation over other traffic and provide detour guidelines for other drivers, while causing insignificant detour penalties. Our solution leverages incremental window aggregations to identify the busiest road segments, priority scheduling, and Dijkstra shortest path algorithm to shape and detour traffic. Our experimental evaluation shows the effectiveness of our Environment Protective Traffic Orchestration (EPTrOn) algorithm in identifying and alleviating traffic congestions.

Recently, navigation and localization systems have emerged to support queries like the shortest distance in either indoor or outdoor with additional constraints. These systems, however, neither combine the indoor and outdoor information nor consider the external natural conditions like the weather that one may face across an outdoor path. In this demonstration paper we present CAPRIO , which proposes and implements a novel graph representation that integrates indoor and outdoor information to discover paths that personalize outdoor exposure while minimizes the overall path length. We also demonstrate how unifying the graph algorithms for indoor and outdoor navigation enables significant optimizations that would not be possible otherwise.

Load shedding is a technique that aims to ameliorate the consequences of the Velocity and the Volume of Big Data stream processing. When temporal input spikes appear, tuples are shed until a Stream Processing Engine's (SPE) processing capacity is not overwhelmed and results are produced in a timely fashion. Existing load shedding techniques have become obsolete and are not applicable to modern use-cases which require the extraction of patterns from continuously evolving (i.e., Variable) voluminous streams.In this work, we identify the shortcomings of existing load shedding techniques when applied to streams with concept drift. We propose Concept-Driven load shedding (CoD), which aims at limiting the data volume imposed on the SPE while producing high accuracy results. On top of that, we designed CoD for modern SPEs and made its overhead negligible. Our experiments indicate that CoD can deliver more than 10x more accurate results compared to the state of the art in load shedding. Also, CoD can offer up to 2.25× better performance compared to normal processing and reduce the processed data volume significantly.

Data Management (DM), like many areas of computer science (CS), relies on empirical evaluation that uses software, data sets and benchmarks to evaluate new ideas and compare with past innovation. Despite the importance of these artifacts and associated information about experimental evaluations, few researchers make these available in a findable, accessible, interoperable and reusable (FAIR) manner, in this way hindering the scientific process by limiting open collaboration, credibility of published outcomes, and research progress. Fortunately, this problem is recognized and many CS communities, including the DM one, are advocating and providing incentives for software and analysis papers to follow FAIR principles and be treated equally to traditional publications. Some ACM/IEEE conferences adopted Artifact Evaluation (AE) to reward authors for doing a great job in conducting experiments with FAIR software and data. After half a decade since AE's inception, the question is whether the emerging emphasis on artifacts, is having a real impact in CS research.

Recent studies in urban navigation have revealed new demands (e.g., diversity, safety, happiness, serendipity) for the navigation services that are critical to providing useful recommendations to travelers. This exposes the need to design next-generation navigation services that accommodate these newly emerging aspects. In this paper, we present a prototype system, namely, EPUI (an Experimental Platform of Urban Informatics), which provides a testbed for exploring and evaluating venues and route recommendation solutions that balance between different objectives (i.e., demands) including the newly discovered ones. In addition, EPUI incorporates a modularized design, enabling researchers to upload their own algorithms and compare them to well-known algorithms using different performance metrics. Its user interface makes it easily usable by both end-user and experienced researchers.

Data visualization is a common and effective technique for data exploration. However, for complex data, it is infeasible for an analyst to manually generate and browse all possible visualizations for insights. This observation motivated the need for automated solutions that can effectively recommend such visualizations. The main idea underlying those solutions is to evaluate the utility of all possible visualizations and then recommend the top-k visualizations. This process incurs high data processing cost, that is further aggravated by the presence of numerical dimensional attributes. To address that challenge, we propose novel view recommendation schemes, which incorporate a hybrid multi-objective utility function that captures the impact of numerical dimension attributes. Our first scheme, Multi-Objective View Recommendation for Data Exploration (MuVE), adopts an incremental evaluation of our multi-objective utility function, which allows pruning of a large number of low-utility views and avoids unnecessary objective evaluations. Our second scheme, upper MuVE (uMuVE), further improves the pruning power by setting the upper bounds on the utility of views and allowing interleaved processing of views, at the expense of increased memory usage. Finally, our third scheme, Memory-aware uMuVE (MuMuVE), provides pruning power close to that of uMuVE, while keeping memory usage within a pre-specified limit.

In this demo we present a prototype of an experimental platform for evaluating item recommendation algorithms. The application domain for our system is that of digital city guides. Our prototype implementation allows the user to explore different algorithms and compare their output. Among the algorithms implemented is MPG, which aims at providing a diverse set of recommendations better aligned with user preferences. MPG takes into consideration the user preferences (e.g., reach willing to cover, types of venues interested in exploring etc.), the popularity of the establishments as well as their distance from the current location of the user by combining them into a single composite score. We provide a web interface, which outputs on a map the recommended locations along with metadata (e.g., type and name of location, relevance and diversity scores, etc.). It also illustrates the potential of the Preferential Diversity approach on which MPG is based.

The exponential growth of high dimensional biological data has led to a rapid increase in demand for automated approaches for knowledge production. Existing methods rely on two general approaches to address this challenge: 1) the Theory-driven approach, which utilizes prior accumulated knowledge, and 2) the Data-driven approach, which solely utilizes the data to deduce scientific knowledge. Both of these approaches alone suffer from bias toward past/present knowledge, as they fail to incorporate all of the current knowledge that is available to make new discoveries. In this paper, we show how an integrated method can effectively address the high dimensionality of big biological data, which is a major problem for pure data-driven analysis approaches. We realize our approach in a novel two-step analytical workflow that incorporates a new feature selection paradigm as the first step to handling high-throughput gene expression data analysis and that utilizes graphical causal modeling as the second step to handle the automatic extraction of causal relationships. Our results, on real-world clinical datasets from The Cancer Genome Atlas (TCGA), demonstrate that our method is capable of intelligently selecting genes for learning effective causal networks.

Data stream processing is becoming essential in most current advanced scientific or business applications as data production rates are increasing. Different companies compete to efficiently ingest high velocity data and apply some form of computation in order to make better business decisions. In order to successfully compete in this environment, companies are focusing on the most recent data within a count or time-based window by continuously executing aggregate queries on it. Incremental sliding-window computation is commonly used to avoid the performance implications of re-evaluating the aggregate value of the window from scratch on every update. The state-of-the-art FlatFAT technique executes ACQs with high efficiency but it does not scale well with the increasing workloads. In this paper we propose a novel algorithm, FlatFIT, that accelerates such calculations by intelligently maintaining index structures, leading to higher reuse of intermediate calculations and thus exceptional scalability in systems with heavy workloads. Our theoretical analysis shows that FlatFIT is superior in both time and space complexities compared to FlatFAT, while maintaining the same query generality. Given a window of size n, FlatFIT achieves constant algorithmic complexity compared to O(log(n)) complexity of FlatFAT. We experimentally show that FlatFIT achieves up to a 17x throughput improvement over FlatFAT for the same input workload while using less memory.

Stream processing has become the dominant processing model for monitoring and real-time analytics. Modern Parallel Stream Processing Engines (pSPEs) have made it feasible to increase the performance in both monitoring and analytical queries by parallelizing a query's execution and distributing the load on multiple workers. A determining factor for the performance of a pSPE is the partitioning algorithm used to disseminate tuples to workers. Until now, partitioning methods in pSPEs have been similar to the ones used in parallel databases and only recently load-aware algorithms have been employed to improve the effectiveness of parallel execution. We identify and demonstrate the need to incorporate aggregation costs in the partitioning model when executing stateful operations in parallel, in order to minimize the overall latency and/or through-put. Towards this, we propose new stream partitioning algorithms, that consider both tuple imbalance and aggregation cost. We evaluate our proposed algorithms and show that they can achieve up to an order of magnitude better performance, compared to the current state of the art.

Exploration over large datasets is a key first step in data analysis, as users may be unfamiliar with the underlying database schema and unable to construct precise queries that represent their interests. Such data exploration task usually involves executing numerous ad-hoc queries, which requires a considerable amount of time and human effort. In this paper, we present REQUEST, a novel framework that is designed to minimize the human effort and enable both effective and efficient data exploration. REQUEST supports the query-from-examples style of data exploration by integrating two key components: 1) Data Reduction, and 2) Query Selection. As instances of the REQUEST framework, we propose several highly scalable schemes, which employ active learning techniques and provide different levels of efficiency and effectiveness as guided by the user's preferences. Our results, on real-world datasets from Sloan Digital Sky Survey, show that our schemes on average require 1-2 orders of magnitude fewer feedback questions than the random baseline, and 3-16× fewer questions than the state-of-the-art, while maintaining interactive response time. Moreover, our schemes are able to construct, with high accuracy, queries that are often undetectable by current techniques.

The increasing popularity and ubiquity of various large graph datasets has caused renewed interest for graph partitioning. Existing graph partitioners either scale poorly against large graphs or disregard the impact of the underlying hardware topology. A few solutions have shown that the nonuniform network communication costs may affect the performance greatly. However, none of them considers the impact of resource contention on the memory subsystems (e.g., LLC and Memory Controller) of modern multicore clusters. They all neglect the fact that the bandwidth of modern high-speed networks (e.g., Infiniband) has become comparable to that of the memory subsystems. In this paper, we provide an in-depth analysis, both theoretically and experimentally, on the contention issue for distributed workloads. We found that the slowdown caused by the contention can be as high as 11x. We then design an architecture-aware graph partitioner, Argo, to allow the full use of all cores of multicore machines without suffering from either the contention or the communication heterogeneity issue. Our experimental study showed (1) the effectiveness of Argo, achieving up to 12x speedups on three classic workloads: Breadth First Search, Single Source Shortest Path, and PageRank; and (2) the scalability of Argo in terms of both graph size and the number of partitions on two billion-edge real-world graphs.

With the explosion of large, dynamic graph datasets from various fields, graph partitioning and repartitioning are becoming more and more critical to the performance of many graph-based Big Data applications, such as social analysis, web search, and recommender systems. However, well-studied graph (re)partitioners usually assume a homogeneous and contention-free computing environment, which contradicts the increasing communication heterogeneity and shared resource contention in modern, multicore high performance computing clusters. To bridge this gap, we introduce PARAGON, a parallel architecture-aware graph partition refinement algorithm, which mitigates the mismatch by modifying a given decomposition according to the nonuniform network communication costs and the contentiousness of the underlying hardware topology. To further reduce the overhead of the refinement, we also make PARAGON itself architecture-aware. Our experiments with a diverse collection of datasets showed that on average PARAGON improved the quality of graph decompositions computed by the de-facto standard (hashing partitioning) and two state-of-the-art streaming graph partitioning heuristics (deterministic greedy and linear deterministic greedy) by 43%, 17%, and 36%, respectively. Furthermore, our experiments with an MPI implementation of Breadth First Search and Single Source Shortest Path showed that, in comparison to the state-of-the-art streaming and multi-level graph (re)partitioners, PARAGON achieved up to 5.9x speedups. Finally, we demonstrated the scalability of PARAGON by scaling it up to a graph with 3.6 billion edges using only 3 machines (60 physical cores).

To support effective data exploration, there is a well-recognized need for solutions that can automatically recommend interesting visualizations, which reveal useful insights into the analyzed data. However, such visualizations come at the expense of high data processing costs, where a large number of views are generated to evaluate their usefulness. Those costs are further escalated in the presence of numerical dimensional attributes, due to the potentially large number of possible binning aggregations, which lead to a drastic increase in the number of possible visualizations. To address that challenge, in this paper we propose the MuVE scheme for Multi-Objective View Recommendation for Visual Data Exploration. MuVE introduces a hybrid multi-objective utility function, which captures the impact of binning on the utility of visualizations. Consequently, novel algorithms are proposed for the efficient recommendation of data visualizations that are based on numerical dimensions. The main idea underlying MuVE is to incrementally and progressively assess the different benefits provided by a visualization, which allows an early pruning of a large number of unnecessary operations. Our extensive experimental results show the significant gains provided by our proposed scheme.

Graph partitioning is an essential preprocessing step in distributed graph computation and scientific simulations. Existing well-studied graph partitioners are designed for static graphs, but real-world graphs, such as social networks and Web networks, keep changing dynamically. In fact, the communication and computation patterns of some graph algorithms may vary significantly, even across their different computation phases. This means that the optimal partitioning changes over time, requiring the graph to be repartitioned periodically to maintain good performance. However, the state-of-the-art graph (re)partitioners are known for their poor scalability against massive graphs. Furthermore, they usually assume a homogeneous and contention-free computing environment, which is no longer true in modern high performance computing infrastructures. In this paper, we introduce Planar, a parallel lightweight graph repartitioner, which does not require full knowledge of the graph and incrementally adapts the partitioning to changes while considering the heterogeneity and contentiousness of the underlying computing infrastructure. Using a diverse collection of datasets, we showed that, in comparison with the de-facto standard and two state-of-the-art streaming graph partitioning heuristics, Planar improved the quality of graph partitionings by up to 68%, 46%, and 69%, respectively. Furthermore, our experiments with an MPI implementation of Breadth First Search and Single Source Shortest Path showed that Planar achieved up to 10x speedups against the state-of-the-art streaming and multi-level graph (re)partitioners. Finally, we scaled Planar up to a graph with 3.6 billion edges.

The proliferation of mobile, ubiquitous and spatial computing has led to a number of services aiming into facilitate the exploration of a city. Platforms such as Foursquare and Yelp curate information about establishments in an area that can then be used for recommendation purposes. Traditionally an approach followed by these systems is to rank places based on their popularity, proximity or any other feature that represents the quality of the venue and then return the top-k of them. However, this approach, while simple and intuitive, is not necessarily providing a diverse set of recommendations, since similar venues typically are ranked closely. Therefore, in this paper we design and introduce MPG (which stands for Mobile Personal Guide), a mobile service that provides a set of diverse venue recommendations better aligned with user preferences. MPG takes into consideration the user preferences (e.g., distance willing to cover, types of venues interested in exploring, etc.), the popularity of the establishments, as well as their distance from the current location of the user by combining them in a single composite score. We evaluate our approach using a large-scale dataset of approximately 14 million venues collected from Foursquare. Our results indicate that MPG can increase coverage of the result set compared to the baselines considered. It further achieves a significantly better Relevancy-Diversity trade-off ratio.

Data Stream Management Systems performing on-line analytics rely on the efficient execution of large numbers of Aggregate Continuous Queries (ACQs). The state-of-the-art WeaveShare optimizer uses the Weavability concept in order to selectively combine ACQs for partial aggregation and produce high quality execution plans. However, WeaveShare does not scale well with the number of ACQs. In this paper we propose a novel closed formula, F1, that accelerates Weavability calculations, and thus allows WeaveShare to achieve exceptional scalability in systems with heavy workloads. In general, F1 can reduce the computation time of any technique that combines partial aggregations within composite slides of multiple ACQs. We theoretically analyze the Bit Set approach currently used by WeaveShare and show that F1 is superior in both time and space complexities. We show that F1 performs 1062 times less operations compared to Bit Set to produce the same execution plan for the same input. We experimentally show that F1 executes up to 60,000 times faster and can handle 1,000,000 ACQs in a setting where the limit for the current technique is 550.

PASQL is an extension to SQL that allows users of a distributed database to specify privacy constraints on an SQL query evaluation plan. However, privacy constraints can be difficult for users to specify, and worse yet, all possible situations that could lead to a privacy violation may not be known to the user a priori. To address these challenges, we propose a GUI-based interactive process for detecting such violations and generating appropriate constraints. In this work, we demonstrate two approaches to implementing such a GUI that provide different ways of analyzing and interactively optimizing a PASQL query plan.

Wi-Fi (or WLAN) based indoor navigation applications for mobiles rely on cloud-based services (s) that take care of a user's (u) localization task using structures called Radio Maps (RMs). It is imperative for u to have a stable WiFi connection in order to either continuously receive location updates from s or to download RMs a priori for offline navigation. Wi-Fi networks however, suffer from intermittent connectivity due to poor network planning that results in sparse deployment of access points and effectively areas where Wi-Fi coverage cannot be guaranteed. This inherently affects the localization accuracy and therefore the navigation experience of users. In this paper, we propose an innovative framework for accurate and fast indoor localization over an intermittently connected WiFi network, coined Prefetching Localization (PreLoc). In Preloc, we prioritize the download of RM records based on knowledge acquired from historic traces of other users inside the same building. Instead of downloading the complete RM from s to u, we propose a Probabilistic Group Selection (PGS) strategy, which identifies RM records that have a higher probability of being necessary to a user moving inside a target area. We have evaluated our framework using a real prototype developed in Android, as well as realistic Wi-Fi traces we collected at the University of Cyprus. Our experimental study reveals that PreLoc using PGS and conventional fingerprint-based indoor positioning algorithms can yield accuracy that is as good as using the same algorithms with a complete RM, even under scenarios of weak Wi-Fi coverage.

Data Stream Management Systems (DSMS) are crucial for modern high-volume/high-velocity data-driven applications, necessitating a distributed approach to processing them. In addition, data providers often require certain levels of confidentiality for their data, especially in cases of user-generated data, such as those coming out of physical activity/health tracking devices (i.e., our motivating application). This demonstration will showcase Synefo, an infrastructure that enables elastic scaling of DSMS operators, and CryptStream, a framework that provides confidentiality and access controls for data streams while allowing computation on untrusted servers, fused as CE-Storm. We will demonstrate both systems working in tandem and also visualize their behavior over time under different scenarios.

Graph partitioning and repartitioning have been widely used by scientists to parallelize compute- and dataintensive simulations. However, existing graph (re)partitioning algorithms usually assume homogeneous communication costs among partitions, which contradicts the increasing heterogeneity in inter-core communication in modern parallel architectures and is further exacerbated by increasing dataset sizes (i.e., Big Data). To resolve this, we propose an architecture-aware graph repartitioner, called AragonLB. AragonLB considers the heterogeneity in both inter- and intra-node communication while rebalancing the load. Our experimental study with a turbulent combustion simulation dataset shows that AragonLB can result in up to 60% improvement against existing architecture-agnostic graph repartitioners (which assume uniform communication costs among partitions), and the improvement becomes more significant as the number of computation steps, the number of partitions, or the size of the interconnect increase.

The declarative nature of SQL has traditionally been a major strength. Users simply state what information they are interested in, and the database management system determines the best plan for retrieving it. A consequence of this model is that should a user ever want to specify some aspect of how their queries are evaluated (e.g., a preference to read data from a specific replica, or a requirement for all joins to be performed by a single server), they are unable to. This can leave database administrators shoehorning evaluation preferences into database cost models. Further, for distributed database users, it can result in query evaluation plans that violate data handling best practices or the privacy of the user. To address such issues, we have developed a framework for declarative, user-specified constraints on the query optimization process and implemented it within PosgreSQL. Our Preference-Aware Query Optimizer (PAQO) upholds both strict requirements and partially ordered preferences that are issued alongside of the queries that it processes. In this paper, we present the design of PAQO and thoroughly evaluate its performance.

Although the declarative nature of SQL provides great utility to database users, its use in distributed database management systems can leave users unaware of which servers in the system are evaluating portions of their queries. By allowing users to merely say what data they are interested in accessing without providing guidance regarding how to retrieve it, query optimizers can generate plans with unintended consequences to the user (e.g., violating user privacy by revealing sensitive portions of a user's query to untrusted servers, or impacting result freshness by pulling data from stale data stores). To address these types of issues, we have created a framework that empowers users with the ability to specify constraints on the kinds of plans that can be produced by the optimizer to evaluate their queries. Such constraints are specified through an extended version of SQL that we have developed which we call PASQL. With this proposal, we aim to demonstrate PAQO, a version of PostgreSQL's query optimizer that we have modified to produce plans that respect constraints specified through PASQL while optimizing user-specified SQL queries in terms of performance.

Aggregate Continuous Queries (ACQs) are both a very popular class of Continuous Queries (CQs) and also have a potentially high execution cost. As such, optimizing the processing of ACQs is imperative for Data Stream Management Systems (DSMSs) to reach their full potential in supporting (critical) monitoring applications. For multiple ACQs that vary in window specifications and pre-aggregation filters, existing multiple ACQs optimization schemes assume a processing model where each ACQ is computed as a final-aggregation of a sub-aggregation. In this paper, we propose a novel processing model for ACQs, called Tri Ops, with the goal of minimizing the repetition of operator execution at the sub-aggregation level. We also propose Tri Weave, a Tri Ops-aware multi-query optimizer. We analytically and experimentally demonstrate the performance gains of our proposed schemes which shows their superiority over alternative schemes. Finally, we generalize Tri Weave to incorporate the classical subsumption-based multi-query optimization techniques.

This demo presents AstroShelf, our on-going effort to enable astrophysicists to collaboratively investigate celestial objects using data originating from multiple sky surveys, hosted at different sites. The AstroShelf platform combines database and data stream, workflow and visualization technologies to provide a means for querying and displaying telescope images (in a Google Sky manner), visualizations of spectrum data, and for managing annotations. In addition to the user interface, AstroShelf supports a programmatic interface (available as a web service), which allows astrophysicists to incorporate functionality from AstroShelf in their own programs. A key feature is Live Annotations which is the detection and delivery of events or annotations to users in real-time, based on their profiles. We demonstrate the capabilities of AstroShelf through real end-user exploration scenarios (with participation from "stargazers" in the audience), in the presence of simulated annotation workloads executed through web services.

Data Streams Management Systems are designed to support monitoring applications, which require the processing of hundreds of Aggregate Continuous Queries (ACQs). These ACQs typically have different time granularities, with possibly different selection predicates and group-by attributes. In order to achieve scalability in the presence of heavy workloads, in this paper, we introduce the concept of 'Weaveability' as an indicator of the potential gains of sharing the processing of ACQs. We then propose Weave Share, a cost-based optimizer that exploits weaveability to optimize the shared processing of ACQs. Our experimental analysis shows that Weave Share outperforms the alternative sharing schemes generating up to four orders of magnitude better quality plans. Finally, we describe a practical implementation of the Weave Share optimizer.

Energy consumption for computing devices in general and for data centers in particular is receiving increasingly high attention, both because of the increasing ubiquity of computing and also because of increasing energy prices. In this work, we propose QMD (Quasi Mirrored Disks) that exploit flash as a write buffer to complement RAID systems consisting of hard disks. QMD along with partial on-line mirrors, are a first step towards energy proportionality which is seen as the holy grail of energy-efficient system design. QMD exhibits significant energy savings of up 31%, as per our evaluation study using real workloads.

Complex event detection over data streams has become ubiquitous through the widespread use of sensors, wireless connectivity and the wide variety of end-user mobile devices. Typically, such event detection is carried out by a data stream management system executing continuous queries (CQs), registered by the users. In this paper, we consider the situation where the results of the CQs, which are in the form of individual data streams, are disseminated to the users' hand-held, battery-operated devices over a shared broadcast medium. In order to reduce the overall energy consumption of the mobile devices, we propose Bose*, a power-aware query operator placement algorithm that determines which part of a CQ plan should be executed at the data stream management system and which part should be executed at the mobile device. Bose*'s effectiveness in reducing energy consumption, as well as response time under specific conditions, is evaluated using simulation, driven by parameters measured on real mobile devices.

Complex event detection over data streams has become ubiquitous through the widespread use of sensors, wireless connectivity and the wide variety of end-user mobile devices. Typically, event detection is carried out by a central server executing continuous queries. In this demonstration, we focus on the case where users with mobile devices submit continuous queries (for event detection) to a data stream management server which disseminates the results to the users over a shared broadcast medium. In order to minimize the overall energy consumption of the mobile devices (clients), we have proposed operator placement algorithms that split the processing of each continuous query between the centralized server and the requesting mobile clients, thus trading off energy consumption for communication energy consumption for computation. Specifically, in this demonstration, we present an interactive graphical interface to the inner workings of our three proposed operator placement algorithms, whereby attendees are able to investigate various query plans and the decisions that the algorithms make, as well as visualize the results of these algorithms in terms of client power consumption and response time. Besides being able to step through an algorithm's execution as it considers various operator placement decisions, attendees are able to experiment with different scenarios by customizing the parameters of the query workloads (e.g., changing the selectivities and projectivities of the operators) or the client's profile (e.g., power consumed per unit of time of processing) and examine the impact.

Traditional workflow enactment systems view a workflow as a one-time interaction with various data sources, executing a series of steps once, whenever the workflow results are requested. The fundamental underlying assumption has been that data sources are passive and all interactions are structured along the request/reply (query) model. Hence, traditional Workflow Management Systems cannot effectively support business or scientific reactive applications that require the processing of continuous data streams.

Amazon, Google, and IBM now sell cloud computing services.We consider the setting of a for-profit business selling data stream monitoring/management services and we investigate auction-based mechanisms for admission control of continuous queries. When submitting a query, each user also submits a bid of how much she is willing to pay for that query to run. The admission control auction mechanism then determines which queries to admit, and how much to charge each user in a way that maximizes system revenue while being strategyproof and sybil immune, incentivizing users to use the system honestly. Specifically, we require that each user maximizes her payoff by bidding her true value of having her query run. We design several payment mechanisms and experimentally evaluate them. We describe the provable game theoretic characteristics of each mechanism alongside its performance with respect to maximizing profit and total user payoff.

This demo presents a graphical user interface and ranking system, coined KSpot, for effectively monitoring the K highest-ranked answers to a query Q in a wireless sensor network. KSpot deploys state-of-the-art distributed top-k query processing algorithms in order to realize both snapshot queries and historic queries minimizing the consumption of system resources and prolonging the lifetime of the deployed sensor network. Additionally, KSpot is user-friendly and customizable featuring an intuitive user interface that enables a user to express declarative SQL-like queries over any ad-hoc scenario and to display the results graphically as opposed to the traditional tabular representation. To demonstrate the applicability of our system during the conference, we will continuously identify the K conference rooms with the highest sound level and display them such that conference attendees will be able to quickly determine the rooms with the most active discussions. The demo will also allow attendees to customize the system by changing the target scenario (e.g., by adapting the K value, the sensed parameter, etc.) Finally, we will present KSpot's system panel which continuously displays the savings in energy and messages that our system yields.

In highly interactive dynamic Web database systems, user satisfaction determines their success. In such systems, user requested web pages are dynamically created by executing a number of database queries or Web transactions. In this paper, we model the interrelated transactions generating a web page asworkflowsand quantify the user satisfaction by associating dynamic Web pages withsoft-deadlines. Further, we model the importance of transactions in generating a page by associating different weights to transactions. Using this framework, system success is measured in terms of minimizing the deviation from the deadline (i.e., tardiness) and also minimizing the weighted such deviation (i.e., weighted tardiness). In order to efficiently support the materialization of dynamic Web pages, we proposeASETS*, which is a parameter-free adaptive scheduling algorithm that automatically adapts to, not only system load, but also transactions' characteristics (i.e., interdependencies, deadlines and weights).ASETS* prioritizes the execution of transactions with the objective of minimizing weighted tardiness. It is also capable of balancing the tradeoff between optimizing average- and worst-case performance when needed. The performance advantages ofASETS* are experimentally demonstrated.

Continuous queries in wireless sensor networks (WSNs) are founded on the premise of query routing tree structures (denoted as T), which provide sensors with a path to the querying node. Predominant data acquisition systems for WSNs construct such structures in an ad-hoc manner and therefore there is no guarantee that a given query workload will be distributed equally among all sensors. That leads to data collisions which represent a major source of energy waste. In this paper we present the energy-driven tree construction (ETC) algorithm, which balances the workload among nodes and minimizes data collisions, thus reducing energy consumption, during data acquisition in WSNs. We show through real micro-benchmarks on the CC2420 radio chip and trace-driven experimentation with real datasets from Intel Research and UC-Berkeley that ETC can provide significant energy reductions under a variety of conditions prolonging the longevity of a wireless sensor network.

This paper assumes a set of n mobile sensors that move in the Euclidean plane as a swarm. Our objectives are to explore a given geographic region by detecting spatio-temporal events of interest and to store these events in the network until the user requests them. Such a setting finds applications in mobile environments where the user (i.e., the sink) is infrequently within communication range from the field deployment. Our framework, coined SenseSwarm, dynamically partitions the sensing devices into perimeter and core nodes. Data acquisition is scheduled at the perimeter, in order to minimize energy consumption, while storage and replication takes place at the core nodes which are physically and logically shielded to threats and obstacles. To efficiently identify the nodes laying on the perimeter of the swarm we devise the Perimeter Algorithm (PA), an efficient distributed algorithm with a low communication complexity. For storage and fault-tolerance we devise the Data Replication Algorithm (DRA), a voting-based replication scheme that enables the exact retrieval of events from the network in cases of failures. Our trace-driven experimentation shows that our framework can offer significant energy reductions while maintaining high data availability rates. In particular, we found that when failures are less than 60% failure then we can recover over 80% of generated events exactly.

The performance provided by an interactive online database system is typically measured in terms of meeting certain pre-specified Service Level Agreements (SLAs), with expected transaction latency being the most commonly used type of SLA. This form of SLA acts as a soft deadline for each transaction, and user satisfaction can be measured in terms of minimizing tardiness, that is, the deviation from SLA. This objective is further complicated for I/O-intensive transactions, where the storage system becomes the performance bottleneck. Moreover, common I/O scheduling policies employed by the Operating System with a goal of improving I/O throughput or average latency may run counter to optimizing per-transaction performance since the Operating System is typically oblivious to the application high-level SLA specifications. In this paper, we propose a new SLA-aware policy for scheduling I/O requests of database transactions. Our proposed policy synergistically combines novel deadline-aware scheduling policies for database transactions with features of Operating System scheduling policies designed for improving I/O throughput. This enables our proposed policy to dynamically adapt to workload and consistently provide the best performance.

The use of atomic commit protocols in mobile ad-hoc networks involves difficulties in setting up reasonable time-outs for aborting a pending distributed transaction. This paper presents the non-blocking adjourn state, a concurrency control modification which makes time-outs in an atomic commit protocol for aborting a transaction unnecessary. Further, it enhances concurrency among transactions performing conflicting accesses to resources used by completed distributed transactions waiting for the commit protocol to be initiated.

Continuous queries in wireless sensor networks are established on the premise of a routing tree that provides each sensor with a path over which answers can be transmitted to the query processor. We found that these structures are sub- optimality constructed in predominant data acquisition systems leading to an enormous waste of energy. In this paper we present MicroPulse1, a workload-aware optimization algorithm for query routing trees in wireless sensor networks. Our algorithm is established on profiling recent data acquisition activity and on identifying the bottlenecks using an in-network execution of the critical path method. A node S utilizes this information in order to locally derive the time instance during which it should wake up, the interval during which it should deliver its workload and the workload increase tolerance of its parent node. We additionally provide an elaborate description of energy-conscious algorithms for disseminating and maintaining the critical path cost in a distributed manner. Our trace-driven experimentation with real sensor traces from Intel Research Berkeley shows that MicroPulse can reduce the data acquisition costs by many orders.

Recently, several policies have been proposed for scheduling multiple Continuous Queries (CQs) in a Data Stream Management System (DSMS). The decision on which policy to use plays an important role in shaping the percieved online performance provided by the DSMS. In this tutorial, we provide an overview of different policies employed by current CQ schedulers and the performance goals optimized by these policies. Further, we discuss the salient properties of CQs conisdered by current policies as well as the efficent implementation of such policies into CQ schedulers. Finally, we present future research directions and open problems in CQ scheduling.

The emergence of monitoring applications has precipitated the need for Data Stream Management Systems (DSMSs), which constantly monitor incoming data feeds (through registered continuous queries), in order to detect events of interest. In this article, we examine the problem of how to schedule multiple Continuous Queries (CQs) in a DSMS to optimize different Quality of Service (QoS) metrics. We show that, unlike traditional online systems, scheduling policies in DSMSs that optimize for average response time will be different from policies that optimize for average slowdown, which is a more appropriate metric to use in the presence of a heterogeneous workload. Towards this, we propose policies to optimize for the average-case performance for both metrics. Additionally, we propose a hybrid scheduling policy that strikes a fine balance between performance and fairness, by looking at both the average- and worst-case performance, for both metrics. We also show how our policies can be adaptive enough to handle the inherent dynamic nature of monitoring applications. Furthermore, we discuss how our policies can be efficiently implemented and extended to exploit sharing in optimized multi-query plans and multi-stream CQs. Finally, we experimentally show using real data that our policies consistently outperform currently used ones.

In this paper we introduce MINT (materialized in-network top-k) Views, a novel framework for optimizing the execution of continuous monitoring queries in sensor networks. A typical materialized view V maintains the complete results of a query Q in order to minimize the cost of future query executions. In a sensor network context, maintaining consistency between V and the underlying and distributed base relation R is very expensive in terms of communication. Thus, our approach focuses on a subset V(sube. V) that unveils only the k highest-ranked answers at the sink for some user defined parameter k. We additionally provide an elaborate description of energy-conscious algorithms for constructing, pruning and maintaining such recursively- defined in-network views. Our trace-driven experimentation with real datasets show that MINT offers significant energy reductions compared to other predominant data acquisition models.

In this paper we present MicroPulse, a novel framework for adapting the waking window of a sensing device S based on the data workload incurred by a query Q. Assuming a typical tree-based aggregation scenario, the waking window is defined as the time interval r during which S enables its transceiver in order to collect the results from its children. Minimizing the length of r enables S to conserve energy that can be used to prolong the longevity of the network and hence the quality of results. Our method is established on profiling recent data acquisition activity and on identifying the bottlenecks using an in-network execution of the Critical Path Method. We show through trace- driven experimentation with a real dataset that MicroPulse can reduce the energy cost of the waking window by three orders of magnitude.

We propose an In-Network Data-Centric Storage (INDCS) scheme for answering ad-hoc queries in sensor networks. Previously proposed In-Network Storage (INS) schemes suffered from Storage Hot-Spots that are formed if either the sensors' locations are not uniformly distributed over the coverage area, or the distribution of sensor readings is not uniform over the range of possible reading values. Our K-D tree based Data-Centric Storage (KDDCS) scheme maintains the invariant that the storage of events is distributed reasonably uniformly among the sensors. KDDCS is composed of a set of distributed algorithms whose running time is within a poly-log factor of the diameter of the network. The number of messages any sensor has to send, as well as the bits in those messages, is poly-logarithmic in the number of sensors. Load balancing in KDDCS is based on defining and distributively solving a theoretical problem that we call the Weighted Split Median problem. In addition to analytical bounds on KDDCS individual algorithms, we provide experimental evidence of our scheme's general efficiency, as well as its ability to avoid the formation of storage hot-spots of various sizes, unlike all previous INDCS schemes.

A major problem in mobile web applications as well as the wireless Internet is the scalable delivery of data. The most popular solution for this problem is a hybrid system that uses broadcast push to scalably deliver the most popular data, and reserves broadcast pull for delivery of less popular data. Such a hybrid scheme introduces a variety of data management problems at the broadcast server. In this paper, we examine three of these problems: the push popularity problem, the document classification problem, and the bandwidth division problem. The push popularity problem is to estimate the popularity of the documents in the web site. The document classification problem is to determine which documents should be pushed and which documents must be pulled. The bandwidth division problem is to determine how much of the server bandwidth to devote to pushed documents and how much of the server bandwidth should be reserved for pulled documents. We propose simple and elegant solutions for these problems. We report on experiments with our system that validate our algorithms.

Sensor Networks have brought closer than ever before the network and database research communities. A novel sensor data management paradigm appeared with the development of data centric routing protocols viewing the network as a huge distributed database. However, this paradigm is typically supported through a query processing layer that treats the wireless network as a black box and underestimates its fundamental limitations. In this seminar we elaborate on these limitations and utilize them in favor of efficient data management in wireless sensor environments.

Data access prediction has been proposed as a mechanism to overcome latency lag, and more recently as a means of conserving energy in mobile systems. We present a fully adaptive predictor, that can optimize itself for any arbitrary workload, while simultaneously offering simple adjustment of goals between energy conservation and latency reduction. Our algorithm. STEP, achieves power savings on mobile computers by eliminating more data fetches, which would otherwise have caused excess energy to be consumed in accessing local storage devices or using the wireless interface to fetch remote data. We have demonstrated our algorithm to perform as well as some of the best access predictors, while incurring almost none of the associated increase in I/O workloads typical of their use. Our algorithm reduced average response times by approximately 50% compared to an LRU cache, while requiring less than half the I/O operations that traditional predictors would require to achieve the same performance, thereby incurring no energy penalty.

Broadcasting provides an efficient means for disseminating information in both wired and wireless settings, especially for popular data items. Multiversion (MV) data broadcast, i.e., data broadcast in which more than one value is broadcast per data item, has the advantage of allowing more client transactions to read consistent data and complete their operation successfully. Naturally, the MV broadcast can satisfy both historical queries in which a client accesses many versions of the same data item and snapshot queries in which a client accesses different data items of the same version. Furthermore, multiple versions increase clients' tolerance to network disconnections that are common in wireless communications. In this paper, we expand our previous work on MV broadcasts to support efficient selective tuning. Selective tuning is important for energy constraint mobile devices since it enables the client to be active only when data of interest appear on the broadcast. The rest of the time the client stays in doze mode with its antenna powered down. In its simplest form, we adopt (1,1)-Indexing and organize multiversion data in buckets, so that the average energy consumption is significantly reduced while minimally affecting the average access time.

A major problem in web database applications and on the Internet in general is the scalable delivery of data. One proposed solution for this problem is a hybrid system that uses multicast push to scalably deliver the most popular data, and reserves traditional unicast pull for delivery of less popular data. However, such a hybrid scheme introduces a variety of data management problems at the server. In this paper we examine three of these problems: the push popularity problem, the document classification problem, and the bandwidth division problem. The push popularity problem is to estimate the popularity of the documents in the web site. The document classification problem is to determine which documents should be pushed and which documents must be pulled. The band-width division problem is to determine how much of the server bandwidth to devote to pushed documents and how much of the server bandwidth should be reserved for pulled documents. We propose simple and elegant solutions for these problems. We report on experiments with our system that validate our algorithms.

Together with wireless communication technologies, portable computers and hand-held devices provide a pervasive base for mobile computing. Mobile computing involves mobility of users, hardware, software and data. In addition to advances in communications and hardware, mobile and wireless access requires innovative theories and paradigms in data management and new data engineering techniques in order to cope with the inherent limitations of the mobile environment while satisfying the users’ new expectations and needs. This seminar aims at covering such data engineering aspects along two dimensions: (a) the wireless network perspective, and (b) the information processing perspective. Thus, this seminar provides a good overview of current methods and practices in building mobile information systems, examine mobile and wireless infrastructures and discuss challenging research problems in all aspects of mobile information processing.

A major problem on the Internet is the scalable dissemination of information. This problem is particularly acute exactly at the time when the scalability of data delivery is most important. One proposed solution to this scalability problem is to use multicast communication. However, allowing multicast communication introduces many nontrivial data management problems, such as caching, consistency, and scheduling. We have built a middleware that unifies and extends state-of-the-art data management methods and algorithms into one software distribution. Its flexible and extensible architecture is built from individual components that can be selected or replaced depending on the underlying multicast transport mechanism or on the application needs. Particular care has gone into the design of the algorithms to optimize the user-perceived level of service. We demonstrate our middleware within the context of the RODS application.

With the rapid growth in mobile and wireless technologies and the availability, pervasiveness and cost effectiveness of wireless networks, mobile computers are quickly becoming the normal front-end devices for accessing enterprise data. In this paper, we are addressing the issue of efficient delivery of business decision support data in the form of summary tables to mobile clients equipped with OLAP front-end tools. Towards this, we propose a new on-demand scheduling algorithm, called SBS, that exploits both the derivation semantics among OLAP summary tables and the mobile clients' capabilities of executing simple SQL queries. It maximizes the aggregated data sharing between clients and reduces the broadcast length compared to the already existing techniques. The degree of aggregation can be tuned to control the tradeoff between access time and energy consumption. Further, the proposed scheme adapts well to different request rates, access patterns and data distributions. The algorithm effectiveness with respect to access time and power consumption is evaluated using simulation.

As mobile devices get ubiquitous and grow in computational power, their management of interdependent data also becomes increasingly important. The mobile environment exhibits all the characteristics of a distributed database plus the feature of whimsical connectivity. Consequently, transactions respecting data consistency can suffer unbounded and unpredictable delays at both mobile and stationary nodes. The currently popular multi-tier model, in which mobile devices are in one end and always-connected stationary servers in the other, has certain practical advantages. However, it assumes that all integrity constraints are evaluated at the servers and hence relies on the semantics of operations for any autonomy enhancement of the mobile devices. In this paper, we examine the idea of constraint localization in cases where two mobile nodes each own data that share a constraint. It relies on reformulation of a constraint into more flexible local constraints that give more autonomy to the mobile nodes. The scheme also involves dynamic changes of these local constraints through negotiation, which we call re-localization. To overcome the problem of simultaneous requests for such re-localization, we give algorithms along with experimental results indicating their effectiveness.

Given the undeniable popularity of the Web, providing efficient and secure access to remote databases using a Web browser is crucial for the emerging cooperative information systems and applications. In this paper, we evaluate all currently available Java-based approaches that support persistent connections between Web clients and database servers. These approaches include Java applets, Java Sockets, Servlets, Remote Method Invocation, CORBA, and mobile agents technology. Our comparison is along the dimensions of performance and programmability. Our findings point out that best performance is not always achievable with high programmability and low resource requirements. Moreover, the mobile agent technology needs to improve its programmability while giving particular emphasis on its infrastructure.

Summary form only given, as follows. We are in the midst of a wireless and mobile revolution. In the near future, a typical computing environment - business, personal, scientific or educational - will provide wireless network connectivity between powerful data servers and mobile, sometimes disconnected, computers and devices. This has created exciting opportunities for developing a wide range of innovative database applications and systems. However, an open question remains: What kind of system will be capable of offering scalable data services and exhibit scalable performance? Besides advances in communications and hardware, does achieving pervasive mobile computing require innovative theories and paradigms in data management or new data engineering techniques? The objective of this tutorial is to provide an answer to the above questions by presenting the current state-of-the-research and contrasting it with the state-of-the-practice. Towards this, it will provide an overview of the commercial-state-of-the-art for supporting mobile database access and present a summary of the significant research advances in theories and techniques for mobile and wireless data access. It will also discuss some future directions in the context of pervasive and invisible computing applications.

We identify one of the incompatibility problems associated with atomic commit :protocols that prevents them from being used together and wei derive a correctness criterion that captures the correctness of their integration.We also present a new atomic commit Iprotocol, called Presumed Any, that integrates the three commonly known two-phase commit protocols and prove its correctness.

The advent of high-speed networks will enable the deployment of data-server systems (currently used in LANs) over WANs. The users of these systems will have the same high expectations with respect to performance parameters (such as the transaction throughput, response time and system reliability) as in the case of LANs. Thus, it is important to study the performance of existing distributed database protocols in the new networking environment, identify the performance bottlenecks and develop protocols that are capable of taking advantage of the high-speed networking technology. As a first step, in this paper, we examine the scalability of the server-based two-phase locking (s-2PL) protocol, and discuss three optimizations which allow the s-2PL protocol to be tailored for high-speed WAN environments where the size of the message is less of a concern than the number of rounds of message passing. These optimizations, collectively called the group two-phase locking (g-2PL) protocol, reduce the number of rounds of message passing by grouping lock grants, client-end caching and data migration. In a simulation study, 20-25% improvement in the response time of the g-2PL protocol over that of the s-2PL protocol was observed.

The authors argue in favor of the presumed commit protocol by proposing two new presumed commit variants that significantly reduce the cost of logging activities associated with the original presumed commit protocol. Furthermore, for read-only transactions, they apply their unsolicited update-vote optimization and show that the cost associated with this type of transactions is the same in both presumed commit and presumed abort protocols, thus, nullifying the basis for the argument that favors the presumed abort protocol. This is especially important for modern distributed environments which are characterized by high reliability and high probability of transactions being committed rather than aborted.

QBI is an icon-based query processing and exploration facility for large distributed databases [3]. As opposed to other interactive query interfaces, it combines (1) a pure iconic specification, i.e., no diagrams of any form, only icon manipulation, with (2) intensional browsing or metaquery tools that assist in the formulation of complete queries without involving path specification or access to the actual data in the database.Path expressions are automatically generated by QBI and irrespective of their length, represented by a single icon, allowing for better use of the screen. It requires no special knowledge of the content of the underlying database nor understanding of the details of the database schema. Hence, QBI is domain independent and equally useful to both unsophisticated and expert users.

ACTA is a comprehensive transaction framework that facilitates the formal description of properties of extended transaction models. Specifically, using ACTA, one can specify and reason about (1) the effects of transactions on objects and (2) the interactions between transactions. This article presents ACTA as a tool for the synthesis of extended transaction models , one which supports the development and analysis of new extended transaction models in a systematic manner. Here, this is demonstrated by deriving new transaction definitions (1) by modifying the specifications of existing transaction models, (2) by combining the specifications of existing models, and (3) by starting from first principles. To exemplify the first, new models are synthesized from atomic transactions and join transactions . To illustrate the second, we synthesize a model that combines aspect of the nested - and split-transaction models. We demonstrate the latter by deriving the specification of an open-nested-transaction model from high-level requirements.

article Extracting concurrency from objects: a methodology Share on Authors: Panos K. Chrysanthis Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile , S. Raghuram Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile , Krithi Ramamritham Department of Computer and Information Science, University of Massachusetts, Amherst, MA Department of Computer and Information Science, University of Massachusetts, Amherst, MAView Profile Authors Info & Claims ACM SIGMOD RecordVolume 20Issue 2June 1991 pp 108–117https://doi.org/10.1145/119995.115803Online:01 April 1991Publication History 28citation326DownloadsMetricsTotal Citations28Total Downloads326Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Recently, a number of extensions to the traditional transaction model have been proposed to support new information-intensive applications such as CAD/CAM and software development. However, these extended models capture only a subset of interactions that can be found in such applications, and represent only some of the points within the spectrum of interactions possible in competitive and cooperative environments.

The database cache transaction recovery technique as proposed in [Elhard and Bayer 84] offers significant performance advantages for reliable database systems. However, the smallest granularity of locks it provides is the page. Here we present two schemes supporting smaller granularity. The first scheme allows maximal concurrency consistent with physical two-phase locking, with the same per-transaction I/O cost as original database cache scheme. The second scheme offers the same concurrency as the first, but features reduced I/O on commit, at the cost of some increase recovery time.