Wind turbines are equipped with high-quality sensors that generate vast volumes of high-frequency time series. The time series are ingested on the edge and transferred to the cloud for later analytics. This process is complicated by challenges like low network bandwidth and high cloud storage costs. ModelarDB was proposed as a solution to efficiently manage time series across the entire pipeline by using so-called models for lossless or error-bounded lossy compression of time series. However, ModelarDB’s compression can be further improved through: 1) avoiding models that only represent few values by storing residuals (i.e., values that models fail to compress) explicitly with them; 2) exploiting error bounds even more through preprocessing; and 3) timestamp compression specialized for regular and irregular time series. We propose the multi-model compression method Fauna which uses 1) the novel model fitting method Platypus; 2) PMC and Swing for compressing values and; 3) the novel Macaque for compressing residuals and timestamps. Platypus is a model fitting method that uses different models for specialized compression of values and residuals. We then evaluate state-of-the-art lossless compression methods for 32-bit floats and propose preprocessing methods to add support for error-bounded compression. We present Macaque that includes MacaqueV and MacaqueTS. MacaqueV modifies Facebook Gorilla’s lossless compression method for 32-bit floats (GorillaV) and combines it with our novel preprocessing methods to now also enable error-bounded lossy compression. MacaqueTS is a lossless compression method for timestamps. Using only Platypus reduces ModelarDB’s storage use by up to 1.8x and significantly simplifies using the system. While also up to 7x better for lossless compression, ModelarDB with Fauna uses up to 2.5x less storage than ModelarDB and up to 14.5x, 7.2x, 17.5x and 14.2x less storage than ClickHouse, Apache IoTDB, Apache Parquet and TimescaleDB, respectively, with a realistic 1% error bound.

Spatio-temporal data proliferates in numerous real-world domains, such as transportation, weather, and energy. Spatio-temporal deep learning models aims to utilize useful patterns in such data to support tasks like prediction, imputation, and anomaly detection. However, previousone-to-onedeep learning models designed for specific tasks typically require separate training for each use case, leading to increased computational and storage costs. To address this issue,one-to-manyspatio-temporal foundation models have emerged, offering a unified framework capable of solving multiple spatio-temporal tasks. These foundation models achieve remarkable success by learning general knowledge with spatio-temporal data or transferring the general capabilities of pre-trained language models. While previous surveys have explored spatio-temporal data and methodologies separately, they have ignored a comprehensive examination of how foundation models are designed, selected, pre-trained, and adapted. As a result, the overall pipeline for spatio-temporal foundation models remains unclear. To bridge this gap, we innovatively provide an up-to-date review of previous spatio-temporal foundation models from the pipeline perspective. The pipeline begins with an introduction to different types of spatio-temporal data, followed by details of data preprocessing and embedding techniques. The pipeline then presents a novel data property taxonomy to divide existing methods according to data sources and dependencies, providing efficient and effective model design and selection for researchers. On this basis, we further illustrate the training objectives of primitive models, as well as the adaptation techniques of transferred models. Overall, our survey provides a clear and structured pipeline to understand the connection between core elements of spatio-temporal foundation models while guiding researchers to get started quickly. Additionally, we introduce emerging opportunities such as multi-objective training in the field of spatio-temporal foundation models, providing valuable insights for researchers and practitioners.

Modern analytics rely on insights derived from the execution of inference queries over vast amounts of unstructured data such as text, images, and video. Oftentimes, these queries evaluate predicates based on an expensive “oracle“ model in the likes of a deep neural network or human input that dominates the total query cost. Prior work has focused on training computationally cheap proxy models at query time that produce an approximate result. Alternatively, index-based methods apply the original oracle over a representative set of data points and generate the approximate result through an inference propagation process. Current state-of-the-art (SOTA) index-based methods require a memory -expensive index construction process which offsets their oracle cost-effectiveness and can make their usage prohibitive. In this work, we present HAIDES, an index-based, domain-agnostic framework for approximating inference on unstructured data. HAIDES consists of two main components: a coarse-to-fine framework that can be efficiently constructed using minimal memory, and a novel index adaptation component that makes use of oracle invocations during query execution in order to adaptively produce representative sets that yield high-quality approximate results. Our experimental results across three challenging domains-video, images, text-show that HAIDES (a) constructs indexes that produce performant representative sets with up to 2 orders of magnitude less memory than the SOTA baseline, while (b) requires up to 2x less oracle calls to produce the same result quality, and (c) achieves up to 10 percentage points better result quality when using the same oracle calls.

Prescriptive Analytics (PSA), an emerging business analytics field suggesting concrete options for solving business problems , has seen an increasing amount of interest after more than a decade of multidisciplinary research . This paper is a comprehensive survey of existing applications within PSA in terms of their use cases, methodologies, and possible future research directions. To ensure a manageable scope, we focus on PSA applications that develop data-driven, automatic workflows, i.e., Data-Driven PSA (DPSA) . Following a systematic methodology , we identify and include 104 papers in our survey. As our key contributions, we derive a number of novel taxonomies of the field and use them to analyse the field’s temporal development. In terms of use cases, we derive 10 application domains for DPSA, from Healthcare to Manufacturing, and subsumed problem types within each. In terms of individual method usage, we derive 5 method types and map them to a comprehensive taxonomy of method usage within DPSA applications, covering mathematical optimization , data mining and machine learning , probabilistic modelling , domain expertise , as well as simulations . As for combined method usage, we provide a statistical overview of how different method usage combinations are distributed and derive 2 generic workflow patterns along with subsumed workflow patterns, combining methods by either sequential or simultaneous relationships. Finally, we derive 5 possible research directions based on frequently recurring issues among surveyed papers, suggesting new frontiers in terms of methods, tools, and use cases.

Renewable Energy Sources (RESs) are monitored by many high-quality sensors that produce vast amounts of high-frequency time series data. This can be used to increase the renewable energy production and longevity of the RESs, e.g., yaw misalignment detection and predictive maintenance for wind turbines. It is currently not possible for wind turbine manufacturers and owners to use this data due to limits on bandwidth and storage that are infeasible to increase. Thus, they store simple aggregates which remove valuable outliers and fluctuations. As a remedy, we demonstrate the new model-based Time Series Management System (TSMS) ModelarDB. The participants can experience how ModelarDB ingests time series on the edge and compresses them as segments with metadata and so-called models. The models represent values within a user-defined absolute or relative error bound (even 0 or 0%). Participants can adjust many parameters and see how the segments are transferred to the cloud using much less bandwidth and storage than other popular solutions like Apache Parquet and Apache TsFile, e.g., up to 90%–99% less than Apache Parquet. Participants can analyze the time series on the edge, in the cloud, and on the client using SQL or Python. On the client, ModelarDB runs in-process to integrate with, e.g., Python. Thus, participants can see how ModelarDB efficiently manages high-frequency time series across edge, cloud, and client.

Big time series are increasingly available from an ever wider range of IoT-enabled sensors deployed in various environments. Significant insights can be gained by mining temporal patterns from these time series. Temporal pattern mining (TPM) extends traditional pattern mining by adding event time intervals into extracted patterns, making them more expressive at the expense of increased time and space complexities. Besides frequent temporal patterns (FTPs), which occur frequently in the entire dataset, another useful type of temporal patterns are so-calledrare temporal patterns (RTPs), which appear rarely but with high confidence. Mining rare temporal patterns yields additional challenges. For FTP mining, the temporal information and complex relations between events already create an exponential search space. For RTP mining, the support measure is set very low, leading to a further combinatorial explosion and potentially producing too many uninteresting patterns. Thus, there is a need for a better approach to mine frequent and rare temporal patterns. This paper presents ourGeneralized Temporal Pattern Mining from Time Series (GTPMfTS)approach that can mine both types of patterns, with the following specific contributions: (1) The end-to-end GTPMfTS process taking time series as input and producing frequent/rare temporal patterns as output. (2) The efficientGeneralized Temporal Pattern Mining (GTPM)algorithm mines frequent and rare temporal patterns using efficient data structures for fast retrieval of events and patterns during the mining process, and employs effective pruning techniques for significantly faster mining. (3) An approximate version of GTPM that uses mutual information, a measure of data correlation, to prune unpromising time series from the search space. (4) An extensive experimental evaluation of GTPM for rare temporal pattern mining (RTPM) and frequent temporal pattern mining (FTPM), showing that RTPM and FTPM significantly outperform the baselines on runtime and memory consumption, and can scale to big datasets. The approximate RTPM is up to one order of magnitude, and the approximate FTPM is up to two orders of magnitude, faster than the baselines, while retaining high accuracy.

Time series data is widely used for decision-making and advanced analytics such as forecasting. However, the vast data volumes make storage challenging. Using lossy compression can save more space compared to lossless methods, but it can affect the forecasting accuracy. Understanding the impact of lossy compression on forecasting accuracy is a multifaceted challenge, necessitating experimental evaluation across various forecasting models, compression methods, and time series. This paper conducts such experimental evaluation by combining seven forecasting models, three lossy compression algorithms, and six datasets. By simulating a real-life scenario where forecasting models use lossy compressed data for prediction, we address three main research questions related to compression error and its effects on the time series characteristics and the forecasting models. The results show that the Poor Man’s Compression and Swing Filter lossy compression algorithms add less error than the Squeeze method as the error bound increases. Poor Man’s Compression provides the best balance between compression ratio and forecasting accuracy. Specifically, we obtained an average compression ratio of 13.65, 5.56, and 14.97 for PMC, SWING, and SZ with an average impact on forecasting accuracy of 5.56%, 3.3%, and 8.5%, respectively. An analysis of several time series characteristics shows that the maximum Kullback-Leibler divergence between consecutive windows in the time series is the best indicator of the impact of lossy compression on forecasting accuracy. Finally, our results indicate that simple models like Arima, are more resilient to lossy compression than complex deep learning models. The source code and data are available at https://github.com/cmcuza/EvalImpLSTS.

Modern wind turbines are equipped with wired high-quality sensors that produce high-frequency sensor data in the form of time series as shown in Figure 1 a. From working with multiple different practitioners, we have learned that relatively few but very long high-quality time series are produced. The time series are either univariate, i.e., have one value per timestamp, or multivariate, i.e., have multiple values per timestamp. Further, they are either regular, i.e., have a fixed time interval between consecutive data points, or irregular. Despite these differences, the volume and velocity of the time series that are being produced are generally major challenges. For example, if the sensors are sampled at 100Hz, a single park of 100 wind turbines generates more than 11 PiB of data each year [1]. The sensor data is collected by weak edge devices and then transferred to powerful cloud servers over a relatively slow connection as shown in Figure 2. However, it is infeasible to transfer and store the raw time series due to their volume and velocity. Renewable energy system installations use low-end commodity PCs on the edge, e.g., 4 CPU cores, 4 GiB RAM, and an HDD [1]. In addition, the bandwidth between the edge and the cloud can be as low as 0.5-5 Mbit/s [1]. Thus, practitioners use simple aggregates, e.g., 10-minute averages, which remove valuable outliers and fluctuations as shown in Figure 1b. To remedy this, practitioners want to use lossy compression with a per-value error bound (E) to collect more high-frequency time series and thus improve their analytics.

Modern wind turbines are monitored by sensors that generate massive amounts of high frequency time series that are ingested on the edge and then transferred to the cloud where they are stored and analyzed. This results in at least four challenges: (1) Limited hardware makes efficient ingestion necessary to keep up; (2) Limited bandwidth makes data compression necessary; (3) High storage costs as all data must be stored; and (4) Low data quality due to lossy compression methods without error bounds. Practitioners currently use solutions that only solve some of these. In this paper, we evaluate the Time Series Management System ModelarDB, a solution that meets all four challenges by efficiently managing time series across the entire pipeline. We compare it to three commonly used alternatives and evaluate different aspects of them in a realistic edge-to-cloud scenario with real-life datasets. For lossless compression, ModelarDB achieves up to 2x better compression and 1.2x better transfer efficiency. For lossy compression, ModelarDB achieves up to 4.6x better compression and 10x better transfer efficiency, or similar compression with orders of magnitude less error.

Abstract With the widespread use of networked and geo-positioned mobile devices, e.g., smartphones, Spatial Crowdsourcing (SC), which refers to the assignment of location-based tasks to moving workers, is drawing increasing attention. One of the critical issues in SC is task assignment that allocates tasks to appropriate workers. We propose and study a novel SC problem, namely Coalition-based Task Assignment (CTA), where the spatial tasks (e.g., home improvement and furniture installation) may require more than one worker (forming a coalition) to cooperate to maximize the overall rewards of workers. We design a greedy and an equilibrium-based CTA approach. The greedy approach forms a set of worker coalitions greedily for performing tasks and uses an acceptance probability to identify high-value task assignments. In the equilibrium-based approach, workers form coalitions in sequence and update their strategies (i.e., selecting a best-response task), to maximize their own utility (i.e., the reward of the coalition they belong to) until a Nash equilibrium is reached. Since the equilibrium obtained is not unique and optimal in terms of total rewards, we further propose a simulated annealing scheme to find a better Nash equilibrium. To achieve fair task assignments, we optimize the framework to distribute rewards fairly among workers in a coalition based on their marginal contributions and give workers who arrive first at the SC platform highest priority. Extensive experiments demonstrate the efficiency and effectiveness of the proposed methods on real and synthetic data.

Due to their expressive power, Knowledge Graphs (KGs) have received increasing interest not only as means to structure and integrate heterogeneous information but also as a native storage format for large amounts of knowledge and statistical data. Therefore, analytical queries over KG data, typically stored as RDF, have become increasingly important. Yet, formulating such queries represents a difficult task for users that are not familiar with the query language (typically SPARQL) and the structure of the dataset at hand. To overcome this limitation, we propose Re2xOLAP: The first comprehensive interactive approach that allows to reverse-engineer and refine RDF exploratory OLAP queries over KGs containing statistical data. Thus, Re2xOLAP enables to perform KG exploratory analytics without requiring the user to write any query at all.We achieve this goal by first reverseengineering analytical SPARQL queries from a small set of userprovided examples and then, given the reverse-engineered query, we propose intuitive and explainable exploratory query refinements to iteratively help the user obtain the desired information. Our experiments on real-world large-scale KGs show that Re2xOLAP can efficiently reverse-engineer analytical SPARQL queries solely based on a small set of input examples. Additionally, we demonstrate the expressive power of our interactive refinement methods by showing that Re2xOLAP allows users to navigate hundreds of thousands of different exploration paths with just a few interactions.

As IoT-enabled sensors become more pervasive, very large time series data are increasingly generated and made available for advanced data analytics. By mining temporal patterns from the available data, valuable insights can be extracted to support decision making. A useful type of patterns found in many real-world applications exhibits periodic occurrences, and is thus called seasonal temporal patterns (STP). Compared to regular patterns, mining seasonal temporal patterns is more challenging since traditional measures such as support and confidence do not capture the seasonality characteristics. Further, the anti-monotonicity property does not hold for STPs, and thus, resulting in an exponential search space. We propose a first solution for seasonal temporal pattern mining (STPM) from time series that can mine STP at different data granularities. We design efficient data structures and use two pruning techniques for the STPM algorithm that downsize the search space and accelerate the mining process. Further, based on the mutual information measure, we propose an approximate version of STPM that only mine seasonal patterns on the promising time series. Finally, extensive experiments with real-world and synthetic datasets show that STPM outperforms the baseline in terms of runtime and memory usage, and can scale to large datasets. The approximate STPM is up to an order of magnitude faster and less memory-consuming than the baseline, while maintaining high accuracy.

In Spatial crowdsourcing, mobile users perform spatio-temporal tasks that involve travel to specified locations. Spatial crowdsourcing (SC) is enabled by SC platforms that support mobile worker recruitment and retention, as well as task assignment, which is essential to maximize profits that are accrued from serving task requests. Specifically, how to best achieve task assignment in a cost-effective manner while contending with spatio-temporal constraints is a key challenge in SC. To address this challenge, we formalize and study a novel Profit-driven Task Assignment problem. We first establish a task reward pricing model that takes into account the temporal constraints (i.e., expected completion time and deadline) of tasks. Then we adopt an optimal algorithm based on tree decomposition to achieve an optimal task assignment and propose greedy algorithms based on Random Tuning Optimization to improve the computational efficiency. To balance effectiveness and efficiency, we also provide a heuristic task assignment algorithm based on Ant Colony Optimization that assigns tasks by simulating behavior of ant colonies foraging for food. Finally, we conduct extensive experiments using real and synthetic data, offering detailed insight into effectiveness and efficiency of the proposed methods.

With the lowering costs of sensors, high-volume and high-velocity data are increasingly being generated and analyzed, especially in IoT domains like energy and smart homes. Consequently, applications that require accurate short-term forecasts and predictions are also steadily increasing. In this paper, we provide an overview of a novel end-to-end platform that provides efficient ingestion, compression, transfer, query processing, and machine learning-based analytics for high-frequency and high-volume time series from IoT. The performance of the platform is evaluated using real-world dataset from RES installations. The results show the importance of high-frequency analytics and the surprisingly positive impact of error bounded lossy compression on machine learning in the form of AutoML. For example, when detecting yaw misalignments in wind turbines, an improvement of 9% in accuracy was observed for AutoML models on lossy compressed data compared to the current industry standard of 10-minute aggregated data. Thus, these small-scale experiments show the potential of the platform, and larger pilots are planned.

The rapid increase of traffic data generated by different sensing systems opens many opportunities to improve transportation services. An important opportunity is to enable stochastic routing that computes the arrival time probabilities for each suggested route instead of only the expected travel time. However, traffic datasets typically have many missing values, which prevents the construction of stochastic speeds. To address this limitation, we propose the Stochastic Spatio-Temporal Graph Convolutional Network (SST-GCN) architecture that accurately imputes missing speed distributions in a road network. SST-GCN combines Temporal Convolutional Networks and Graph Convolutional Networks into a single framework to capture both spatial and temporal correlations between road segments and time intervals. Moreover, to cope with datasets with many missing values, we propose a novel self-adaptive context-aware diffusion process that regulates the propagated information around the network, avoiding the spread of false information. We extensively evaluate the effectiveness of SST-GCN on real-world datasets, showing that it achieves from 4.6% to 50% higher accuracy than state-of-the-art baselines using three different evaluation metrics. Furthermore, multiple ablation studies confirm our design choices and scalability to large road networks.

The widespread deployment of smartphones, net-worked in-vehicle devices with geo-positioning capabilities, and vessel tracking technologies renders it feasible to collect the evolving geo-locations of populations of land- and sea-based moving objects. The continuous clustering of such data can enable a variety of real-time services, such as road traffic management and vessel collision risk assessment. However, little attention has so far been given to the quality of moving-object clusters-for example, it is beneficial to smooth short-term fluctuations in clusters to achieve robustness to exceptional data and to improve existing applications. We propose the notion of evolutionary clustering of moving objects, abbreviated ECM, that enhances the quality of moving object clustering by means of temporal smoothing that prevents abrupt changes in clusters across successive timestamps. Employing the notions of snapshot and historical costs, we formalize ECM and formulate ECM as an optimization problem. We prove that ECM can be performed approximately in linear time, thus eliminating iterative processes employed in previous studies. Further, we propose a minimal-group structure and a seed-point shifting strategy to facilitate temporal smoothing. Finally, we present all algorithms underlying ECM along with a set of optimization techniques. Extensive experiments with three real-life datasets offer insights into ECM and show that it outperforms state-of-the-art solutions in terms of both clustering quality and clustering efficiency.

The prevalence of mobile devices and positioning techniques has enabled so-called traffic-aware urban computing. In urban daily life, people's activities consist of indoor and outdoor parts whose transitions have important impacts on traffic behavior. For example, outdoor traffic events (e.g., jams) can be triggered by indoor events (e.g., the ending of exhibitions, tour-naments, or working hours). In turn, indoor events (e.g., subway jams) can also be affected by outdoor events (e.g., snowy weather or other bad outdoor traffic conditions). For a wide range of applications like traffic monitoring and emergency response, it is thus interesting to develop techniques for analyzing data in an integrated indoor and outdoor space. Since real datasets of this kind are still scarce and small, a suitable data generator is needed for both functional and scalability testing. In this work, we present UrbanGen, which follows the constraints of road networks for the outdoor space and the constraints of topologies for the indoor space. The system provides the functionalities including: 1) integrating a model of indoor topologies with the state-of-art road networks; 2) parameterizing the movement of objects in the integrated model; 3) serializing and visualizing the generated trajectories.

In applications of Web of Things or Web of Events, a massive volume of multi-dimensional streaming data are automatically and continuously generated from different sources, such as GPS, sensors, and other measurement devices, which are essentially imprecise (inaccurate and/or uncertain). It is challenging to monitor and get insights over imprecise and low-level streaming data, in order to capture potentially important data changing trends and to initiate prompt responses. In this work, we investigate solutions for conducting multi-dimensional and multi-granularity probabilistic regression for the imprecise streaming data. The probabilistic nature of streaming data poses big computational challenges to the regression and its aggregation. In this paper, we study a series of techniques on multi-dimensional probabilistic regression, including aggregation, sketching, popular path materialization, and exception-driven querying. Extensive experiments on real and synthetic datasets show the efficiency and scalability of our proposals.

Large amounts of spatial, textual, and temporal (STT) data are being produced daily. This is data containing an unstructured component (text), a spatial component (geographic position), and a time component (timestamp). Therefore, there is a need for a powerful and general way of analyzing STT data together. In this paper, we define and formalize the Spatio-Textual-Temporal Cube (STTCube) structure to enable combined effective and efficient analytical queries over STT data. Our novel data model over STT objects enables novel joint and integrated STT insights that are hard to obtain using existing methods. Furthermore, our proposed STTCube Incremental Maintenance (IMstt) method maintains the already constructed STTCube efficiently when new data arrives. Moreover, we introduce the new concept of STT measures with associated novel STT-OLAP operators. To allow for efficient large-scale analytics, we present a pre-aggregation framework for exact and approximate computation of STT measures. Our comprehensive experimental evaluation on a real-world Twitter dataset confirms that our proposed methods reduce query response time by 1–5 orders of magnitude compared to the No Materialization baseline and decrease storage cost between 97% and 99.9% compared to the Full Materialization baseline while adding only a negligible overhead in the STTCube construction time. Moreover, approximate computation achieves an accuracy between 90% and 100% while reducing query response time by 3–5 orders of magnitude compared to No Materialization and IMstt achieves an order of magnitude improvement in maintenance time compared to the baseline maintenance method.

Besides the traditional cartographic data sources, spatial information can also be derived from location-based sources. However, even though different location-based sources refer to the same physical world, each one has only partial coverage of the spatial entities, describe them with different attributes, and sometimes provide contradicting information. Hence, we introduce the spatial entity linkage problem, which finds which pairs of spatial entities belong to the same physical spatial entity. Our proposed solution (QuadSky) starts with a time-efficient spatial blocking technique (QuadFlex), compares pairwise the spatial entities in the same block, ranks the pairs using Pareto optimality with theSkyRankalgorithm, and finally, classifies the pairs with our novelSkyEx-*family of algorithms that yield 0.85precisionand 0.85recallfor a manually labeled dataset of 1,500 pairs and 0.87precisionand 0.6recallfor a semi-manually labeled dataset of 777,452 pairs. Moreover, we provide a theoretical guarantee and formalize theSkyEx-FESalgorithm that explores only 27 percent of the skylines without any loss inF-measure. Furthermore, our fully unsupervised algorithmSkyEx-Dapproximates the optimal result with anF-measureloss of just 0.01. Finally,QuadSkyprovides the best trade-off betweenprecisionandrecall, and the bestF-measurecompared to the existing baselines and clustering techniques, and approximates the results of supervised learning solutions.

Abstract RDF triplestores’ ability to store and query knowledge bases augmented with semantic annotations has attracted the attention of both research and industry. A multitude of systems offer varying data representation and indexing schemes. However, as recently shown for designing data structures, many design choices are biased by outdated considerations and may not result in the most efficient data representation for a given query workload. To overcome this limitation, we identify a novel three-dimensional design space. Within this design space, we map the trade-offs between different RDF data representations employed as part of an RDF triplestore and identify unexplored solutions. We complement the review with an empirical evaluation of ten standard SPARQL benchmarks to examine the prevalence of these access patterns in synthetic and real query workloads. We find some access patterns, to be both prevalent in the workloads and under-supported by existing triplestores. This shows the capabilities of our model to be used by RDF store designers to reason about different design choices and allow a (possibly artificially intelligent) designer to evaluate the fit between a given system design and a query workload.

The widespread deployment of IoT systems in the real world today has enabled the generation and collection of an enormous amount of sensor times series. One of the important mining techniques to extract patterns from time series is temporal pattern mining (TPM). Unlike the sequential pattern mining, TPM adds an additional temporal dimension, i.e., time intervals, into extracted patterns, making them more informative. However, adding the extra temporal dimension into patterns results in an additional exponential factor to the growth of the search space, and thus, significantly increases the mining complexity. Current TPM approaches work sequentially, therefore, cannot scale to large datasets. In this paper, we propose Distributed Hierarchical Pattern Graph TPM (DHPG-TPM), the first distributed solution that supports large-scale TPM using the leading distributed platform Apache Spark. Moreover, DHPG-TPM employs efficient data structures, distributed bitmap and distributed Hierarchical Pattern Graph that are carefully designed to work efficiently in a distributed environment to enable fast computations of support and confidence. To address the exponential search space of TPM, we design effective distributed pruning techniques based on the Apriori principle and the transitivity property of temporal relations to reduce the search space while minimizing the communication overhead between the cluster nodes. We conduct extensive experiments on real-world and synthetic datasets, showing that DHPG-TPM outperforms the sequential baselines and scales to very large datasets.

Today, advanced data analysts make use of both predictive models and optimization problem solving to build data-driven decision making applications, a combination of technologies recently termed Prescriptive Analytics (PA). Current PA applications typically have multiple layers of poorly integrated components: a relational DBMS for data storage/management, ML tools for prediction, and specialized software packages for problem modeling and optimization problem solving. This complex stack leads to inefficient, labor-intensive, and error-prone PA workflows, blocking wider adoption of PA. In this paper, we present SolveDB+ -an RDBMS for PA applications which supports all PA steps with modeling, predictive, and optimization functionalities, and integrates these in a common SQL-based framework. Major SolveDB+ novelties are 1) a powerful SQL-based approach for PA problem specification and solving, 2) an extensible in-DBMS infrastructure for prediction and optimization solvers, and 3) in-DBMS modeling and management of PA models. SolveDB+ significantly improves both PA developer productivity and performance.

To monitor critical infrastructure, high quality sensors sampled at a high frequency are increasingly used. However, as they produce huge amounts of data, only simple aggregates are stored. This removes outliers and fluctuations that could indicate problems. As a remedy, we present a model-based approach for managing time series with dimensions that exploits correlation in and among time series. Specifically, we propose compressing groups of correlated time series using an extensible set of model types within a user-defined error bound (possibly zero). We name this new category of model-based compression methods for time series Multi-Model Group Compression (MMGC). We present the first MMGC method GOLEMM and extend model types to compress time series groups. We propose primitives for users to effectively define groups for differently sized data sets, and based on these, an automated grouping method using only the time series dimensions. We propose algorithms for executing simple and multi-dimensional aggregate queries on models. Last, we implement our methods in the Time Series Management System (TSMS) ModelarDB (ModelarDB+). Our evaluation shows that compared to widely used formats, ModelarDB+provides up to 13.7x faster ingestion due to high compression, 113x better compression due to the adaptivity of GOLEMM, 573x faster aggregates by using models, and close to linear scalability. It is also extensible and supports online query processing.

The proliferation of advanced mobile terminals opened up a new crowdsourcing avenue, spatial crowdsourcing, to utilize the crowd potential to perform real-world tasks. In this work, we study a new type of spatial crowdsourcing, called time-continuous spatial crowdsourcing (TCSC in short). It supports broad applications for long-term continuous spatial data acquisition, ranging from environmental monitoring to traffic surveillance in citizen science and crowdsourcing projects. However, due to limited budgets and limited availability of workers in practice, the data collected is often incomplete, incurring data deficiency problem. To tackle that, in this work, we first propose an entropy-based quality metric, which captures the joint effects of incompletion in data acquisition and the imprecision in data interpolation. Based on that, we investigate quality-aware task assignment methods for both single- and multi-task scenarios. We show the NP-hardness of the single-task case, and design polynomial-time algorithms with guaranteed approximation ratios. We study novel indexing and pruning techniques for further enhancing the performance in practice. Then, we extend the solution to multi-task scenarios and devise a parallel framework for speeding up the process of optimization. We conduct extensive experiments on both real and synthetic datasets to show the effectiveness of our proposals.

The widespread diffusion of smartphones offers a capable foundation for the deployment of Spatial Crowdsourcing (SC), where mobile users, called workers, perform location- dependent tasks assigned to them. A key issue in SC is how best to assign tasks, e.g., the delivery of food and packages, to appropriate workers. Specifically, we study the problem of Fairness-aware Task Assignment (FTA) in SC, where tasks are to be assigned in a manner that achieves some notion of fairness across workers. In particular, we aim to minimize the payoff difference among workers while maximizing the average worker payoff. To solve the problem, we first generate so-called Valid Delivery Point Sets (VDPSs) for each worker according to an approach that exploits dynamic programming and distance- constrained pruning. Next, we show that FTA is NP-hard and proceed to propose two heuristic algorithms, a Fairness-aware Game-Theoretic (FGT) algorithm and an Improved Evolutionary Game-Theoretic (IEGT) algorithm. More specifically, we formulate FTA as a multi-player game. In this setting, the FGT approach represents a best-response method with sequential and asynchronous updates of workers' strategies, given by the VDPSs, that achieves a satisfying task assignment when a pure Nash equilibrium is reached. Next, the IEGT approach considers a setting with a large population of workers that repeatedly engage in strategic interactions. The IEGT approach exploits replicator dynamics that cause the whole population to evolve and choose better resources, i.e., VDPSs. Using the property of evolutionary equilibrium, a satisfying task assignment is obtained that corresponds to a stable state with similar payoffs among workers and good average worker payoff. Extensive experiments offer insight into the effectiveness and efficiency of the proposed solutions.

Very large time series are increasingly available from an ever wider range of IoT-enabled sensors deployed in different environments. Significant insights can be gained by mining temporal patterns from these time series. Unlike traditional pattern mining, temporal pattern mining (TPM) adds event time intervals into extracted patterns, making them more expressive at the expense of increased time and space complexities. Existing TPM methods either cannot scale to large datasets, or work only on pre-processed temporal events rather than on time series. This paper presents our Frequent Temporal Pattern Mining from Time Series (FTPMfTS) approach providing: (1) The end-to-end FTPMfTS process taking time series as input and producing frequent temporal patterns as output. (2) The efficient Hierarchical Temporal Pattern Graph Mining (HTPGM) algorithm that uses efficient data structures for fast support and confidence computation, and employs effective pruning techniques for significantly faster mining. (3) An approximate version of HTPGM that uses mutual information, a measure of data correlation, to prune unpromising time series from the search space. (4) An extensive experimental evaluation showing that HTPGM outperforms the baselines in runtime and memory consumption, and can scale to big datasets. The approximate HTPGM is up to two orders of magnitude faster and less memory consuming than the baselines, while retaining high accuracy.

The deployment of vehicle location services generates increasingly massive vehicle trajectory data, which incurs high storage and transmission costs. A range of studies target offline compression to reduce the storage cost. However, to enable online services such as real-time traffic monitoring, it is attractive to also reduce transmission costs by being able to compress streaming trajectories in real-time. Hence, we propose a framework called TRACE that enables compression, transmission, and querying of network-constrained streaming trajectories in a fully online fashion. We propose a compact two-stage representation of streaming trajectories: a speed-based representation removes redundant information, and a multiple-references based referential representation exploits subtrajectory similarities. In addition, the online referential representation is extended with reference selection, deletion and rewriting functions that further improve the compression performance. An efficient data transmission scheme is provided for achieving low transmission overhead. Finally, indexing and filtering techniques support efficient real-time range queries over compressed trajectories. Extensive experiments with real-life and synthetic datasets evaluate the different parts of TRACE, offering evidence that it is able to outperform the existing representative methods in terms of both compression ratio and transmission cost.

Renewable Energy Sources such as wind and solar do not emit CO2but their production vary considerably depending on time and weather. Thus, it is important to use the flexibility in device loads to shift energy consumption to follow the production. For example, an Electrical Vehicle (EV) can be charged very flexibly between arriving home at 5PM and leaving again at 7AM. Utilizing all available energy flexibility requires applying machine learning and AI on massive amounts of Big Data from many different actors and devices, ranging from private consumers, over companies, to energy network operators, and using this to create digital solutions to enable and exploit flexibility. The project Flexible Energy Denmark (FED) is building the foundation for this for the entire Danish society. Specifically, FED collects data from a number of Living Labs (LLs) in representative real-life physical environments. The data is stored in the Danish National Energy Data Lake, called FED Data Lake (FEDDL) to enable efficient and advanced analysis. FEDDL is built using only open source tools which can run both on-premise and in cloud settings. In this paper, we describe the requirements for FEDDL based on a representative LL case study, present its technical architecture, and provide a comparison of relevant tools along with the arguments for which ones we selected.

Very large time series are increasingly available from an ever wider range of IoT-enabled sensors deployed in different environments. Significant insights and values can be obtained from these time series through performing cross-domain analyses, one of which is analyzing time delay temporal correlations across different datasets. Most existing works in this area are either limited in the type of detected relations, e.g., linear relations alone, only working with a fixed temporal scale, or not considering time delay between time series. This paper presents our Time delaY COrrelation Search (TYCOS) approach which provides a powerful and robust solution with the following features: (1) TYCOS is based on the concept of mutual information (MI) from information theory, giving it a strong theoretical foundation to detect all types of relations including non-linear ones, (2) TYCOS is able to discover time delay correlations at multiple temporal scales, (3) TYCOS works in an efficient, bottom-up fashion, pruning non-interesting time intervals from the search by employing a novel MI-based noise theory, and (4) TYCOS is designed to efficiently minimize computational redundancy. A comprehensive experimental evaluation using synthetic and real-world datasets from the energy and smart city domains shows that TYCOS is able to find significant time delay correlations across different time intervals among big time series. The performance evaluation shows that TYCOS can scale to large datasets, and achieve an average speedup of 2 to 3 orders of magnitude compared to the baselines by using the proposed optimizations.

As the data is becoming bigger, more heterogeneous, and originating from different sources, the availability of the same information in different forms leads to various entity linkage problems. We demonstrate our skyex package, an R package that supports all three steps of entity linkage: blocking, pairwise comparison, and labeling. Thus, the user can solve the whole process using skyex, but not necessarily; the skyex modules are independent, meaning that the user can easily integrate them with other packages or even other environments. Additionally, we are the first to provide the implementation of two skyline-based algorithms (SkyEx-F and SkyEx-D) that can label the compared pairs without the need for weights, scoring functions, etc. skyex supports the typical workflow of entity linkage, using minimalist, user- friendly function calls.

By expressing physical laws and control strategies, interoperable physical system models such as Functional Mock-up Units(FMUs) are playing a major role in designing, simulating, and evaluating complex (cyber-)physical systems. However, existing FMU simulation software environments require significant user/developer effort when such models need to be tightly integrated with actual data from a database and/or model simulation results need to be stored in a database, e.g., as a part of larger user analytical workflows. Hence, users encounter substantial complexity and overhead when using such physical models to solve analytical problems based on real data. To address this issue, this paper proposes pgFMU - an extension to the relational database management system PostgreSQL for integrating and conveniently using FMU-based physical models inside a database environment. pgFMU reduces the complexity in specifying (and executing) analytical workflows based on such simulation models(requiring on average 22x fewer code lines) while maintaining improved overall execution performance (up to 8.43x faster formulti-instance scenarios) due to the optimization techniques and integration between database and an FMU library. With pgFMU,cyber-physical data scientists are able to develop a typical FMUworkflow up to 11.74x faster than using the standard FMU software stack. When combined with an existing in-DBMS analytics tool, pgFMU can increase the accuracy of Machine Learning models by up to 21.1%.

Worker movement information can help the spatial crowdsourcing platform to identify the right time to assign a task to a worker for successful completion of the task. However, the majority of the current assignment strategies do not consider worker movement information. This paper aims to utilize the worker movement information via transits in an online task assignment setting. The idea is to harness the waiting periods at different transit stops in a worker transit route (WTR) for performing the tasks. Given the limited availability of workers’ waiting periods at transit stops, task deadlines and workers’ preference of performing tasks with higher rewards, we define the Transit-based Task Assignment (TTA) problem. The objective of the TTA problem is to maximize the average worker rewards for motivating workers, considering the fixed worker transit models. We solve the TTA problem by considering three variants, step-by-step, from offline to batch-based online versions. The first variant is the offline version of the TTA, which can be reduced to a maximum bipartite matching problem, and be leveraged for the second variant. The second variant is the batch-based online version of the TTA, for which, we propose dividing each batch into an offline version of the TTA problem, along with additional credibility constraints to ensure a certain level of worker response quality. The third variant is the extension of the batch-based online version of the TTA (Flexible-TTA) that relaxes the strict nature of the WTR model and assumes that a task with higher reward than a worker-defined threshold value will convince the worker to stay longer at the transit stop. Through our extensive evaluation, we observe that the algorithm solving the Flexible-TTA problem outperforms the algorithms proposed to solve other variants of the TTA problems, by 55% in terms of the number of assigned tasks, and by at least 35% in terms of average reward for the worker. With respect to the baseline (online task assignment) algorithm, the algorithm solving the Flexible-TTA problem results in three times higher reward and at least three times faster runtime.

Massive volumes of uncertain trajectory data are being generated by GPS devices. Due to the limitations of GPS data, these trajectories are generally uncertain. This state of affairs renders it is attractive to be able to compress uncertain trajectories and to be able to query the trajectories efficiently without the need for (full) decompression. Unlike existing studies that target accurate trajectories, we propose a framework that accommodates uncertain trajectories in road networks. To address the large cardinality of instances of a single uncertain trajectory, we exploit the similarity between uncertain trajectory instances and provide a referential representation. First, we propose a reference selection algorithm based on the notion of Fine-grained Jaccard Distance to efficiently select trajectory instances as references. Then we provide referential representations of the different types of information contained in trajectories to achieve high compression ratios. In particular, a new compression scheme for temporal information is presented to take into account variations in sample intervals. Finally, we propose an index and develop filtering techniques to support efficient queries over compressed uncertain trajectories. Extensive experiments with real-life datasets offer insight into the properties of the framework and suggest that it is capable of outperforming the existing state-of-the-art method in terms of both compression ratio and efficiency.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracityproblem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges, since a probabilistic database can have exponential number of possible worlds under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. We study two types of aggregation: convolution and sketch-based, which take polynomial time complexities for aggregation and jointly enable efficient query processing. Also, our proposal is versatile in terms of: 1) its capability of supporting common aggregation functions, i.e., SUM, COUNT, MAX, and AVG; 2) its adaptivity to different materialization strategies, e.g., full versus partial materialization, with support of our devised cost models and parallelization framework; 3) its coverage of common OLAP operations, i.e., probabilistic slicing and dicing queries. Extensive experiments over real and synthetic datasets show that our techniques are effective and scalable.

OpenStreetMap (OSM) is a popular community-driven mapping platform with voluntary contributions from (amateur) cartographers. However, it is a difficult process for the cartographer to identify the areas where she can best contribute to OSM. Furthermore, the current OSM spatial entities are missing many tags; for example, top three road network tags, Name, Source, and Surface, are available only for the 10% of the total road segments. Our paper aims to improve the quantity and quality of the road network tags by actively pushing the nearest road segments for the cartographer to be mapped. We propose a push-based spatial crowdsourcing method to achieve this objective, and validate it by focusing on road segments in OSM. Specifically, we formally define the batch-based maximum road segment task assignment problem and suggest methods based on heuristics like travel distance and road segment task grouping. Finally, our experimental evaluation verify the applicability of our assignment solutions by comparing the resulting number of assigned tasks. With regard to the number of assigned road segments, our junctions-based and road segment-based heuristic methods, outperform the baseline methods by five and two times, respectively.

Recent developments in computing and IoT technology have enabled the daily generation of enormous amounts of time series data. These time series have to be analyzed to create value. A fundamental type of analysis is to find temporal correlations between given sets of time series. To provide a robust method for solving this problem, several properties are desirable. First, the method should have a strong theoretical foundation. Second, since temporal correlations can occur at different temporal scales, e.g., sub-second versus weekly, it is important that the method is capable of discovering multitemporal scale correlations. Finally, the method should be efficient and scalable. This paper presents an approach to search for synchronous correlations in big time series that displays all three properties: the proposed method (i) utilizes the metric of mutual information from information theory, providing a strong theoretical foundation, (ii) is able to discover correlations at multiple temporal scales, and (iii) works in an efficient, bottom-up fashion, making it scalable to large datasets. Our experiments verify that the proposed approach can identify various types of correlation relations across multiple temporal scales, while achieving a performance of an order of magnitude faster than the state-of-the-art techniques.

Due to the big amounts of sensor data produced, it is infeasible to store all of the data points collected and practitioners currently hide outliers by storing simple aggregates instead. As a remedy, we demonstrate ModelarDB, a model-based Time Series Management System (TSMS) for time series with dimensions and possibly gaps. In this demonstration, participants can ingest data sets from multiple domains and experience how ModelarDB provides fast ingestion and a high compression ratio by adaptively compressing time series using a set of models to accommodate changes in the structure of each time series over time. Models approximate time series within a user-defined error bound (possibly zero). Participants can also experience how the compression ratio can be improved by ingesting correlated time series in groups created by ModelarDB from user-hints. Participants provide these using primitives for describing correlation. Last, participants can execute SQL queries on the ingested data sets and see how the system optimizes queries directly on models.

Geo-social data has been an attractive source for a variety of problems such as mining mobility patterns, link prediction, location recommendation, and influence maximization. However, new geo-social data is increasingly unavailable and suffers several limitations. In this paper, we aim to remedy the problem of effective data extraction from geo-social data sources. We first identify the limitations of extracting geo-social data. To overcome the limitations, we propose a novel seed-driven approach that uses the points of one source as the seed to feed as queries for the others. We additionally handle differences between, and dynamics within the sources by proposing three variants for optimizing search radius. Furthermore, we provide an optimization based on recursive clustering to minimize the number of requests and an adaptive procedure to learn the specific data distribution of each source. Our comprehensive experiments with six popular sources show that our seed-driven approach yields 14.3 times more data overall, while our request-optimized algorithm retrieves up to 95% of the data with less than 16% of the requests. Thus, our proposed seed-driven approach set new standards for effective and efficient extraction of geo-social data.

Besides the traditional cartographic data sources, spatial information can also be derived from location-based sources. Location-based sources offer rich spatial information describing the semantics of locations. However, even though different location-based sources refer to the same physical world, each one has only partial coverage of the spatial entities of interest, describe them with different attributes, and sometimes provide contradicting information. Hence, the problem of finding which pairs of spatial entities belong to the same physical spatial entity demands specific attention. We propose a solution (QuadSky) to the problem of spatial entity linkage across diverse location-based sources. QuadSky starts with a spatial blocking technique (QuadFlex) that inherits the concept and the complexity from the quadtree algorithm but improves the splitting technique not to separate nearby points. After comparing the spatial entities of the same block, we propose a novel algorithm, referred to as SkyEx that separates the pairs considered as a match (positive class) from the rest (negative class) by using Pareto optimality. SkyEx does not require weights on the attributes, scoring function, or a training set. QuadSky achieves 0.85 precision and 0.85 recall for a manually labeled dataset of 1,500 pairs and 0.87 precision and 0.6 recall for a semi-manually labeled dataset of 777,452 pairs. Moreover, QuadSky provides the best trade-off between precision and recall and consequently, the best F-measure compared to the existing baselines.

With the increase of devices equipped with location sensors, mining spatio-temporal data for interesting behavioral patterns has gained attention in recent years. One of such well-known patterns is the convoy pattern which can be used, e.g., to find groups of people moving together in public transport or to prevent traffic jams. A convoy consists of at least m objects moving together for at least k consecutive time instants where m and k are user-defined parameters. Convoy mining is an expensive task and existing sequential algorithms do not scale to real-life dataset sizes. Existing sequential as well as parallel algorithms require a complex set of data-dependent parameters which are hard to set and tune. Therefore, in this paper, we propose a new fast exact sequential convoy pattern mining algorithm "k/2-hop" that is free of data-dependent parameters. The proposed algorithm processes the data corresponding to a few specific key timestamps at each step and quickly prunes objects with no possibility of forming a convoy. Thus, only a very small portion of the complete dataset is considered for mining convoys. Our experimental results show that k/2-hop outperforms existing sequential as well as parallel convoy pattern mining algorithms by orders of magnitude, and scales to larger datasets which existing algorithms fail on.

Widespread use of advanced mobile devices has led to the emergence of a new class of crowdsourcing called spatial crowdsourcing. Spatial crowdsourcing advances the potential of a crowd to perform tasks related to real-world scenarios involving physical locations, which were not feasible with conventional crowdsourcing methods. The main feature of spatial crowdsourcing is the presence of spatial tasks that require workers to be physically present at a particular location for task fulfillment. Research related to this new paradigm has gained momentum in recent years, necessitating a comprehensive survey to offer a bird’s-eye view of the current state of spatial crowdsourcing literature. In this article, we discuss the spatial crowdsourcing infrastructure and identify the fundamental differences between spatial and conventional crowdsourcing. Furthermore, we provide a comprehensive view of the existing literature by introducing a taxonomy, elucidate the issues/challenges faced by different components of spatial crowdsourcing, and suggest potential research directions for the future.

Location-based social networks (LBSN) are social networks complemented with users' location data, such as geo-tagged activity data. Predicting such activities finds application in marketing, recommendation systems, and logistics management. In this paper, we exploit LBSN data to predict future visitors at given locations. We fetch the travel history of visitors by their check-ins in LBSNs and identify five features that significantly drive the mobility of a visitor towards a location: (i) historic visits, (ii) location category, (iii) time, (iv) distance, and (v) friends' activities. We provide a visitor prediction model, CMViP, based on collective matrix factorization and influence propagation. CMViP first utilizes collective matrix factorization to map the first four features to a common latent space to find visitors having a significant potential to visit a given location. Then, it utilizes an influence-mining approach to further incorporate friends of those visitors, who are influenced by the visitors' activities and likely to follow them. Our experiments on two real-world data-sets show that our methods outperform the state of art in terms of precision and accuracy.

Industrial systems, e.g., wind turbines, generate big amounts of data from reliable sensors with high velocity. As it is unfeasible to store and query such big amounts of data, only simple aggregates are currently stored. However, aggregates remove fluctuations and outliers that can reveal underlying problems and limit the knowledge to be gained from historical data. As a remedy, we present the distributed Time Series Management System (TSMS) ModelarDB that uses models to store sensor data. We thus propose an online, adaptive multi-model compression algorithm that maintains data values within a user-defined error bound (possibly zero). We also propose (i) a database schema to store time series as models, (ii) methods to push-down predicates to a key-value store utilizing this schema, (iii) optimized methods to execute aggregate queries on models, (iv) a method to optimize execution of projections through static code-generation, and (v) dynamic extensibility that allows new models to be used without recompiling the TSMS. Further, we present a general modular distributed TSMS architecture and its implementation, ModelarDB, as a portable library, using Apache Spark for query processing and Apache Cassandra for storage. An experimental evaluation shows that, unlike current systems, ModelarDB hits a sweet spot and offers fast ingestion, good compression, and fast, scalable online aggregate query processing at the same time. This is achieved by dynamically adapting to data sets using multiple models. The system degrades gracefully as more outliers occur and the actual errors are much lower than the bounds.

Due to the popularity of social networks with geo-tagged activities, so-called location-based social networks (LBSN), a number of methods have been proposed for influence maximization for applications such as word-of-mouth marketing (WOMM), and out-of-home marketing (OOH). It is thus important to analyze and compare these different approaches. In this demonstration, we present a unified system IMaxer that both provides a complete pipeline of state-of-the-art and novel models and algorithms for influence maximization (IM) as well as allows to evaluate and compare IM techniques for a particular scenario. IMaxer allows to select and transform the required data from raw LBSN datasets. It further provides a unified model that utilizes interactions of nodes in an LBSN, i.e., users and locations, for capturing diverse types of information propagations. On the basis of these interactions, influential nodes can be found and their potential influence can be simulated and visualized using Google Maps and graph visualization APIs. Thus, IMaxer allows users to compare and pick the most suitable IM method in terms of effectiveness and cost.

In this demo, we present SolveDB - the first purely SQL-based DBMS for optimization problem solving and solver integration. SolveDB provides (1) an SQL-based syntax for optimization problem specification, (2) an extensible infrastructure of solvers for different classes of problems (e.g., linear programming), and (3) query optimization techniques to achieve the best execution performance and/or result quality. We demonstrate how our PostgreSQL-based SolveDB implementation allows simplifying specifications of data-driven optimization problems and increasing overall solving performance for (1) traditional well-known optimization problems, (2) "how-to" problems based on TPC-H, and (3) a complex energy planning problem with interlinked energy forecasting and load scheduling.

Location-based social networks (LBSN) are social networks complemented with location data such as geo-tagged activity data of its users. In this paper, we study how users of a LBSN are navigating between locations and based on this information we select the most influential locations. In contrast to existing works on influence maximization, we are not per se interested in selecting the users with the largest set of friends or the set of locations visited by the most users; instead, we introduce a notion of location influence that captures the ability of a set of locations to reach out geographically. We provide an exact on-line algorithm and a more memory-efficient but approximate variant based on the HyperLogLog sketch to maintain a data structure called Influence Oracle that allows to efficiently find a top-k set of influential locations. Experiments show that our algorithms are efficient and scalable and that our new location influence notion favors diverse sets of locations with a large geographical spread.

The collection of time series data increases as more monitoring and automation are being deployed. These deployments range in scale from an Internet of things (IoT) device located in a household to enormous distributed Cyber-Physical Systems (CPSs) producing large volumes of data at high velocity. To store and analyze these vast amounts of data, specialized Time Series Management Systems (TSMSs) have been developed to overcome the limitations of general purpose Database Management Systems (DBMSs) for times series management. In this paper, we present a thorough analysis and classification of TSMSs developed through academic or industrial research and documented through publications. Our classification is organized into categories based on the architectures observed during our analysis. In addition, we provide an overview of each system with a focus on the motivational use case that drove the development of the system, the functionality for storage and querying of time series a system implements, the components the system is composed of, and the capabilities of each system with regard to Stream Processing and Approximate Query Processing (AQP). Last, we provide a summary of research directions proposed by other researchers in the field and present our vision for a next generation TSMS.

RFID (Radio Frequency Identification)-based object tracking is increasingly deployed and used in indoor environments such as airports, shopping malls, etc. However, the inherent noise in the raw RFID data makes it difficult to support queries and analyses on the data. In this paper, we propose an RFID data cleansing based on regular expressions. We generate the regular expressions in an automaton that captures all possible indoor paths from the spatial and temporal aspects of indoor space and deployed readers. Given the raw data of an object, the proposed matching algorithm finds all the matching paths using the automaton. We evaluate the proposed approach by conducting experimental studies using real dataset. The results demonstrate the effectiveness of the propose approach.

Publication and sharing of multidimensional (MD) data on the Semantic Web (SW) opens new opportunities for the use of On-Line Analytical Processing (OLAP). The RDF Data Cube (QB) vocabulary, the current standard for statistical data publishing, however, lacks key MD concepts such as dimension hierarchies and aggregate functions. QB4OLAP was proposed to remedy this. However, QB4OLAP requires extensive manual annotation and users must still write queries in SPARQL, the standard query language for RDF, which typical OLAP users are not familiar with. In this demo, we present QB2OLAP, a tool for enabling OLAP on existing QB data. Without requiring any RDF, QB(4OLAP), or SPARQL skills, it allows semi-automatic transformation of a QB data set into a QB4OLAP one via enrichment with QB4OLAP semantics, exploration of the enriched schema, and querying with the high-level OLAP language QL that exploits the QB4OLAP semantics and is automatically translated to SPARQL.

On-Line Analytical Processing (OLAP) enables powerful analytics by quickly computing aggregate values of numerical measures over multiple hierarchical dimensions for massive datasets. However, many types of source data, e.g., from GPS, sensors, and other measurement devices, are intrinsically inaccurate (imprecise and/or uncertain) and thus OLAP cannot be readily applied. In this paper, we address the resulting data veracity problem in OLAP by proposing the concept of probabilistic data cubes. Such a cube is comprised of a set of probabilistic cuboids which summarize the aggregated values in the form of probability mass functions (pmfs in short) and thus offer insights into the underlying data quality and enable confidence-aware query evaluation and analysis. However, the probabilistic nature of data poses computational challenges as even simple operations are #P-hard under the possible world semantics. Even worse, it is hard to share computations among different cuboids, as aggregation functions that are distributive for traditional data cubes, e.g., SUM and COUNT, become holistic in probabilistic settings. In this paper, we propose a complete set of techniques for probabilistic data cubes, from cuboid aggregation, over cube materialization, to query evaluation. For aggregation, we focus on how to maximize the sharing of computation among cells and cuboids. We present two aggregation methods: convolution and sketch-based. The two methods scale down the time complexities of building a probabilistic cuboid to polynomial and linear, respectively. Each of the two supports both full and partial data cube materialization. Then, we devise a cost model which guides the aggregation methods to be deployed and combined during the cube materialization. We further provide algorithms for probabilistic slicing and dicing queries on the data cube. Extensive experiments over real and synthetic datasets are conducted to show that the techniques are effective and scalable.

The ongoing trend for data gathering not only produces larger volumes of data, but also increases the variety of recorded data types. Out of these, especially time series, e.g. various sensor readings, have attracted attention in the domains of business intelligence and decision making. As OLAP queries play a major role in these domains, it is desirable to also execute them on time series data. While this is not a problem on the conceptual level, it can become a bottleneck with regards to query run-time. In general, processing OLAP queries gets more computationally intensive as the volume of data grows. This is a particular problem when querying time series data, which generally contains multiple measures recorded at fine time granularities. Usually, this issue is addressed either by scaling up hardware or by employing workload based query optimization techniques. However, these solutions are either costly or require continuous maintenance. In this paper we propose an approach for approximate OLAP querying of time series that offers constant latency and is maintenance-free. To achieve this, we identify similarities between aggregation cuboids and propose algorithms that eliminate the redundancy these similarities present. In doing so, we can achieve compression rates of up to 80% while maintaining low average errors in the query results.

Technologies such as RFID and Bluetooth have received considerable attention for tracking indoor moving objects. In a time-critical indoor tracking scenario such as airport baggage handling, a bag has to move through a sequence of locations until it is loaded into the aircraft. Inefficiency or inaccuracy at any step can make the bag risky, i.e., the bag may be delayed at the airport or sent to a wrong airport. In this paper, we propose a novel probabilistic approach for predicting the risk of an indoor moving object in real-time. We propose a probabilistic flow graph (PFG) and an aggregated probabilistic flow graph (APFG) that capture the historical object transitions and the durations of the transitions. In the graphs, the probabilistic information is stored in a set of histograms. Then we use the flow graphs for obtaining a risk score of an online object and use it for predicting its riskiness. The paper reports a comprehensive experimental study with multiple synthetic data sets and a real baggage tracking data set. The experimental results show that the proposed method can identify the risky objects very accurately when they approach the bottleneck locations on their paths and can significantly reduce the operation cost.

Due to the wide spread of mobile devices equipped with location sensors, the amount of mobility data being generated is enormous. Mining this data to reveal interesting behavioral patterns has gained attention in recent years. Various mobility patterns have been proposed which describe collective mobility behaviour. One such pattern is the convoy pattern which can be used to find groups of people moving together in public transport or for prevention of traffic jams. A convoy consists of at least m objects moving together for at least k consecutive time instants where m and k are user-defined parameters. Existing algorithms for detecting convoy patterns, however, do not scale to real-life dataset sizes. Therefore in this paper, we propose a generic distributed convoy pattern mining algorithm and show how such an algorithm can be implemented using the MapReduce framework. Our experimental results show that our distributed algorithm is scalable and more efficient than the existing sequential convoy pattern mining algorithms.

Using GPS-enabled smart phones, social network services are enriched with location information which allows users to share geo-tagged contents with their friends. This so called location-based social network (LBSN) data has a dual spatial and graph nature. The growing scale and importance of LBSN data necessitate a platform which (i) has both spatial and graph capabilities, (ii) supports a wide range of queries, e.g., selection, structural, and aggregate queries, (iii) supports scalable distributed processing of large data volumes. In this paper, we propose such a platform, called Geo Social-GraphX, that segregates the LBSN data into several specific graphs capturing user-user, user-location, and location-location relationships, and enables a wide range of LBSN queries by proposing a comprehensive set of query primitives that can be composed into more advanced queries. We implement the platform based on GraphX, a map-reduce infrastructure for distributed graph computation. We further improve the query performance in several ways. For social-related data, we use vertex-centric messaging operators which better address the recursive nature of graph data than traditional two-stage map-reduce. For spatial-related data, we use effective spatial partitioning and indexing methods. Experiments on both synthetic and real LBSN datasets show that Geo Social-GraphX can process a variety of LBSN queries efficiently, scales on multicore architectures, and achieves much better performance than the state of the art competing framework, Spatial Hadoop.

RFID is widely used for object tracking in indoor environments, e.g., airport baggage tracking. Analyzing RFID data offers insight into the underlying tracking systems as well as the associated business processes. However, the inherent uncertainty in RFID data, including noise (cross readings) and incompleteness (missing readings), pose challenges to high-level RFID data querying and analysis. In this paper, we address these challenges by proposing a learning-based data cleansing approach that, unlike existing approaches, requires no detailed prior knowledge about the spatio-temporal properties of the indoor space and the RFID reader deployment. Requiring only minimal information about RFID deployment, the approach learns relevant knowledge from raw RFID data and uses it to cleanse the data. In particular, we model raw RFID readings as time series that are sparse because the indoor space is only partly covered by a limited number of RFID readers.

Many real-world decision problems involve solving optimization problems based on data in an SQL database. Traditionally, solving such problems requires combining a DBMS with optimization software packages for each required class of problems (e.g. linear and constraint programming) -- leading to workflows that are cumbersome, complex, inefficient, and error-prone. In this paper, we present SolveDB - a DBMS for optimization applications. SolveDB supports solvers for different problem classes and offers seamless data management and optimization problem solving in a pure SQL-based setting. This allows for much simpler and more effective solutions of database-based optimization problems. SolveDB is based on the 3-level ANSI/SPARC architecture and allows formulating, solving, and analysing solutions of optimization problems using a single so-called solve query. SolveDB provides (1) an SQL-based syntax for optimization problems, (2) an extensible infrastructure for integrating different solvers, and (3) query optimization techniques to achieve the best execution performance and/or result quality. Extensive experiments with the PostgreSQL-based implementation show that SolveDB is a versatile tool offering much higher developer productivity and order of magnitude better performance for specification-complex and data-intensive problems.

Having constantly increasing amounts of data, the analysis of it is often entrusted for a MapReduce framework. The execution of an analytical workload can be cheapened by adopting cloud computing resources, and in particular by using spot instances (cheap, fluctuating price instances) offered by Amazon Web Services (AWS). The users aiming for the spot market are presented with many instance types placed in multiple datacenters in the world, and thus it is difficult to choose the optimal deployment. In this paper, we propose the framework SpotADAPT (Spot-Aware (re-)Deployment of Analytical Processing Tasks) which is designed to help users by first, estimating the workload execution time on different AWS instance types, and, second, proposing the deployment (i.e., specific availability zone, instance type, pricing model) aligned with user-provided optimization goals (fastest or cheapest execution within boundaries). Moreover, during the execution of the workload, SpotADAPT suggests a redeployment if the current spot instance gets terminated by Amazon or a better deployment becomes possible due to fluctuations of the spot prices. The approach is evaluated using the actual execution times of typical analytical workloads and real spot price traces. SpotADAPT's suggested deployments are comparable to the theoretically optimal ones, and in particular, it shows good cost benefits for the budget optimization - on average SpotADAPT is at most 0.3% more expensive than the theoretically optimal deployments.

In order to create better decisions for business analytics, organizations increasingly use external data, structured, semi-structured and unstructured, in addition to the (mostly structured) internal data. Current Extract-Transform-Load (ETL) tools are not suitable for this "open world scenario" because they do not consider semantic issues in the integration process. Also, current ETL tools neither support processing semantic-aware data nor create a Semantic Data Warehouse (DW) as a semantic repository of semantically integrated data. This paper describes SETL: a (Python-based) programmable Semantic ETL framework. SETL builds on Semantic Web (SW) standards and tools and supports developers by offering a number of powerful modules, classes and methods for (dimensional and semantic) DW constructs and tasks. Thus it supports semantic-aware data sources, semantic integration, and creating a semantic DW, composed of an ontology and its instances. A comprehensive experimental evaluation comparing SETL to a solution made with traditional tools (requiring much more hand-coding) on a concrete use case, shows that SETL provides better performance, knowledge base quality and programmer productivity.

Increasingly, streaming positions from moving objects in blended indoor/outdoor spaces are used to deliver new types of real-time location-based services. To support such scenarios, this paper presents the Searchlight Graph (SLG) model and the associated Searchlight Continuous Query Processing Framework (CQPF) for (predictive) Continuous Query Processing (CQP) in symbolic indoor/outdoor spaces. The model captures both actual and predicted object movement, object-specific edge costs, and location/object context annotation with keywords, enabling context-aware (predictive) querying of both locations and objects. Furthermore, the paper proposes several types of continuous spatio-temporal queries, expressed in the declarative Searchlight Query Language (SLQL), along with novel query processing algorithms, and describes their implementation in the Searchlight CQPF. Finally, a novel location prediction algorithm is proposed. Extensive experimental studies show that Searchlight is scalable, efficient, and outperforms its main competitor.

Airport baggage management is a significant part of the aviation industry. However, for several reasons every year a vast number of bags are mishandled (e.g., Left behind, send to wrong flights, gets lost, etc.,) which costs a lot of money to the aviation industry as well as creates inconvenience and frustration to the passengers. To remedy these problems we propose a detailed methodology for mining risk factors from Radio Frequency Identification (RFID) baggage tracking data. The factors should identify potential issues in the baggage management. However, the baggage tracking data are low level and not directly accessible for finding such factors. Moreover, baggage tracking data are highly imbalanced, for example, our experimental data, which is a large real-world data set from the Scandinavian countries, contains only 0.8% mishandled bags. This imbalance presents difficulties to most data mining techniques. The paper presents detailed steps for pre-processing the unprocessed raw tracking data for higher-level analysis and handling the imbalance problem. We fragment the data set based on a number of relevant factors and find the best classifier for each of them. The paper reports on a comprehensive experimental study with real RFID baggage tracking data and it shows that the proposed methodology results in a strong classifier, and can find interesting concrete patterns and reveal useful insights of the data.

This paper describes the convergence of some of the most influential technologies in the last few years, namely data warehousing (DW), on-line analytical processing (OLAP), and the Semantic Web (SW). OLAP is used by enterprises to derive important business-critical knowledge from data inside the company. However, the most interesting OLAP queries can no longer be answered on internal data alone, external data must also be discovered (most often on the web), acquired, integrated, and (analytically) queried, resulting in a new type of OLAP, exploratory OLAP. When using external data, an important issue is knowing the precise semantics of the data. Here, SW technologies come to the rescue, as they allow semantics (ranging from very simple to very complex) to be specified for web-available resources. SW technologies do not only support capturing the “passive” semantics, but also support active inference and reasoning on the data. The paper first presents a characterization of DW/OLAP environments, followed by an introduction to the relevant SW foundation concepts. Then, it describes the relationship of multidimensional (MD) models and SW technologies, including the relationship between MD models and SW formalisms. Next, the paper goes on to survey the use of SW technologies for data modeling and data provisioning, including semantic data annotation and semantic-aware extract, transform, and load (ETL) processes. Finally, all the findings are discussed and a number of directions for future research are outlined, including SW support for intelligent MD querying, using SW technologies for providing context to data warehouses, and scalability issues.

In many scientific and commercial domains, we encounter flexibility objects, i.e., objects with explicit flexibilities in a time and an amount dimension (e.g., energy or product amount). Applications of flexibility objects require novel and efficient techniques capable of handling large amounts of such objects while preserving flexibility. Hence, this paper formally defines the concept of flexibility objects (flex-objects) and provides a novel and efficient solution for aggregating and disaggregating flex-objects. Out of the broad range of possible applications, this paper will focus on smart grid energy data management and discuss strategies for aggregation and disaggregation of flex-objects while retaining flexibility. This paperfurther extends these approaches beyond flex-objects originating from energy consumption by additionally considering flex-objects originating from energy production and aiming at energy balancing during aggregation. In more detail, this paper considers the complete life cycle of flex-objects: aggregation, disaggregation, associated requirements, efficient incremental computation, and balance aggregation techniques. Extensive experiments based on real-world data from the energy domain show that the proposed solutions provide good performance while satisfying the strict requirements.

Indoor spaces accommodate large parts of people's lives. Relevant techniques are thus needed to efficiently manage indoor moving objects, whose positions are detected by technologies, such as Assisted GPS, Wi-Fi, RFID, and Bluetooth. Among such techniques, the distance-aware join processing is of importance in practice for indoor spatial databases. Such join operators leverage a series of applications, such as indoor mobile service and facility monitoring. However, distance-aware joining over indoor moving objects is challenging because: (1) indoor spaces are characterized by many special entities and thus render distance calculation very complex; (2) the limitations of indoor positioning technologies create inherent uncertainties in indoor moving objects data. In this paper, we study two representative join predicates in indoor settings, semi-range join and semi-neighborhood join. To implement them, we define and categorize the indoor distances between indoor uncertain objects, and derive different distance bounds that can facilitate the join processing. We design a composite index scheme that integrates indoor geometries, indoor topologies, as well as indoor uncertain objects, and thus supports the join processing efficiently. The results of extensive experimental studies demonstrate that our proposals are efficient and scalable in evaluating distance-aware join over indoor moving objects.

Next generation BI systems emerge as platforms where traditional BI tools meet semi-structured and unstructured data coming from the Web. In these settings, the user-centric orientation represents a key characteristic for the acceptance and wide usage by numerous and diverse end users in their data analysis tasks. System and user related metadata are the base for enabling user assistance features. However, current approaches typically store these metadata in ad-hoc manners. In this paper, we propose a generic and extensible approach for the definition and modeling of the relevant metadata artifacts. We present SM4AM, a Semantic Metamodel for Analytical Metadata created as an RDF formalization of the Analytical Metadata artifacts needed for user assistance exploitation purposes in next generation BI systems. We consider the Linked Data initiative and its relevance for user assistance functionalities. We discuss the metamodel benefits and present directions for future work.

Extract-Transform-Load (ETL) programs process data into data warehouses (DWs). Rapidly growing data volumes demand systems that scale out. Recently, much attention has been given to MapReduce for parallel handling of massive data sets in cloud environments. Hive is the most widely used RDBMS-like system for DWs on MapReduce and provides scalable analytics. It is, however, challenging to do proper dimensional ETL processing with Hive; e.g., the concept of slowly changing dimensions (SCDs) is not supported (and due to lacking support for UPDATEs, SCDs are complex to handle manually). Also the powerful Pig platform for data processing on MapReduce does not support such dimensional ETL processing. To remedy this, we present the ETL framework CloudETL which uses Hadoop to parallelize ETL execution and to process data into Hive. The user defines the ETL process by means of high-level constructs and transformations and does not have to worry about technical MapReduce details. CloudETL supports different dimensional concepts such as star schemas and SCDs. We present how CloudETL works and uses different performance optimizations including a purpose-specific data placement policy to co-locate data. Further, we present a performance study and compare with other cloud-enabled systems. The results show that CloudETL scales very well and outperforms the dimensional ETL capabilities of Hive both with respect to performance and programmer productivity. For example, Hive uses 3.9 times as long to load an SCD in an experiment and needs 112 statements while CloudETL only needs 4.

Finding the dense locations in large indoor spaces is very useful for getting overloaded locations, security, crowd management, indoor navigation, and guidance. Indoor tracking data can be very large and are not readily available for finding dense locations. This paper presents a graph-based model for semi-constrained indoor movement, and then uses this to map raw tracking records into mapping records representing object entry and exit times in particular locations. Then, an efficient indexing structure, the Dense Location Time Index (DLT-Index) is proposed for indexing the time intervals of the mapping table, along with associated construction, query processing, and pruning techniques. The DLT-Index supports very efficient aggregate point queries, interval queries, and dense location queries. A comprehensive experimental study with real data shows that the proposed techniques can efficiently find dense locations in large amounts of indoor tracking data.

The Radio-Frequency Identification (RFID) is a useful technology for object tracking and monitoring systems in indoor environments, e.g., Airport baggage tracking. Nevertheless, the data produced by RFID tracking is inherently uncertain and contains errors. In order to support meaningful high-level applications including queries and analyses over RFID data, it is necessary to cleanse raw RFID data. In this paper, we focus on false negatives in raw indoor RFID tracking data. False negatives occur when a moving object passes the detection range of an RFID reader but the reader fails to produce any readings. We investigate the topology of indoor spaces as well as the deployment of RFID readers, and propose the transition probabilities that capture how likely objects move from one RFID reader to another. We organize such probabilities, together with the characteristics of indoor topology and RFID readers, into a probabilistic distance-aware graph. With the aid of this graph, we design algorithms to identify false negatives and recover missing information in indoor RFID tracking data. We evaluate the proposed cleansing approach using both real and synthetic datasets. The experimental results show that the approach is effective, efficient and scalable.

Finding the hotspots in large indoor spaces is very important for getting overloaded locations, security, crowd management, indoor navigation and guidance. The tracking data coming from indoor tracking are huge in volume and not readily available for finding hotspots. This paper presents a graph-based model for constrained indoor movement that can map the tracking records into mapping records which represent the entry and exit times of an object in a particular location. Then it discusses the hotspots extraction technique from the mapping records.

The Radio Frequency Identification (RFID) emerges to be one of the key technologies to modernize object tracking and monitoring systems in indoor environments, e.g., airport baggage tracking. Although RFID has advantages over alternative identification technologies, the raw RFID data produced is inherently uncertain and contains errors. The dirty nature of raw RFID data hinders the progress of applying meaningful high-level applications that range from querying to analyzing. Therefore, cleansing RFID data is a high necessity. In this paper, we focus on handling one of the main aspects of raw RFID data, namely, false negatives, which occurs when a moving object passes the detection range of an RFID reader but the reader fails to produce any readings. We investigate the topology of indoor spaces as well as the deployment of RFID readers, and propose the transition probabilities that capture how likely objects move from one RFID reader to another. We organize such probabilities, together with the characteristics of indoor topology and RFID readers, into a probabilistic distance-aware graph model. Further, we evaluate the effectiveness and efficiency of devised graph model in recovering the false negatives using real dataset. The experimental results show that the devised graph model is effective and efficient in handling false negatives in indoor RFID tracking data.

Indoor spaces accommodate large parts of people's life. The increasing availability of indoor positioning, driven by technologies like Wi-Fi, RFID, and Bluetooth, enables a variety of indoor location-based services (LBSs). Efficient indoor distance-aware queries on indoor moving objects play an important role in supporting and boosting such LBSs. However, the distance-aware query evaluation on indoor moving objects is challenging because: (1) indoor spaces are characterized by many special entities and thus render distance calculation very complex; (2) the limitations of indoor positioning technologies create inherent uncertainties in indoor moving objects data. In this paper, we propose a complete set of techniques for efficient distance-aware queries on indoor moving objects. We define and categorize the indoor distances in relation to indoor uncertain objects, and derive different distance bounds that can facilitate query evaluation. Existing works often assume indoor floor plans are static, and require extensive pre-computation on indoor topologies. In contrast, we design a composite index scheme that integrates indoor geometries, indoor topologies, as well as indoor uncertain objects, and thus supports indoor distance-aware queries efficiently without time-consuming and volatile distance computation. We design algorithms for range query and k nearest neighbor query on indoor moving objects. The results of extensive experimental studies demonstrate that our proposals are efficient and scalable in evaluating distance-aware queries over indoor moving objects.

Today, airport baggage handling is far from perfect. Baggage goes on the wrong flights, is left behind, or gets lost, which costs a lot of money for the airlines, as well as frustration for the passengers. To remedy the situation, we present a data warehouse (DW) solution for storing and analyzing spatio-temporal Radio Frequency Identification (RFID) baggage tracking data. Analysis of this data can yield interesting results on baggage flow, the causes of baggage mishandling, and the parties responsible for the mishandling(airline, airport, handler,...), which can ultimately lead to improved baggage handling quality. The paper presents a carefully designed data warehouse (DW), with a relational schema sitting underneath a multidimensional data cube, that can handle the many complexities in the data. The paper also discusses the Extract-Transform-Load (ETL) flow that loads the data warehouse with the appropriate tracking data from the data sources. The presented concepts are generalizable to other types of multi-site indoor tracking systems based on Bluetooth and RFID. The system has been tested with large amount of real-world RFID-based baggage tracking data from a major industry initiative. The developed solution is shown to both reveal interesting insights as well as being several orders of magnitude faster than computing the results directly on the data sources.

The Radio Frequency Identification (RFID) is increasingly being deployed in indoor tracking systems, e.g., airport baggage monitoring. However, the “dirtiness” in raw RFID readings hinder the progress of applying meaningful high level applications that range from monitoring to analysis. Hence, it is indispensable to cleansing RFID data in such systems. In this paper, we focus on two quality aspects in raw indoor RFID data: temporal redundancy and spatial ambiguity. The former refers to the large number of repeated readings for the same object and the same RFID reader during a period of time. The latter refers to the undetermined whereabouts of an object due to multiple readings by different readers simultaneously. We investigate the spatiotemporal characteristics of indoor spaces as well as RFID reader deployment, and exploit them in designing effective data cleansing techniques. Specifically, we aggregate raw RFID readings to reduce temporal redundancy; we design a distance-aware graph to resolve spatial ambiguity with respect to the indoor topology and the RFID reader deployment captured in the graph. We evaluate the spatiotemporal data cleansing techniques using both real and synthetic datasets. The experimental results demonstrate that the proposed techniques are effective and efficient in cleansing indoor RFID tracking data.

Monitoring the actual and predicted flow of receptor-based (e.g. RFID) moving objects can be useful in a variety of applications, e.g., to predict congestion in an airport bag handling system or reason about the location of a lost bag. In this paper, we propose the Flow Representation Graph (FRG) model, which, unlike earlier work, captures both the actual and predicted flow of moving objects in a symbolic space covering both indoor and outdoor space. Further, the FRG supports time- and value-bound semi-constraints on the object flow, which are useful for modeling important real-world conditions. The paper further introduces FlowPredictor, a Continuous Query Processing Framework (CQPF) that supports continuous spatio-temporal selection, aggregate, and nested queries on FRG objects. A range of update policies allows tuning the tradeoff between performance and accuracy. FlowPredictor employs carefully selected data structures to efficiently handle both insertion and lookup for the actual and predicted flow of objects. The experimental study shows that FlowPredictor can handle a high number of receptor readings while simultaneously processing a large number of continuous queries. Furthermore, the proposed optimizations of data insertion and retrieval are shown to yield significant performance and memory advantages.

In this paper we demonstrate FlowPredictor, a novel Continuous Query Processing Framework (CQPF) for continuous query processing of the actual and predicted flow of receptor-based moving objects in a symbolic space covering both indoor and outdoor space. FlowPredictor enables spatiotemporal selection, aggregate, nested, and complex queries to be evaluated using novel algorithms. We illustrate the use of a novel model, called Flow Representation Graph (FRG), in the context of an airport bag handling system using an interactive web interface in FlowPredictor. The web interface allows modelling the FRG as well as definition of continuous spatio-temporal queries. Furthermore, the interface enables the user to manually create readings or start real-time simulations of moving objects in the defined FRG. We conclude by presenting the performance of FlowPredictor under heavy load.

Route evaluation and optimization have received significant attention in recent years. In this light, we propose and investigate a novel problem of estimating the travel time (TTE query) for a user specified path by considering the related traffic conditions. Given a query path and a departure time, TTE query finds the estimated travel time along this path. We believe that this type of query may bring important benefits to users in many popular applications, such as travel route evaluation and optimization, and route planning and recommendation. To address the TTE problem in a convincing approach, we construct a traffic-aware spatial network Gpt(V, E) by analysing uncertain trajectory data of moving objects. Based on Gpt(V, E), we define two novel types of TTE queries: TTEepfor an exact query path, and TTElpfor a loose query path. The performance of the construction of traffic-aware spatial network is verified by extensive experiments based on real and synthetic spatial data sets.

In recent years, indoor spatial data management has started to attract attention, partly due to the increasing use of receptor devices (e.g., RFID readers, and wireless sensor networks) in indoor, as well as outdoor spaces. There is thus a great need for a model that captures such spaces, their receptors, and provides powerful reasoning techniques on top. This paper reviews and extends a recent unified model of outdoor and indoor spaces and receptor deployments in these spaces. The extended model enables modelers to capture various information pieces from the physical world. On top of the extended model, this paper proposes and formalizes the route observability concept, and demonstrates its usefulness in enhancing the reading environment. The extended model also enables incorporating receptor data through a probabilistic trajectory-to-route translator. This translator first facilitates the tracking of moving objects enabling the search for them to be optimized, and second supports high-level reasoning about points of potential traffic (over)load, so-called bottleneck points. The functional analysis illustrates the behavior of the route observability function. The experimental evaluation shows the accuracy of the translator, and the quality of the inference and reasoning. The experiments are conducted on both synthetic data and uncleansed, real-world data obtained from RFID-tagged flight baggage.

This paper proposes a highly efficient bitmap-based approach for discovery of so-called sentinels. Sentinels represent schema level relationships between changes over time in certain measures in a multidimensional data cube. Sentinels are actionable and notify users based on previous observations, for example, that revenue might drop within two months if an increase in customer problems combined with a decrease in website traffic is observed. We significantly extend prior art by representing the sentinel mining problem by bitmap operations, using bitmapped encoding of so-called indication streams. We present a very efficient algorithm, SentBit, that is 2-3 orders of magnitude faster than the state of the art, and utilizes CPU specific instructions and the multicore architectures available on modern processors. The SentBit algorithm scales efficiently to very large data sets, which is verified by extensive experiments on both real and synthetic data.

Geographic information systems traditionally dealt with only outdoor spaces. In recent years, indoor spatial information systems have started to attract attention partly due to the increasing use of receptor devices (e.g., RFID readers or wireless sensor networks) in both outdoor and indoor spaces. Applications that employ these devices are expected to span uniformly and supply seamless functionality in both outdoor and indoor spaces. What makes this impossible is the current absence of a unified account of these two types of spaces both in terms of modeling and reasoning about the models. This paper presents a unified model of outdoor and indoor spaces and receptor deployments in these spaces. The model is expressive, flexible, and invariant to the segmentation of a space plan, and the receptor deployment policy. It is focused on partially constrained outdoor and indoor motion, and it aims at underlying the construction of future, powerful reasoning applications.

We demonstrate TimeTravel, an efficient DBMS system for seamless integrated querying of past and (forecasted) future values of time series, allowing the user to view past and future values as one joint time series. This functionality is important for advanced application domain like energy. The main idea is to compactly represent time series as models. By using models, the TimeTravel system answers queries approximately on past and future data with error guarantees (absolute error and confidence) one order of magnitude faster than when accessing the time series directly. In addition, it efficiently supports exact historical queries by only accessing relevant portions of the time series. This is unlike existing approaches, which access the entire time series to exactly answer the query. To realize this system, we propose a novel hierarchical model index structure. As real-world time series usually exhibits seasonal behavior, models in this index incorporate seasonality. To construct a hierarchical model index, the user specifies seasonality period, error guarantees levels, and a statistical forecast method. As time proceeds, the system incrementally updates the index and utilizes it to answer approximate and exact queries. TimeTravel is implemented into PostgreSQL, thus achieving complete user transparency at the query level. In the demo, we show the easy building of a hierarchical model index for a real-world time series and the effect of varying the error guarantees on the speed up of approximate and exact queries.

This paper demonstrates ETLMR , a novel dimensional Extract--Transform--Load (ETL) programming framework that uses Map-Reduce to achieve scalability. ETLMR has built-in native support of data warehouse (DW) specific constructs such as star schemas, snowflake schemas, and slowly changing dimensions (SCDs). This makes it possible to build MapReduce-based dimensional ETL flows very easily. The ETL process can be configured with only few lines of code. We will demonstrate the concrete steps in using ETLMR to load data into a (partly snowflaked) DW schema. This includes configuration of data sources and targets, dimension processing schemes, fact processing, and deployment. In addition, we also present the scalability on large data sets.

In order to keep more detailed data available for longer periods, old data has to be reduced gradually to save space and improve query performance, especially on resource-constrained systems with limited storage and query processing capabilities. In this regard, some hand-coded data aggregation solutions have been developed; however, their actual usage have been limited, for the reason that hand-coded data aggregation solutions have proven themselves too complex to maintain. Maintenance need to occur as requirements change frequently and the existing data aggregation techniques lack flexibility with regards to efficient requirements change management. This paper presents an effective rule-based tool for data reduction based on gradual granular data aggregation. With the proposed solution, data can be maintained at different levels of granularity. The solution is based on high-level data aggregation rules. Based on these rules, data aggregation code can be auto-generated. The solution is effective, easy-to-use and easy-to-maintain. In addition, the paper also demonstrates the use of the proposed tool based on a farming case study using standard database technologies. The results show productivity of the proposed tool-based solution in terms of initial development time, maintenance time and alteration time as compared to a hand-coded solution.

Extract-Transform-Load (ETL) programs are used to load data into data warehouses (DWs). An ETL program must extract data from sources, apply different transformations to it, and use the DW to look up/insert the data. It is both time consuming to develop and to run an ETL program. It is, however, typically the case that the ETL program can exploit both task parallelism and data parallelism to run faster. This, on the other hand, makes the development time longer as it is complex to create a parallel ETL program. To remedy this situation, we propose efficient ways to parallelize typical ETL tasks and we implement these new constructs in an ETL framework. The constructs are easy to apply and do only require few modifications to an ETL program to parallelize it. They support both task and data parallelism and give the programmer different possibilities to choose from. An experimental evaluation shows that by using a little more CPU time, the (wall-clock) time to run an ETL program can be greatly reduced.

Emerging trends in urban mobility have accelerated the need for effective traffic prediction and management systems. The present paper proposes a novel approach to using continuously streaming moving object trajectories for traffic prediction and management. The approach continuously performs three functions for streams of moving object positions in road networks: 1) management of current evolving trajectories, 2) incremental mining of closed frequent routes, and 3) prediction of near-future locations and densities based on 1) and 2). The approach is empirically evaluated on a large real-world data set of moving object trajectories, originating from a fleet of taxis, illustrating that detailed closed frequent routes can be efficiently discovered and used for prediction.

This paper describes the implementation of so-called sentinels in the TARGIT BI Suite. Sentinels are a novel type of rules that can warn a user if one or more measure changes in a multi-dimensional data cube are expected to cause a change to another measure critical to the user. Sentinels notify users based on previous observations, e.g., that revenue might drop within two months if an increase in customer problems combined with a decrease in website traffic is observed. In this paper we show how users, without any prior technical knowledge, can mine and use sentinels in the TARGIT BI Suite. We present in detail how sentinels are mined from data, and how sentinels are scored. We describe in detail how the sentinel mining algorithm is implemented in the TARGIT BI Suite, and show that our implementation is able to discover strong and useful sentinels that could not be found when using sequential pattern mining or correlation techniques. We demonstrate, through extensive experiments, that mining and usage of sentinels is feasible with good performance for the typical users on a real, operational data warehouse.

Compressed bitmap indexes are increasingly used for efficiently querying very large and complex databases. The Word Aligned Hybrid (WAH) bitmap compression scheme is commonly recognized as the most efficient compression scheme in terms of CPU efficiency. However, WAH compressed bitmaps use a lot of storage space. This paper presents the Position List Word Aligned Hybrid (PLWAH) compression scheme that improves significantly over WAH compression by better utilizing the available bits and new CPU instructions. For typical bit distributions, PLWAH compressed bitmaps are often half the size of WAH bitmaps and, at the same time, offer an even better CPU efficiency. The results are verified by theoretical estimates and extensive experiments on large amounts of both synthetic and real-world data.

This paper demonstrates so-called sentinels in the TARGIT BI Suite. Sentinels are a novel type of rules that can warn a user if one or more measure changes in a multi-dimensional data cube are expected to cause a change to another measure critical to the user. We present the concept of sentinels, and we explain how sentinels represent stronger and more specific rules than sequential patterns and correlation techniques. In addition, we present the algorithm, implementation, and data warehouse setup that are prerequisites for our demo. In the demo we present a dialogue where users, without any prior technical knowledge, are able to select a critical measure, a number of cubes, and a time dimension, and subsequently mine and schedule sentinels for early warnings .

Extract-Transform-Load (ETL) processes are used for extracting data, transforming it and loading it into data warehouses (DWs). Many tools for creating ETL processes exist. The dominating tools all use graphical user interfaces (GUIs) where the developer visually defines the data flow and operations. In this paper, we challenge this approach and propose to do ETL programming by writing code. To make the programming easy, we present the (Python-based) framework pygrametl which offers commonly used functionality for ETL development. By using the framework, the developer can efficiently create effective ETL solutions from which the full power of programming can be exploited. Our experiments show that when pygrametl is used, both the development time and running time are short when compared to an existing GUI-based tool.

Transportation-related problems, like road congestion, parking, and pollution, are increasing in most cities. In order to reduce traffic, recent work has proposed methods for vehicle sharing, for example for sharing cabs by grouping "closeby" cab requests and thus minimizing transportation cost and utilizing cab space. However, the methods published so far do not scale to large data volumes, which is necessary to facilitate large-scale collective transportation systems, e.g., ride-sharing systems for large cities. This paper presents highly scalable trip grouping algorithms, which generalize previous techniques and support input rates that can be orders of magnitude larger. The following three contributions make the grouping algorithms scalable. First, the basic grouping algorithm is expressed as a continuous stream query in a data stream management system to allow for a very large flow of requests. Second, following the divide-and-conquer paradigm, four space-partitioning policies for dividing the input data stream into sub-streams are developed and implemented using continuous stream queries. Third, using the partitioning policies, parallel implementations of the grouping algorithm in a parallel computing environment are described. Extensive experimental results show that the parallel implementation using simple adaptive partitioning methods can achieve speed-ups of several orders of magnitude without significantly degrading the quality of the grouping.

In order to provide context--aware Location--Based Services, real location data of mobile users must be collected and analyzed by spatio--temporal data mining methods. However, the data mining methods need precise location data, while the mobile users want to protect their location privacy. To remedy this situation, this paper first formally defines novel location privacy requirements. Then, it briefly presents a system for privacy--preserving trajectory collection that meets these requirements. The system is composed of an untrusted server and clients communicating in a P2P network. Location data is anonymized in the system using data cloaking and data swapping techniques. Finally, the paper empirically demonstrates that the proposed system is effective and feasible.

Data warehouses (DWs) have traditionally been loaded with data at regular time intervals, e.g., monthly, weekly, or daily, using fast bulk loading techniques. Recently, the trend is to insert all (or only some) new source data very quickly into DWs, called near-realtime DWs (right-time DWs). This is done using regular INSERT statements, resulting in too low insert speeds. There is thus a great need for a solution that makes inserted data available quickly, while still providing bulk-load insert speeds. This paper presents RiTE ("Right-Time ETL"), a middleware system that provides exactly that. A data producer (ETL) can insert data that becomes available to data consumers on demand. RiTE includes an innovative main-memory based catalyst that provides fast storage and offers concurrency control. A number of policies controlling the bulk movement of data based on user requirements for persistency, availability, freshness, etc. are supported. The system works transparently to both producer and consumers. The system is integrated with an open source DBMS, and experiments show that it provides "the best of both worlds", i.e., INSERT-like data availability, but with bulk-load speeds (up to 10 times faster).

This paper surveys the most relevant research on combining Data Warehouse (DW) and Web data. It studies the XML technologies that are currently being used to integrate, store, query and retrieve web data, and their application to DWs. The paper reviews different DW distributed architectures and the use of XML languages as an integration tool in these systems. It also introduces the problem of dealing with semi-structured data in a DW. It studies Web data repositories, the design of multidimensional databases for XML data sources and the XML extensions of On-Line Analytical Processing techniques. The paper addresses the application of information retrieval technology in a DW to exploit text-rich documents collections. The authors hope that the paper will help to discover the main limitations and opportunities that offer the combination of the DW and the Web fields, as well as, to identify open research lines.

Data warehouses (DWs) have become very successful in many enterprises, but only for relatively simple and traditional types of data. It is now time to extend the benefits of DWs to a much wider range of data, making it feasible to literally "warehouse the world". To do this, five unique challenges must be addressed: warehousing data about the physical world, integrating structured, semi-structured, and unstructured data in DWs, integrating the past, the present, and the future, warehousing imperfect data, and ensuring privacy in DW.

Current data warehouse and OLAP (Kimball and Ross, 2002) technologies can be efficiently applied to analyze the huge amounts of structured data that companies produce. These organizations also produce many text documents and use the Web as their largest source of external information. Although these documents include highly valuable information that should also be exploited by companies, they cannot be analyzed by current OLAP technologies because they are unstructured and mainly contain text. The current trend is to find these documents available in XML-like formats. Our proposal is to build XML document warehouses that can be used by companies to store unstructured information coming from their internal and external sources. In (Perez et al., 2005) we proposed an architecture for the integration of a corporate warehouse of structured data with a warehouse of text-rich XML documents. We call the resulting warehouse a contextualized warehouse. Since the XML document warehouse may contain documents about many different topics, we apply well-known information retrieval (IR) (Baeza-Yates and Ribeiro-Neto, 1999) techniques to select the context of analysis from the document warehouse. First, the user specifies an analysis context by supplying a sequence of keywords (e.g., an IR condition like "financial crisis"). Then, the analysis is performed on a so-called R-cube (Relevance cube), which is materialized by retrieving the documents and facts related to the selected context. Each fact in the R-cube will be linked to the set of documents that describe its context, and will have assigned a numerical value representing its relevance with respect to the specified context (e.g., how important the fact is for a "financial crisis"). In (Perez et al., 2005) we provided R-cubes with a data model and an algebra. This paper presents a prototype R-cube system, and explains how to use it.

The popularity of embedded positioning technologies in mobile devices and the development of mobile communication technology have paved the way for powerful location-based services (LBSs). To make LBSs useful and user- friendly, heavy use is made of context information, including patterns in user location data which are extracted by data mining methods. However, there is a potential conflict of interest: the data mining methods want as precise data as possible, while the users want to protect their privacy by not disclosing their exact movements. This paper aims to resolve this conflict by proposing a general framework that allows user location data to be anonymized, thus preserving privacy, while still allowing interesting patterns to be discovered. The framework allows users to specify individual desired levels of privacy that the data collection and mining system will then meet. Privacy-preserving methods are proposed for a core data mining task, namely finding dense spatio-temporal regions. An extensive set of experiments evaluate the methods, comparing them to their non- privacy-preserving equivalents. The experiments show that the framework still allows most patterns to be found, even when privacy is preserved.

As more and more information is available on the web, it is a problem that many web resources are not accessible, i.e., are not usable for users with special needs. For example, for a web page to be accessible, it should give text alternatives (i.e., explanatory texts) for images such that blind users that have the web pages read aloud automatically also can obtain information about the images. In the European Internet Accessibility Observatory (EIAO) project, a crawler that will evaluate the accessibility of thousands of European web sites is built. The crawler frequently performs many tests of the web sites and thus very large amounts of accessibility data are generated. Based on open-source software, a data warehouse (DW) called EIAO DW is built to make analysis of the complex accessibility data easy, reliable and fast. The EIAO DW is, thus, a data warehouse which measures properties of the web or, in other words, a web warehouse. It is believed that this work is the first to address the application of business intelligence (BI) techniques to the complex field of accessibility in a general and scalable way. This paper describes how the EIAO DW is designed and built. The paper introduces accessibility and the EIAO project to give a background for the design of EIAO DW. Then, the conceptual, logical and physical models are presented. The paper also gives descriptions of the complex Resource Description Framework (RDF) source data and complex accessibility aggregation functions supported by EIAO DW.

Motivated by the increasing need to analyze complex, uncertain multidimensional data this paper proposes probabilistic OLAP queries that are computed using probability distributions rather than atomic values. The paper describes how to create probability distributions from base data, and how the distributions can be subsequently used in pre-aggregation. Since the probability distributions can become large, we show how to achieve good time and space efficiency by approximating the distributions. We present the results of several experiments that demonstrate the effectiveness of our methods. The work is motivatedwith a real-world case study, based on our collaboration with a leading Danish vendor of location-based services. This paper is the first to consider the approximate processing of probabilistic OLAP queries over probability distributions.

Creating complex spatio-temporal simulation models is a hot issue in the area of spatio-temporal databases [7]. While existing Moving Object Simulators (MOSs)address different physical aspects of mobility, they neglect the important social and geo-demographical aspects of it. This paper presents ST-ACTS, a Spatio-Temporal ACTivity Simulator that, using various geo-statistical data sources and intuitive principles, models the so far neglected aspects. ST-ACTS considers that (1)objects (representing mobile users)move from one spatio-temporal location to another with the objective of performing a certain activity at the latter location; (2)not all users are equally likely to perform a given activity; (3)certain activities are performed at certain locations and times; and (4)activities exhibit regularities that can be specific to a single user or to groups of users. Experimental results show that ST-ACTS is able to effectively generate realistic spatio-temporal distributions of activities, which make it essential for the development of adequate spatio-temporal data management and data mining techniques.

In today’s OLAP systems, physically integrating fast-changing data (e.g., stock quotes) into a cube is complex and time-consuming. The data is likely to be available in XML format on the World Wide Web (WWW); thus, instead of physical integration, making XML data logically federated with OLAP systems is desirable. In this article, we extend previous work on the logical federation of OLAP and XML data sources by presenting simplified query semantics, a physical query algebra, and a robust OLAP-XML query engine, as well as the query evaluation techniques. Performance experiments with a prototypical implementation suggest that the performance for OLAP-XML federations is comparable to queries on physically integrated data.

Current data warehouse and OLAP technologies can be applied to analyze the structured data that companies store in their databases. The circumstances that describe the context associated with these data can be found in other internal and external sources of documents. In this paper we propose to combine the traditional corporate data warehouse with a document warehouse, resulting in a contextualized warehouse. Thus, contextualized warehouses keep a historical record of the fact and their contexts as described by the documents. In this framework, the user selects an analysis context which is represented as a novel type of OLAP cube, here called R-cube. R-cubes are characterized by two special dimensions, namely: the relevance and the context dimensions. The first dimension measures the relevance of each fact in the selected analysis context, whereas the second one relates each fact with the documents that explain their circumstances. In this work we extend an existing multi-dimensional data model and algebra for representing the R-cubes.

In modern enterprises, almost all data is stored in relational databases. Additionally, most enterprises increasingly collaborate with other enterprises in long-running read-write workflows, primarily through XML-based data exchange technologies such as Web services. However, bidirectional XML data exchange is cumbersome and must often be hand-coded, at considerable expense. This paper remedies the situation by proposing RELAXML, an automatic and effective approach to bidirectional XML-based exchange of relational data. RELAXML supports re-use through multiple inheritance, and handles both export of relational data to XML documents and (re-)import of XML documents with a large degree of flexibility in terms of the SQL statements and XML document structures supported. Import and export are formally defined so as to avoid semantic problems, and algorithms to implement both are given. A performance study shows that the approach has a reasonable overhead compared to hand-coded programs.

In today's OLAP systems, integrating fast changing data, e.g., stock quotes, physically into a cube is complex and time consuming. The widespread use of XML makes it very possible that this data is available in XML format on the WWW. Thus, making XML data logically federated with OLAP systems is desirable. In this paper, we extend previous work on the logical federation of OLAP and XML data sources by presenting a simplified query semantics, a physical query algebra and a robust OLAP-XML query engine. Performance experiments with a prototypical implementation suggest that the performance for OLAP-XML federations is comparable to queries on physically integrated data.

We present work on logical integration of OLAP and XML data sources, carried out in cooperation between TARGIT, a Danish OLAP client vendor, and Aalborg University. A prototype has been developed that allows XML data on the WWW to be used as dimensions and measures in the OLAP system in the same way as ordinary dimensions and measures, providing a powerful and flexible way to handle unexpected or short-term data requirements as well as rapidly changing data. Compared to earlier work, we present several major extensions that resulted from TARGIT's requirements. These include the ability to use XML data as measures, as well as a novel multigranular data model and query language that formalizes and extends the TARGIT data model and query language.

Motivated by the need for more flexible OLAP systems, this paper presents work on logical integration of external data in OLAP databases, carried out in cooperation between the Danish OLAP client vendor targit and Aalborg University. Flexibility is ensured by supporting XML as the external data format, since almost all data sources can be efficiently wrapped in XML. Earlier work has resulted in an extension of the targit system, allowing external XML data to be used as dimensions and measures in OLAP databases. This work has led to a number of new idea for improving the system's ability to adapt to changes in its surroundings.This paper describes the potential problems that may interrupt the operation of the integration system, in particular those caused by the often autonomous and unreliable nature of external XML data sources, and methods for handling these problems. Specifically, we describe techniques for handling changes in external XML data sources. We also describe techniques for improving the reliability of external XML sources, e.g., when these are found on the Internet, by dynamically trying to locate alternative sources during the evaluation of a query. Finally, we discuss solutions to a number of other possible problems, and show how the techniques can be integrated in the targit architecture. Experiments performed with a prototype implementation of central functionality shows the viability of the proposed solutions.

With wireless communications and geo-positioning being widely available, it becomes possible to offer new e-services that provide mobile users with information about other mobile objects. This paper concerns active, ordered k-nearest neighbor queries for query and data objects that are moving in road networks. Such queries may be of use in many services.Specifically, we present an easily implementable data model that serves well as a foundation for such queries. We also present the design of a prototype system that implements the queries based on the data model. The algorithm used for the nearest neighbor search in the prototype is presented in detail. In addition, the paper reports on results from experiments with the prototype system.

The changing data requirements of today's dynamic business environments are not handled well by current OLAP systems. Physically integrating unexpected data into such systems is a long and time-consuming process making logical integration, i.e., federation, the better choice in many situations. The increasing use of Extended Markup Language (XML), e.g. in business-to-business (B2B) applications, suggests that the required data will often be available as XML data. This means that logical federations of OLAP and XML databases will be very attractive in many cases. However, for such OLAP-XML federations to be useful, effective optimization techniques for such systems are needed.In this paper we present novel techniques for query optimization in federations of OLAP and XML databases. The techniques include so-called inlining of XML data in OLAP predicates, caching, and pre-fetching. Experiments show that the proposed optimization techniques improve query execution times significantly. Furthermore, the performance of the optimized federation queries is comparable to the performance achieved with physical integration of the data, showing that our federated OLAP approach is indeed a feasible alternative to physical integration.

Presents a powerful and easy-to-use technique for aggregation-based data reduction that enables the gradual change of the data from being detailed to being increasingly aggregated. The technique enables huge storage gains while retaining the data that is essential to the users, and it preserves the ability to query original and reduced data in an integrated manner.

The rapidly changing data requirements of today's dynamic business environments are not handled well by current online analytical processing (OLAP) systems. Physically integrating data from new sources into OLAP systems is a long and time-consuming process, making logical integration the better choice in many situations. The increasing use of Extended Markup Language (XML) suggests that the required external data will most often be available in XML format. We present a theoretically well-founded approach to the logical federation of OLAP and XML data sources. The approach allows external XML data to be presented along with dimensional data in OLAP query results and enables the use of external XML data for selection and grouping. Special care is taken to ensure that semantic problems do not occur in the integration process. This opens up many new application areas for OLAP. A number of effective optimization techniques for OLAP-XML federations are presented. Performance results from the prototype implementation show that the approach is an attractive alternative to physical integration. The approach is exemplified using a real-world case study from the B2B domain.

On-Line Analytical Processing (OLAP) enables analysts to gain insight into data through fast and interactive access to a variety of possible views on information, organized in a dimensional model. The demand for data integration is rapidly becoming larger as more and more information sources appear in modern enterprises. In the data warehousing approach, selected information is extracted in advance and stored in a repository. This approach is used because of its high performance. However, in many situations a logical (rather than physical) integration of data is preferable. Previous Web-based data integration efforts have focused almost exclusively on the logical level of data models, creating a need for techniques focused on the conceptual level. Also, previous integration techniques for Web-based data have not addressed the special needs of OLAP tools such as handling dimensions with hierarchies. Extensible Markup Language (XML) is fast becoming the new standard for data representation and exchange on the World Wide Web. The rapid emergence of XML data on the Web, e.g., business-to-business (B2B) e-commerce, is making it necessary for OLAP and other data analysis tools to handle XML data as well as traditional data formats. Based on a real-world case study, the paper presents an approach to the conceptual specification of OLAP DBs based on Web data. Unlike previous work, this approach takes special OLAP issues such as dimension hierarchies and correct aggregation of data into account. Additionally, an integration architecture that allows the logical integration of XML and relational data sources for use by OLAP tools is presented.

On-Line Analytical Processing (OLAP) systems based on a multidimensional view of data have found widespread use in business applications and are being used increasingly in non-standard applications.These systems provide good performance and ease-of-use.However, the complex structures and relationships inherent in data in non-standard applications are not accommodated well by OLAP systems.In contrast, object database systems are built to handle such complexity, but do not support OLAP-type querying well.This paper presents the concepts and techniques underlying a flexible, "multi-model" federated system that enables OLAP users to exploit simultaneously the features of OLAP and object database systems.The system allows data to be handled using the most appropriate data model and technology: OLAP systems for multidimensional data and object database systems for more complex, general data.Additionally, physical data integration can be avoided.As a vehicle for demonstrating the capabilities of the system, a prototypical OLAP language is defined and extended to naturally support queries that involve data in object databases.The language permits selection criteria that reference object data, queries that return combinations of OLAP and object data, and queries that group multidimensional data according to object data.The system is designed to be aggregation-safe, in the sense that it exploits the aggregation semantics of the data to prevent incorrect or meaningless query results.A prototype implementation of the system is reported.

Analyzing data obtained from web server logs, so-called "clickstreams", is rapidly becoming one of the most important activities for companies in any sector as most businesses become ebusinesses.Clickstream analysis can reveal usage patterns on the company's web site and give a highly improved understanding of customer behavior.This understanding can then be utilized for improving customer satisfaction with the web site and the company in general, yielding a huge business advantage.In this paper, we present the results of a clickstream analysis project at a large Danish mortgage provider.The paper first describes clickstream data and its usefulness, then it introduces the questions that the company wanted answered in the project.One of the major problems in clickstream analysis is sequences of clicks, which are difficult to handle using normal techniques.This problem is handled by introducing the concept of subsessions, which captures sequences of clicks explicitly.Techniques for overcoming the potential explosion in the number of subsessions and for filtering out unnecessary web requests are presented and the effectiveness of the techniques is evaluated.The proposed approach has been successfully implemented and tested and is currently being integrated in the company's web system architecture.

Online Analytical Processing (OLAP) systems considerably ease the process of analyzing business data and have become widely used in industry. Such systems primarily employ multidimensional data models to structure their data. However current multidimensional data models fall short in their abilities to model the complex data found in some real world application domains. The paper presents nine requirements to multidimensional data models, each of which is exemplified by a real world, clinical case study. A survey of the existing models reveals that the requirements not currently met include support for many-to-many relationships between facts and dimensions, built-in support for handling chance and time, and support for uncertainty as well as different levels of granularity in the data. The paper defines an extended multidimensional data model, and an associated algebra, which address all nine requirements.

Online analytical processing (OLAP) technologies are being used widely, but the lack of effective means of handling data imprecision, which occurs when exact values are not known precisely or are entirely missing, represents a major obstacle in applying these technologies in many domains. The paper develops techniques for handling imprecision that aim to maximally reuse existing OLAP modeling constructs such as dimension hierarchies and granularities. With imprecise data available in the database, queries are tested to determine whether or not they may be answered precisely given the available data; if not, alternative queries unaffected by the imprecision are suggested. When processing queries affected by imprecision, techniques are proposed that take into account the imprecision in the grouping of the data, in the subsequent aggregate computation, and in the presentation of the imprecise result to the user. The approach is capable of exploiting existing OLAP query processing techniques such as pre-aggregation, yielding an effective approach with low computational overhead and that may be implemented using current technology.

Medical informatics has been an important area for the application of computing and database technology for at least four decades. This area may benefit from the functionality offered by data warehousing. However, the special nature of clinical applications poses different and new requirements to data warehousing technologies, over those posed by conventional data warehouse applications. This article presents a number of exciting new research challenges posed by clinical applications, to be met by the database research community. These include the need for complex data modeling features, advanced temporal support, advanced classification structures, continuously valued data, dimensionally reduced data, and the integration of very complex data. In addition, the support for clinical treatment protocols and medical research are interesting areas for research.