Log anomaly detection is crucial for uncovering system failures and security risks. Although logs originate from nested component executions with clear boundaries, this structure is lost when stored as flat sequences. As a result, state-of-the-art methods often miss true dependencies within executions while learning spurious correlations across unrelated events. We propose KRONE, the first hierarchical anomaly detection framework that automatically derives execution hierarchies from flat logs to enable modular, multi-level anomaly detection. At its core, the KRONE Log Abstraction Model extracts application-specific semantic hierarchies, which are used to recursively decompose log sequences into coherent execution units, referred to as KRONE Seqs. This transforms sequence-level detection into a set of modular KRONE Seq-level detection tasks. For each test KRONE Seq, KRONE adopts a hybrid modular detection strategy that routes between an efficient level-independent Local-Context detector for rapid filtering and a Nested-Aware detector that captures cross-level semantic dependencies, augmented with LLM-based anomaly detection and explanation. KRONE further optimizes detection through cached result reuse and early-exit strategies along the hierarchy. Experiments on three public benchmarks and one industrial dataset from ByteDance Cloud demonstrate that KRONE achieves substantial improvements in accuracy (42.49% to 87.98%), F1 score, data efficiency (117.3x reduction), resource efficiency (43.7x reduction), and interpretability. KRONE improves F1-score by 10.07% (82.76% to 92.83%) over prior methods while reducing LLM usage to only 1.1% to 3.3% of the test data. Code: https://github.com/LeiMa0324/KRONE Demo: https://leima0324.github.io/KRONE_Demo_official/

Learning with noisy labels (LNL) is essential for training deep neural networks with imperfect data. Meta-learning approaches have achieved success by using a clean unbiased labeled set to train a robust model. However, this approach heavily depends on the availability of a clean labeled meta-dataset, which is difficult to obtain in practice. In this work, we thus tackle the challenge of meta-learning for noisy label scenarios without relying on a clean labeled dataset. Our approach leverages the data itself while bypassing the need for labels. Building on the insight that clean samples effectively preserve the consistency of related data structures across the last hidden and the final layer, whereas noisy samples disrupt this consistency, we design the Cross-layer Information Divergence-based Meta Update Strategy (CLID-MU). CLID-MU leverages the alignment of data structures across these diverse feature spaces to evaluate model performance and use this alignment to guide training. Experiments on benchmark datasets with varying amounts of labels under both synthetic and real-world noise demonstrate that CLID-MU outperforms state-of-the-art methods. The code is released at https://github.com/ruofanhu/CLID-MU.

Due to the scarcity of reliable anomaly labels, recent anomaly detection methods leveraging noisy auto-generated labels either select clean samples or refurbish noisy labels. However, both approaches struggle due to the unique properties of anomalies. Sample selection often fails to separate sufficiently many clean anomaly samples from noisy ones, while label refurbishment erroneously refurbishes marginal clean samples. To overcome these limitations, we design Unity, the first learning from noisy labels (LNL) approach for anomaly detection that elegantly leverages the merits of both sample selection and label refurbishment to iteratively prepare a diverse clean sample set for network training. Unity uses a pair of deep anomaly networks to collaboratively select samples with clean labels based on prediction agreement, followed by a disagreement resolution mechanism to capture marginal samples with clean labels. Thereafter, Unity utilizes unique properties of anomalies to design an anomaly-centric contrastive learning strategy that accurately refurbishes the remaining noisy labels. The resulting set, composed of selected and refurbished clean samples, will be used to train the anomaly networks in the next training round. Our experimental study on 10 real-world benchmark datasets demonstrates that Unity consistently outperforms state-of-the-art LNL techniques by up to 0.31 in F-1 Score (0.52 \rightarrow 0.83).

Generative Adversarial Networks (GANs) are a generative framework with a notorious reputation for instability. Despite significant work in attempting to improve stability, training remains extremely difficult in practice. Nearly all GAN optimization methods are built on either simultaneous (Sim-GDA) or alternating (Alt-GDA) gradient descent-ascent, where the generator and discriminator are updated either at the same time iteratively or in a fixed pattern. Unfortunately, neither Sim-GDA nor Alt-GDA have any strongly convergent properties, nor are they Lyapunov-stable. In this paper, we prove for simple GANs, for which training had been proven non-convergent under Sim-GDA and Alt-GDA, that our newly introduced training method is Lyapunov-stable. We then design a novel oracle-guided GDA training strategy called Dynamic-GDA that leverages generalized analogs of the properties exhibited in the simple case. We also prove that in contrast to Sim/Alt-GDA, GANs with Dynamic-GDA achieve Lyapunov-stable training with non-infinitesimal learning rates. Empirically, we show Dynamic-GDA improves convergence orthogonally to common stabilizing techniques on 8 classes of GAN models and 7 different data sets.

The pressures faced by college students frequently lead to heightened levels of stress. Wearable devices, which collect sensor data in a non-intrusive manner, present an opportunity for early detection of stress. Nonetheless, there is a lack of diversity in current research concerning psychological assessments, physiological metrics, and time series features. In this work, we utilize a Fitbit dataset and evaluate its use in predicting stress through machine learning. Our results demonstrate that physiological data such as calories burned and sleep hold promise for stress screening, with F1 scores reaching up to 0.81. These findings illustrate the potential of wearable technology for continuous stress monitoring and emphasize the need for selecting appropriate data aggregation levels and physiological modalities for effective screening.

Major depressive disorder (MDD) and post-traumatic stress disorder (PTSD) are mental disorders that reduce quality of life. As they are challenging to detect in a timely manner, recent studies explore the mental illness screening potential of language models on modalities such as transcripts. Such datasets suffer from a limited number of participants. To overcome these challenges, we take a two-pronged approach: (1) we leverage multi-task learning to model multiple illnesses concurrently namely MDD and PTSD screening, and (2) we plug in pre-trained language models as a backbone, namely, Bidirectional Encoder Representations from Transformers (BERT) variants – which are capable of learning the linguistic content of clinical interview transcripts. In particular, we experiment with three multi-task weighting strategies and five BERT variants, applying them to 15 transcript sets extracted from the Distress Analysis Interview Corpus. Our results indicate that leveraging multi-task learning, especially with meta-weighting, increases the screening performance compared to single-task learning. Our multi-task learning model strategies improved the F1 scores for all 15 datasets for both MDD and PTSD screening. Notably, multitask learning improved MDD screening ability by 20 percent with transcripts regarding ‘regret’ and achieved F1 of 0.89 and 0.82 respectively for MDD and PTSD screening with transcripts regarding ‘medical history’. Our findings may help researchers develop more effective mental illness screening models.

Foodborne illnesses pose a threat to public health, leading to morbidity, mortality, and economic burden annually. Social media, while providing a rich timely source for training AI models for surveillance, requires effective tools for annotation. While Large Language Models (LLMs) have shown promise for generating simple labels, here hierarchical labels composed of entity types like food type and symptom (at individual word level) and the foodborne illness event (at complete post level) are required. For this, we introduce ICL2FID, the first LLM-based hierarchical labeling framework designed to annotate social media posts for foodborne illness detection at two levels using only a few demonstration examples. To utilize the interconnection between post and word levels, ICL2FID instructs the LLM to leverage information from one level when predicting the other level. To combat model hallucination and cyclic dependencies, a verification step improves evidence propagation between interconnected word and post-level labeling tasks. Strategies for custom selection of demonstration examples are designed reducing biases and increasing representation. We compare ICL2FID against traditional supervised learning and other LLM methods, demonstrating that it not only achieves superior accuracy but does so at a fraction of the cost and time. These findings highlight ICL2FID’s potential as a viable alternative for hierarchical label generation in scenarios with limited resources and huge data sets. Code is available at https://github.com/zdy93/ICL2FID.

We present FairRankTune, a multi-purpose open-source Python toolkit offering three primary services: quantifying fairness-related harms, leveraging bias mitigation algorithms, and constructing custom fairness-relevant datasets. FairRankTune provides researchers and practitioners with a self-contained resource for fairness auditing, experimentation, and advancing research. The central piece of FairRankTune is a novel fairness-tunable ranked data generator, RankTune, that streamlines the creation of custom fairness-relevant ranked datasets. FairRankTune also offers numerous fair ranking metrics and fairness-aware ranking algorithms within the same plug-and-play package. We demonstrate the key innovations of FairRankTune, focusing on features that are valuable to stakeholders via use cases highlighting workflows in the end-to-end process of mitigating bias in ranking systems. FairRankTune addresses the gap of limited publicly available datasets, auditing tools, and implementations for fair ranking.

The terabyte-scale of data series has motivated recent efforts to design fully distributed techniques for supporting operations such as approximate kNN similarity search, which is a building block operation in most analytics services on data series. Unfortunately, these techniques are heavily geared towards achieving scalability at the cost of sacrificing the results' accuracy. State-of-the-art systems DPiSAX and TARDIS report accuracy below 10% and 40%, respectively, which is not practical for many real-world applications. In this paper, we investigate the root problems in these existing techniques that limit their ability to achieve better a trade-off between scalability and accuracy. Then, we propose a framework, called CLIMBER, that encompasses a novel feature extraction mechanism, indexing scheme, and query processing algorithms for supporting approximate similarity search in big data series. For CLIMBER, we propose a new loss-resistant dual representation composed of rank-sensitive and ranking-insensitive signatures capturing data series objects. Based on this representation, we devise a distributed two-level index structure supported by an efficient data partitioning scheme. Our similarity metrics tailored for this dual representation enables meaningful comparison and distance evaluation between the rank-sensitive and ranking-insensitive signatures. Finally, we propose two efficient query processing algorithms, CLIMBER-kNN and CLIMBER-kNN-Adaptive, for answering approximate kNN similarity queries. Our experimental study on real-world and benchmark datasets demonstrates that CLIMBER, unlike existing techniques, features results' accuracy above 80% while retaining the desired scalability to terabytes of data.

Deep neural networks (DNNs) have advanced many machine learning tasks, but their performance is often harmed by noisy labels in real-world data. Addressing this, we introduce CoLafier, a novel approach that uses Local Intrinsic Dimensionality (LID) for learning with noisy labels. CoLafier consists of two subnets: LID-dis and LID-gen. LID-dis is a specialized classifier. Trained with our uniquely crafted scheme, LID-dis consumes both a sample's features and its label to predict the label - which allows it to produce an enhanced internal representation. We observe that LID scores computed from this representation that effectively distinguish between correct and incorrect labels across various noise scenarios. In contrast to LID-dis, LID-gen, functioning as a regular classifier, operates solely on the sample's features. During training, CoLafier utilizes two augmented views per instance to feed both subnets. CoLafier considers the LID scores from the two views as produced by LID-dis to assign weights in an adapted loss function for both subnets. Concurrently, LID-gen, serving as classifier, suggests pseudo-labels. LID-dis then processes these pseudo-labels along with two views to derive LID scores. Finally, these LID scores along with the differences in predictions from the two subnets guide the label update decisions. This dual-view and dual-subnet approach enhances the overall reliability of the framework. Upon completion of the training, we deploy the LID-gen subnet of CoLafier as the final classification model. CoLafier demonstrates improved prediction accuracy, surpassing existing methods, particularly under severe label noise. For more details, see the code at https://github.com/zdy93/CoLafier.

Log anomaly detection, critical in identifying system failures and preempting security breaches, finds irregular patterns within large volumes of log data. Modern log anomaly detectors rely on training deep learning models on clean anomaly-free log data. However, such clean log data requires expensive and tedious human labeling. In this paper, we thus propose a robust log anomaly detection framework, PlutoNOSPACE, that automatically selects a clean representative sample subset of the polluted log sequence data to train a Transformer-based anomaly detection model. Pluto features three innovations. First, due to localized concentrations of anomalies inherent in the embedding space of log data, Pluto partitions the sequence embedding space generated by the model into regions that then allow it to identify and discard regions that are highly polluted by our pollution level estimation scheme, based on our pollution quantification via Gaussian mixture modeling. Second, for the remaining more slightly polluted regions, we select samples that maximally purify the eigenvector spectrum, which can be transformed into the NP-hard facility location problem; allowing us to leverage its greedy solution with a (1-(1/e)) approximation guarantee in optimality. Third, by iteratively alternating between the above subset selection, a model re-training on the latest subset, and a subset filtering using dynamic training artifacts generated by the latest model, the data selected is progressively refined. The final sample set is used to retrain the final anomaly detection model. Our experiments on four real-world log benchmark datasets demonstrate that by retaining 77.7% (BGL) to 96.6% (ThunderBird) of the normal sequences while effectively removing 90.3% (BGL) to 100.0% (ThunderBird, HDFS) of the anomalies, Pluto provides a significant absolute F-1 improvement up to 68.86% (2.16% → 71.02%) compared to the state-of-the-art sample selection methods. The implementation of this work is available at https://github.com/LeiMa0324/Pluto-SIGMOD25.

Machine learning is routinely used to automate consequential decisions about users in domains such as finance and healthcare, raising concerns of transparency and recourse for negative outcomes. Existing Explainable AI techniques generate a static counterfactual point explanation which recommends changes to a user's instance to obtain a positive outcome. Unfortunately, these recommendations are often difficult or impossible for users to realistically enact. To overcome this, we present FACET, the first interactive robust explanation system which generates personalized counterfactual region explanations. FACET's expressive explanation analytics empower users to explore and compare multiple counterfactual options and develop a personalized actionable plan for obtaining their desired outcome. Visitors to the demonstration will interact with FACET via a new web dashboard for explanations of a loan approval scenario. In doing so, visitors will experience how lay users can easily leverage powerful explanation analytics through visual interactions and displays without the need for a strong technical background.

The process of training deep learning models produces a huge amount of meta-data, including but not limited to losses, hidden feature embeddings, and gradients. Model diagnosis tools have been developed to analyze losses and feature embeddings with the aim to improve the performance of these models. However, gradients, despite carrying rich information that is potentially relevant for model interpretation and data debugging, have yet to be fully explored due to their size and complexity. Each single gradient has a size as large as the number of parameters of the neural net - often measured in the tens of millions. This makes it extremely challenging to efficiently collect, store, and analyze large numbers of gradients in these models. In this work, we develop MetaStore to fill this gap. MetaStore leverages our observation that storing certain compact intermediate results produced in the back propagation process, namely, the prefix and suffix gradients, is sufficient for the exact restoration of the original gradient. These prefix and suffix gradients are much more compact than the original gradients, thus allowing us to address the gradient collection and storage challenges. Furthermore, MetaStore features a rich set of analytics operators that allow the users to analyze the gradients for data debugging or model interpretation. Rather than first having to restore the original gradients and then run analytics on top of this decompressed view, MetaStore directly executes these operators on the compact prefix and suffix structures, making gradient-based analytics efficient and scalable. Our experiments on popular deep learning models such as VGG, BERT, and ResNet and benchmark image and text datasets demonstrate that MetaStore outperforms strong baseline methods from 4 to 678x in storage costs and from 2 to 1000x in running time.

Depression is a prevalent mental health condition with severe impacts on physical and social health. It is costly and difficult to detect, requiring substantial time from trained mental professionals. To alleviate this burden, recent research explores the diagnostic capabilities of deep learning models trained on modalities extracted from videos of clinical interviews for depression screening. However, training deep learning models is challenging because in the mental health domain datasets contain a small number of patients. To address this challenge, we propose DeepScreen, a recurrent deep-learning architecture for depression screening whose performance is boosted by deploying a self-supervised auxiliary task for selective missing value imputation. DeepScreen leverages a multi-task architecture with a bidirectional recurrent deep learning model and a self-attention mechanism, jointly optimizing the supervised depression and the self-supervised auxiliary task. Our first study assesses the capability of the auxiliary task training of DeepScreen under different correlation levels and masking sub-sequence sizes of multi-variate time series. Found to be effective, our second study evaluates DeepScreen on 15 data sets composed of real-world temporal facial landmark features extracted from responses to different clinical interview questions. The results achieved across all 15 datasets demonstrate that the imputation task boosts the depression prediction metrics significantly. Specifically, DeepScreen improves the F1 score for one of the datasets by 57%. Further, our best-performing model achieves an F1 score of 0.85. This work provides valuable insights into improving deep learning driven mental screening applications by leveraging auxiliary tasks such as imputation for learning a better representation even from small datasets.

Major depressive disorder (MDD) and post-traumatic stress disorder (PTSD) are prevalent mental health conditions with severe physical and social impacts. They are expensive and detection is difficult, requiring substantial time from trained mental professionals. To alleviate this issue, recent studies explore the diagnostic potential of deep learning models trained on modalities extracted from clinical interview videos, conducted by a virtual agent. However, deep learning models are challenging to train because of the long sequences and small number of participants common in the mental health community. To combat these challenges, we leverage multi-task learning, using temporal facial features as input, to screen for MDD and PTSD. The multi-task architecture is based on a bidirectional GRU model with self-attention. We evaluate our multi-task model on temporal facial features extracted from responses to 15 clinical interview questions conducted by a virtual agent. The results suggest that multi-task learning increases the generalization performance compared to single-task learning. For MDD screening, multi-task learning improved the balanced accuracy over single-task learning for 11 of the 15 datasets. In fact, our multi-learning model increased the MDD screening ability by 25 percent to a balanced accuracy of 0.87 in some scenarios. This work provides valuable findings for the future of mental screening applications leveraging temporal facial features.

Generative modeling is a powerful technique that involves creating machine learning models capable of creating new data similar to the data it was trained on. Generative Adversarial Networks (GANs) are a leading approach for generative modeling. However, GAN training is known to be a notoriously difficult task. GAN convergence issues are largely caused by the supports of the real and generated distributions being disjoint. To tackle this open problem, we propose a novel GAN pre-training process that effectively aligns the supports of the generated and real data prior to applying traditional adversarial GAN training. The key component of our method, called AlignGAN, is learning a mapping between the input data distribution and a latent representation defined over a hypersphere, regularized by a One Class Classifier. This successfully encourages the generator to produce samples throughout the support of the real data, while not generating samples outside the support. We maintain support alignment through low-bandwidth noise convolutions and additional One Class regularization, leading to continued stable GAN training. We validate our approach against leading stabilization methods on three benchmark datasets, showing AlignGAN routinely produces the best results.

Foodborne illnesses significantly impact public health. Deep learning surveillance applications using social media data aim to detect early warning signals. However, labeling foodborne illness-related tweets for model training requires extensive human resources, making it challenging to collect a sufficient number of high-quality labels for tweets within a limited budget. The severe class imbalance resulting from the scarcity of foodborne illness-related tweets among the vast volume of social media further exacerbates the problem. Classifiers trained on a classimbalanced dataset are biased towards the majority class, making accurate detection difficult. To overcome these challenges, we propose EGAL, a deep learning framework for foodborne illness detection that uses small expert-labeled tweets augmented by crowdsourced-labeled and massive unlabeled data. Specifically, by leveraging tweets labeled by experts as a reward set, EGAL learns to assign a weight of zero to incorrectly labeled tweets to mitigate their negative influence. Other tweets receive proportionate weights to counter-balance the unbalanced class distribution. Extensive experiments on real-world TWEET-FID data show that EGAL outperforms strong baseline models across different settings, including varying expert-labeled set sizes and class imbalance ratios. A case study on a multistate outbreak of Salmonella Typhimurium infection linked to packaged salad greens demonstrates how the trained model captures relevant tweets offering valuable outbreak insights. EGAL, funded by the U.S. Department of Agriculture (USDA), has the potential to be deployed for real-time analysis of tweet streaming, contributing to foodborne illness outbreak surveillance efforts.

Traditional multi-criteria selection methods are the leading approach for selecting a set of candidates when multiple criteria determine selection relevancy. For instance, hiring platforms combine candidates' proximity, skills, and years of experience to build shortlists for recruiters. While these methods succeed in efficiently selecting candidates, their chosen set may unfairly affect marginalized candidate groups (e.g., race or gender). Bridging the gap between traditional fairness-unaware multi-criteria selection and contemporary fairness interventions, we characterize the open problem of fair multi-criteria selection. We design Fair&Share the first efficient fairness-tunable multi-criteria selection method. Fair&Share supports several fair representation notions. The key to Fair&Share is the design of its group-aware utility objective. Fair&Share uses a novel fairness calibration component to provide a user-friendly tuning mechanism for controlling the balance between selection relevancy (utility) and representation fairness. Our fairness-focused selection policy iteratively builds the result set by prioritizing candidates as aiding either the fair representation or the shared overall utility goals. We prove the optimality of Fair&Share, meaning that Fair&Share selects the best possible candidates such that the desired fair representation is achieved. Our experimental study demonstrates that Fair&Share achieves the best fairness and utility performance of state-of-the-art alternatives adapted to this new problem while taking a fraction of the time.

Amid corrosion degradation of metallic structures causing expenses nearing 3 trillion or 4% of the GDP annually along with major safety risks, the adoption of AI technologies for accelerating the materials science life-cycle for developing materials with better corrosive properties is paramount. While initial machine learning models for corrosion assessment are being proposed in the literature, their incorporation into end-to-end tools for field experimentation by corrosion scientists remains largely unexplored. To fill this void, our university data science team in collaboration with the materials science unit at the Army Research Lab have jointly developed MOSS, an innovative AI-based digital platform to support material science corrosion research. MOSS features user-friendly iPadOS app for in-field corrosion progression data collection, deep-learning corrosion assessor, robust data repository system for long-term experimental data modeling, and visual analytics web portal for material science research. In this demonstration, we showcase the key innovations of the MOSS platform via use cases supporting the corrosion exploration processes, with the promise of accelerating the discovery of new materials. We open a MOSS video demo at: https://www.youtube.com/watch?v=CzcxMMRsxkE

Outlier detection is critical in real world. Due to the existence of many outlier detection techniques which often return different results for the same data set, the users have to address the problem of determining which among these techniques is the best suited for their task and tune its parameters. This is particularly challenging in the unsupervised setting, where no labels are available for cross-validation needed for such method and parameter optimization. In this work, we propose AutoOD which uses the existing unsupervised detection techniques to automatically produce high quality outliers without any human tuning. AutoOD's fundamentally new strategy unifies the merits of unsupervised outlier detection and supervised classification within one integrated solution. It automatically tests a diverse set of unsupervised outlier detectors on a target data set, extracts useful signals from their combined detection results to reliably capture key differences between outliers and inliers. It then uses these signals to produce a "custom outlier classifier" to classify outliers, with its accuracy comparable to supervised outlier classification models trained with ground truth labels - without having access to the much needed labels. On a diverse set of benchmark outlier detection datasets, AutoOD consistently outperforms the best unsupervised outlier detector selected from hundreds of detectors. It also outperforms other tuning-free approaches from 12 to 97 points (out of 100) in the F-1 score.

Machine learning systems are deployed in domains such as hiring and healthcare, where undesired classifications can have serious ramifications for the user. Thus, there is a rising demand for explainable AI systems which provide actionable steps for lay users to obtain their desired outcome. To meet this need, we propose FACET, the first explanation analytics system which supports a user in interactively refining counterfactual explanations for decisions made by tree ensembles. As FACET's foundation, we design a novel type of counterfactual explanation called the counterfactual region. Unlike traditional counterfactuals, FACET's regions concisely describe portions of the feature space where the desired outcome is guaranteed, regardless of variations in exact feature values. This property, which we coin explanation robustness, is critical for the practical application of counterfactuals. We develop a rich set of novel explanation analytics queries which empower users to identify personalized counterfactual regions that account for their real-world circumstances. To process these queries, we develop a compact high-dimensional counterfactual region index along with index-aware query processing strategies for near real-time explanation analytics. We evaluate FACET against state-of-the-art explanation techniques on eight public benchmark datasets and demonstrate that FACET generates actionable explanations of similar quality in an order of magnitude less time while providing critical robustness guarantees. Finally, we conduct a preliminary user study which suggests that FACET's regions lead to higher user understanding than traditional counterfactuals.

Human activity recognition (HAR) is the process of using mobile sensor data to determine the physical activities performed by individuals. HAR is the backbone of many mobile healthcare applications, such as passive health monitoring systems, early diagnosing systems, and fall detection systems. Effective HAR models rely on deep learning architectures and big data in order to accurately classify activities. Unfortunately, HAR datasets are expensive to collect, are often mislabeled, and have large class imbalances. State-of-the-art approaches to address these challenges utilize Generative Adversarial Networks (GANs) for generating additional synthetic data along with their labels. Problematically, these HAR GANs only synthesize continuous features — features that are represented by real numbers — recorded from gyroscopes, accelerometers, and other sensors that produce continuous data. This is limiting since mobile sensor data commonly has discrete features that provide additional context such as device location and the time-of-day, which have been shown to substantially improve HAR classification. Hence, we studied Conditional Tabular Generative Adversarial Networks (CTGANs) for data generation to synthesize mobile sensor data containing both continuous and discrete features, a task never been done by state-of-the-art approaches. We show HAR-CTGANs generate data with greater realism resulting in allowing better downstream performance in HAR models, and when state-of-the-art models were modified with HAR-CTGAN characteristics, downstream performance also improves.

Deep learning often relies on the availability of a large amount of high-quality labeled data, which can be very limited in novel domains. To address such data scarcity, domain adaptation is one promising approach that allows for deep networks to leverage large amounts of available data from a source domain to enhance the model’s efficacy on the target domain of interest. However, while there is a plethora of alternate models for domain adaptation proposed over many years in the literature, there is a dearth of studies that objectively compare the relative effectiveness of these models in a rigorous, empirical study. To fill this gap, we provide a thorough, unbiased, empirical study of five state-of-the-art (SOTA) deep domain adaptation models proposed over the past 6 years whose codes are publicly available. Models are evaluated on the complex and diverse domain adaptation tasks featured in the DomainNet benchmark dataset as well as the popular Office-31 dataset. Our results suggest that (1) all 5 models perform similarly, on average, and do not even significantly beat the oldest model, and (2) counter to their intended purpose, the transfer loss functions in the literature do not contribute significantly to learning transferable representations. Our observations suggest that domain adaptation research needs to more thoroughly compare newly proposed models against existing works, along with assessing their loss functions’ utility thoroughly. Our code and data splits are made public for reproducibility of results by the community.

Corpuses of unstructured textual data, such as text messages between individuals, are often predictive of medical issues such as depression. The text data usually used in healthcare applications has high value and great variety, but is typically small in volume. Generating labeled unstructured text data is important to improve models by augmenting these small datasets, as well as to facilitate anonymization. While methods for labeled data generation exist, not all of them generalize well to small datasets. In this work, we thus perform a much needed systematic comparison of conditional text generation models that are promising for small datasets due to their unified architectures. We identify and implement a family of nine conditional sequence generative adversarial networks for text generation, which we collectively refer to as cSeqGAN models. These models are characterized along two orthogonal design dimensions: weighting strategies and feedback mechanisms. We conduct a comparative study evaluating the generation ability of the nine cSeqGAN models on three diverse text datasets with depression and sentiment labels. To assess the quality and realism of the generated text, we use standard machine learning metrics as well as human assessment via a user study. While the unconditioned models produced predictive text, the cSeqGAN models produced more realistic text. Our comparative study lays a solid foundation and provides important insights for further text generation research, particularly for the small datasets common within the healthcare domain.

Recurrent Classifier Chains (RCCs) are a leading approach for multi-label classification as they directly model the interdependencies between classes. Unfortunately, existing RCCs assume that every training instance is completely labeled with all its ground truth classes. In practice often only a subset of an instance's labels are annotated, while the annotations for other classes aremissing. RCCs fail in this missing label scenario, predicting many false negatives and potentially missing important classes. In this work, we propose Robust-RCC, the first strategy for tackling this open problem of RCCs failing formulti-label missing-label data. Robust-RCC is a new type of deep recurrent classifier chain empowered to model inter-class relationships essential for predicting thecomplete label set most likely to match the ground truth. The key to Robust-RCC is the design of the Multi Incomplete Label Risk (MILR) function, which we prove to be equal in expectation to the true risk of the ground truth full label set despite being computed from incompletely labeled data. Our experimental study demonstrates that Robust-RCC consistently beats six state-of-of-the-art methods by as much as 30% in predicting the true labels.

Early classification algorithms help users react faster to their machine learning model's predictions. Early warning systems in hospitals, for example, let clinicians improve their patients' outcomes by accurately predicting infections. While early classification systems are advancing rapidly, a major gap remains: existing systems do not consider irregular time series, which have uneven and often-long gaps between their observations. Such series are notoriously pervasive in impactful domains like healthcare. We bridge this gap and study early classification of irregular time series, a new setting for early classifiers that opens doors to more real-world problems. Our solution, Stop&Hop, uses a continuous-time recurrent network to model ongoing irregular time series in real time, while an irregularity-aware halting policy, trained with reinforcement learning, predicts when to stop and classify the streaming series. By taking real-valued step sizes, the halting policy flexibly decides exactly when to stop ongoing series in real time. This way, Stop&Hop seamlessly integrates information contained in the timing of observations, a new and vital source for early classification in this setting, with the time series values to provide early classifications for irregular time series. Using four synthetic and three real-world datasets, we demonstrate that Stop&Hop consistently makes earlier and more-accurate predictions than state-of-the-art alternatives adapted to this new problem. Our code is publicly available at https://github.com/thartvigsen/StopAndHop.

Combining the preferences of many rankers into one single consensus ranking is critical for consequential applications from hiring and admissions to lending. While group fairness has been extensively studied for classification, group fairness in rankings and in particular rank aggregation remains in its infancy. Recent work introduced the concept of fair rank aggregation for combining rankings but restricted to the case when candidates have a single binary protected attribute, i.e., they fall into two groups only. Yet it remains an open problem how to create a consensus ranking that represents the preferences of all rankers while ensuring fair treatment for candidates with multiple protected attributes such as gender, race, and nationality. In this work, we are the first to define and solve this open Multi-attribute Fair Consensus Ranking (MFCR) problem. As a foundation, we design novel group fairness criteria for rankings, called MANI-Rank, ensuring fair treatment of groups defined by individual protected attributes and their intersection. Leveraging the MANI-Rank criteria, we develop a series of algorithms that for the first time tackle the MFCR problem. Our experimental study with a rich variety of consensus scenarios demonstrates our MFCR methodology is the only approach to achieve both intersectional and protected attribute fairness while also representing the preferences expressed through many base rankings. Our real world case study on merit scholarships illustrates the effectiveness of our MFCR methods to mitigate bias across multiple protected attributes and their intersections.

Explainability helps users trust deep learning solutions for time series classification. However, existing explainability methods for multi-class time series classifiers focus on one class at a time, ignoring relationships between the classes. Instead, when a classifier is choosing between many classes, an effective explanation must show what sets the chosen class apart from the rest. We now formalize this notion, studying the open problem of class-specific explainability for deep time series classifiers, a challenging and impactful problem setting. We design a novel explainability method, DEMUX, which learns saliency maps for explaining deep multi-class time series classifiers by adaptively ensuring that its explanation spotlights the regions in an input time series that a model uses specifically to its predicted class. DEMUX adopts a gradient-based approach composed of three interdependent modules that combine to generate consistent, class-specific saliency maps that remain faithful to the classifier’s behavior yet are easily understood by end users. Our experimental study demonstrates that DEMUX outperforms nine state-of-the-art alternatives on five popular datasets when explaining two types of deep time series classifiers. Further, through a case study, we demonstrate that DEMUX’s explanations indeed highlight what separates the predicted class from the others in the eyes of the classifier.

In important domains from video stream analytics to human context recognition, datasets are only partially-labeled. Worse yet, the labels are often applied sequentially, as annotators choose labels frame-by-frame or timestep-by-timestep in sequence. With labels not collected independently, this results in sequential bias in the labeling. Unfortunately, current state-of-the-art methods for partially labeled data are rendered ineffective under sequential bias. In this work, we propose a novel solution to tackling this open sequential bias problem, called DeepSPU. DeepSPU recovers missing labels by constructing a model of the sequentially biased labeling process itself. This labeling model is then learned jointly with the prediction model that infers the missing labels in an iterative training process. Further, we regulate this training using a theoretically-justified cost functions that prevent our model from converging to incorrect but low-cost solution. Our experimental studies demonstrate that DeepSPU consistently outperforms the state-of-the-art methods by over 10% on a rich variety of real-world datasets.

Objects ranging from a patient's history of medical tests to an IoT device's series of sensor maintenance records leave digital traces in the form of big time series. These time series objects do not only span exceedingly long time periods (sometimes years), but are also characterized by intermittent yet interrelated time series measurements punctuated by long gaps of silence. This prevalent data type, which we refer to as Time Series Compound objects (or, TSC), has been largely overlooked in the literature. Unique challenges arise when managing, querying and analyzing repositories of these big TSC objects. These include appropriate similarity semantics with time misalignment resiliency, efficient storage of excessively long and complex objects, and TSC-holistic indexing. We demonstrate that state-of-the-art time series systems, although effective at indexing and searching regular time series data, fail to support such big TSC data. In this work, we introduce the first comprehensive solution for managing TSC objects as first class citizen. We introduce new similarity-match semantics as well as a compact misalignment-resilient representation for TSCs. Upon this foundation, we then design a TSC-aware distributed indexing infrastructure Sloth that supports scalable storage, indexing and querying of TB-scale TSC datasets. Our experimental study demonstrates that for TB-scale datasets, the query response time of Sloth is up to one order of magnitude faster than that of existing systems, while the mean average precision (mAP) for approximate kNN similarity match query results by Sloth is 70% more accurate than existing solutions.

Large workloads of event trend aggregation queries are widely deployed to derive high-level insights about current event trends in near real time. To speed-up the execution, we identify and leverage sharing opportunities from complex patterns with flat Kleene operators or even nested Kleene expressions. We propose Gloria, a graph-based sharing optimizer for event trend aggregation. First, we map the sharing optimization problem to a graph path search problem in the Gloria graph with execution costs encoded as weights. Second, we shrink the search space by applying cost-driven pruning principles that guarantee optimality of the reduced Gloria graph in most cases. Lastly, we propose a path search algorithm that identifies the sharing plan with minimum execution costs. Our experimental study on three real-world data sets demonstrates that our Gloria optimizer effectively reduces the search space, leading to 5-fold speed-up in optimization time. The optimized plan consistently reduces the query latency by 68%-93% compared to the plan generated by state-of-the-art approaches.

Anomaly detection is a critical task in applications like preventing financial fraud, system malfunctions, and cybersecurity attacks. While previous research has offered a plethora of anomaly detection algorithms, effective anomaly detection remains challenging for users due to the tedious manual tuning process. Currently, model developers must determine which of these numerous algorithms is best suited for their particular domain and then must tune many parameters by hand to make the chosen algorithm perform well. This demonstration showcases AutoOD, the first unsupervised self-tuning anomaly detection system which frees users from this tedious manual tuning process. AutoOD outperforms the best un-supervised anomaly detection methods it deploys, with its performance similar to those of supervised anomaly classification models, yet without requiring ground truth labels. Our easy-to-use visual interface allows users to gain insights into AutoOD's self-tuning process and explore the underlying patterns within their datasets.

Open set recognition models address the real-world scenario where classes of data unobserved during training are encountered in testing after deployment. Closed set classifiers wrongly attempt to classify instances from an unknown class as belonging to one of the known classes from the training set, which reduces the model’s accuracy. Ideally, these unknown instances should be recognized as such, while known instances should continue to be accurately classified. Unfortunately, state-of-the-art open set methods solve this problem by making restrictive assumptions on the variance and/or boundedness of the distributions of known classes. In this paper, we propose a novel method, Variational Open-Set Recognition (VOSR) that eliminates these assumptions. VOSR incorporates a closed set classifier, an unknown detector, and a novel Structured Gaussian Mixture Variational Autoencoder (SGM-VAE) that guarantees separable class distributions with known variances in its la-tent space. Further, by encouraging a large distance between class-specific distributions, VOSR increases the likelihood that instances from unknown classes lie in low-probability regions and thus are more readily identifiable. In rigorous evaluation, we demonstrate that VOSR outperforms state-of-the-art open set classifiers with up to a 14% F1 score increase in identifying instances from unknown classes in multiple image classification and human activity recognition datasets.

Human activity recognition (HAR), the task of predicting the activities performed by an individual using mobile sensor data, is an active and important area of research. Unfortunately, it is very costly to collect the data required to train robust HAR classifiers. To tackle this issue, there has been an increasing focus on generating synthetic HAR data for augmentation purposes. The state-of-the-art generative HAR approaches utilize Generative Adversarial Networks (GANs) to produce realistic synthetic HAR data. However, these solutions can not generate personalized data that matches the behavior of particular users, limiting their potential use cases. This is particularly problematic in the mobile health domain, where the target users are often elderly or disabled and are thus likely to have activity signals that are unique from the general population. To overcome this drawback, we propose a novel controllable GAN solution Control-HAR-GAN. Our approach learns user and activity signals independently, and when generating synthetic instances, practitioners can specify both the activity to be generated as well as the user the data should match. This has the added benefit in that our model supports novel user-activity pairs by generating examples that match the data that would have been recorded by a particular user if they had performed the target activity, even if the user never performed that activity during the data collection process. We show that our model outperforms the existing HAR GAN approach in generating observed user-activity pairs by up to 10%. Additionally, our approach can also perform the task of novel user-activity pair generation, which is impossible for existing approaches.

Transfer learning has been widely used in natural language processing through deep pretrained language models, such as Bidirectional Encoder Representations from Transformers and Universal Sentence Encoder. Despite the great success, language models get overfitted when applied to small datasets and are prone to forgetting when fine-tuned with a classifier. To remedy this problem of forgetting in transferring deep pretrained language models from one domain to another domain, existing efforts explore fine-tuning methods to forget less. We propose DeepEmotex an effective sequential transfer learning method to detect emotion in text. To avoid forgetting problem, the fine-tuning step is instrumented by a large amount of emotion-labeled data collected from Twitter.We conduct an experimental study using both curated Twitter data sets and benchmark data sets. DeepEmotex models achieve over 91% accuracy for multi-class emotion classification on test dataset. We evaluate the performance of the fine-tuned Deep-Emotex models in classifying emotion in EmoInt and Stimulus benchmark datasets. The models correctly classify emotion in 73% of the instances in the benchmark datasets. The proposed DeepEmotex-BERT model outperforms Bi-LSTM result on the benchmark datasets by 23%. We also study the effect of the size of the fine-tuning dataset on the accuracy of our models. Our evaluation results show that fine-tuning with a large set of emotion-labeled data improves both the robustness and effectiveness of the resulting target task model.

Human-like explanation for text classification is essential for high-impact settings such as healthcare where human rationales are required to support specialists’ decisions. Conventional approaches learn explanations using attention mechanisms to assign heavy weights to words that have a high impact on a model’s prediction. However, such heavily-weighted words often do not reflect human intuition. To advance human rationale, recent studies propose to supervise attention mechanisms assuming access to a huge set of attention labels collected from humans, called human attention maps (HAMs). Unfortunately, acquiring such HAMs for a huge dataset is very tedious, error-prone, and expensive in practice. Thus, we propose the novel problem of text classification with limited human attention supervision. Specifically, we study the learning of human-like attention weights from a dataset in which all documents contain classification labels but only a few documents provide HAMs. To this end, we design a deep learning architecture, HELAS: Human-like Explanation with Limited Attention Supervision to adaptively learn attention weights that focus on words analogous to a human with very limited attention supervision. HELAS effectively unifies joint learning improving both tasks of text classification and humanlike explanation even with only insufficient supervision labels for the latter task. Our experiments show that HELAS generates attention maps similar to real human annotations raising similarity scores up to 22% over state-of-the-art alternatives, even with as little as 2% of the documents having HAMs. It concurrently improves text classification by driving accuracy up to 19% over four state-of-the-art methods.

Explainable classification is essential to high-impact settings where practitioners requireevidence to support their decisions. However, state-of-the-art deep learning models lack transparency in how they make their predictions. One increasingly popular solution is attribution-based explainability, which finds the impact of input features on the model's predictions. While this is popular for computer vision, little has been done to explain deep time series classifiers.In this work, we study this problem and propose PERT, a novel perturbation-based explainability method designed to explain deep classifiers' decisions on time series. PERT extends beyond recent perturbation methods to generate a saliency map that assigns importance values to the timesteps of the instance-of-interest.

Depression is a leading cause of disability with tremendous socioeconomic costs. In spite of early detection being crucial to improving prognosis, this mental illness remains largely undiagnosed. Depression classification from voice holds the promise to revolutionize diagnosis by ubiquitously integrating this screening capability into virtual assistants and smartphone technologies. Unfortunately, due to privacy concerns, audio datasets with depression labels have a small number of participants, causing current classification models to suffer from low performance. To tackle this challenge, we introduce Audio-Assisted BERT (AudiBERT), a novel deep learning framework that leverages the multimodal nature of human voice. To alleviate the small data problem, AudiBERT integrates pretrained audio and text representation models for the respective modalities augmented by a dual self-attention mechanism into a deep learning architecture. AudiBERT applied to depression classification consistently achieves promising performance with an increase in F1 scores between 6% and 30% compared to state-of-the-art audio and text models for 15 thematic question datasets. Using answers from medically targeted and general wellness questions, our framework achieves F1 scores of up to 0.92 and 0.86, respectively, demonstrating the feasibility of depression screening from informal dialogue using voice-enabled technologies.

Deep Learning techniques have been widely used in detecting anomalies from complex data. Most of these techniques are either unsupervised or semi-supervised because of a lack of a large number of labeled anomalies. However, they typically rely on a clean training data not polluted by anomalies to learn the distribution of the normal data. Otherwise, the learned distribution tends to be distorted and hence ineffective in distinguishing between normal and abnormal data. To solve this problem, we propose a novel approach called ELITE that uses a small number of labeled examples to infer the anomalies hidden in the training samples. It then turns these anomalies into useful signals that help to better detect anomalies from user data. Unlike the classical semi-supervised classification strategy which uses labeled examples as training data, ELITE uses them as validation set. It leverages the gradient of the validation loss to predict if one training sample is abnormal. The intuition is that correctly identifying the hidden anomalies could produce a better deep anomaly model with reduced validation loss. Our experiments on public benchmark datasets show that ELITE achieves up to 30% improvement in ROC AUC comparing to the state-of-the-art, yet robust to polluted training data.

Complex event processing (CEP) systems continuously evaluate large workloads of pattern queries under tight time constraints. Event trend aggregation queries with Kleene patterns are commonly used to retrieve summarized insights about the recent trends in event streams. State-of-art methods are limited either due to repetitive computations or unnecessary trend construction. Existing shared approaches are guided by statically selected and hence rigid sharing plans that are often sub-optimal under stream fluctuations. In this work, we propose a novel framework Hamlet that is the first to overcome these limitations. Hamlet introduces two key innovations. First, Hamlet adaptively decides at run time whether to share or not to share computations depending on the current stream properties to harvest the maximum sharing benefit. Second, Hamlet is equipped with a highly efficient shared trend aggregation strategy that avoids trend construction. Our experimental study on both real and synthetic data sets demonstrates that Hamlet consistently reduces query latency by up to five orders of magnitude compared to state-of-the-art approaches.

Cutting-edge machine learning techniques often require millions of labeled data objects to train a robust model. Because relying on humans to supply such a huge number of labels is rarely practical, automated methods for label generation are needed. Unfortunately, critical challenges in auto-labeling remain unsolved, including the following research questions: (1) which objects to ask humans to label, (2) how to automatically propagate labels to other objects, and (3) when to stop labeling. These three questions are not only each challenging in their own right, but they also correspond to tightly interdependent problems. Yet existing techniques provide at best isolated solutions to a subset of these challenges. In this work, we propose the first approach, called LANCET, that successfully addresses all three challenges in an integrated framework. LANCET is based on a theoretical foundation characterizing the properties that the labeled dataset must satisfy to train an effective prediction model, namely the Covariate-shift and the Continuity conditions. First, guided by the Covariate-shift condition, LANCET maps raw input data into a semantic feature space, where an unlabeled object is expected to share the same label with its near-by labeled neighbor. Next, guided by the Continuity condition, LANCET selects objects for labeling, aiming to ensure that unlabeled objects always have some sufficiently close labeled neighbors. These two strategies jointly maximize the accuracy of the automatically produced labels and the prediction accuracy of the machine learning models trained on these labels. Lastly, LANCET uses a distribution matching network to verify whether both the Covariate-shift and Continuity conditions hold, in which case it would be safe to terminate the labeling process. Our experiments on diverse public data sets demonstrate that LANCET consistently outperforms the state-of-the-art methods from Snuba to GOGGLES and other baselines by a large margin - up to 30 percentage points increase in accuracy.

Clinical narratives that describe complex medical events are often accompanied by meta-information such as a patient’s demographics, diagnoses and medications. This structured information implicitly relates to the logical and semantic structure of the entire narrative, and thus affects vocabulary choices for the narrative composition. To leverage this meta-information, we propose a supervised topic compositional neural language model, called MeTRNN, that integrates the strength of supervised topic modeling in capturing global semantics with the capacity of contextual recurrent neural networks (RNN) in modeling local word dependencies. MeTRNN generates interpretable topics from global meta-information and uses them to facilitate contextual RNNs in modeling local dependencies of text. For efficient training of MeTRNN, we develop an autoencoding variational Bayes inference method. We evaluate MeTRNN on the word prediction tasks using public text datasets. MeTRNN consistently outperforms all baselines across all datasets in perplexity ranging from 5% to 40%. Our case studies on real world electronic health records (EHR) data show that MeTRNN can learn and benefit from meaningful topics.

Correlation-based analytics of time series data is important for a wide range of applications from stock analysis to weather forecasting. Yet performing these analytics at the granularity of subsequences of time series is prohibitively costly for large data sets. Our proposed framework CORAL (CORrelation based AnaLytics) tackles this challenge by adopting a preprocess-once and query-many-times paradigm. In a preprocessing step, CORAL compresses time series data into compact clusters, each identified by a unique representative, taking advantage of the Euclidean distance triangle inequality property. Using a mapping between the metric Euclidean distance and non-metric Pearson correlation, we establish inter- and intra-cluster correlation bounds as foundation for CORAL processing. In the CORAL model, inter-cluster correlation relationships are captured as a compact overlay graph with representatives as nodes and the correlation between cluster representatives as edges. The two CORAL bounds support time series matching by realizing the comparison among the cluster representatives at the abstract level in the CORAL graph model in place of the underlying huge collection of raw time series. The resulting CORAL model effectively supports a rich set of analytics operations including retrieval of the best-correlated subsequence, self-correlation, and detection of groups of correlated subsequences. Our comprehensive experimental evaluation on 85 real benchmark datasets demonstrates that CORAL is many fold faster than state-of-the-art systems while returning highly accurate results.

In big data applications from digital health to assisted living smart systems, only a fraction of data instances used for training classifiers t end to be labeled. One important subfield of weakly labeled learning, called Positive Unlabeled (PU) learning, does not require a completely labeled dataset in order to train a strong classifier. This is crucial as in many domains it is expensive or impossible to obtain a completely labeled dataset. While prior PU work assumed that unlabeled instances occurred with a random uniform distribution, we observe that labeled (and unlabeled) data tends to occur in long contiguous sequences (or bursts) due the prevalent burst labeling behavior by human annotators. Burst labeling leads to a sequential bias in PU data not addressed by state-of-the-art methods. To tackle this open problem of learning under sequential bias, we propose BurstPU, the first framework for training a classifier on sequentially labeled PU data. BurstPU addresses the challenge that two interdependent models must be learned, namely, the classification model and the labeling likelihood model, with the later predicting the likelihood that a given instance is labeled. The labeling likelihood model is then needed during the training of the classification model to account for the bias in the labeling process. Our experimental study demonstrates that BurstPU consistently outperforms all state-of-the-art PU methods on a rich variety of diverse real-world datasets, and can learn from fewer labeled instances compared to state-of-art PU methods.

Current research in passive health monitoring utilizes machine learning methods to infer users' symptoms and health status from smartphone-sensed data, which can be gathered on a large scale. However, reasoning about smartphone-sensed health behaviors should engage health experts who may not want to solely rely on computational approaches as they provide limited insights. We designed and proposed a visualization framework for the INTeractive Observation of Smartphone-Inferred Symptoms (INTOSIS), that supports contextualization of symptomatic days by presenting a holistic picture of complex smartphone data for analysts to find c oncerning b ehavior patterns. For instance, while sedentary behavior caused by the flu is concerning, sedentary behaviors on holidays are non-concerning. INTOSIS visualizes multiple smartphone sensor data channels such as geo-location, app usage and screen usage. It uses visual metaphors to effectively represent the data to help analysts derive important human-understandable spatio-temporal contexts and assign health consequences with corresponding semantic labels. INTOSIS provides timeline visualizations of contextual clues such as screen and app usage at night that support an analyst in being able to reason about and then extract plausible explanations for the occurrence of certain symptoms, such as, sleep problems. We validate INTOSIS with intuitive use cases, using a real-world smartphone-sensed dataset, along with expert evaluation.

Publicly available pre-trained word embeddings are rich sources for turning critical high-dimensional representations of huge text data repositories into meaningful compact vectors essential for text mining applications. With many of such pre-trained embedding sources available, each faces limitations in the appropriateness of their language use for the downstream text-mining tasks. Meta-embeddings aim to tackle this ambiguity challenge by fusing multiple embedding sources into one feature space. However, current meta-embedding methods assume vocabularies across sources are similar or even identical; which unfortunately stands in sharp contrast to the fact that many sources barely overlap. Further, these methods encode a meta-embedding for each word by reconstructing its actual embedding values (word-encoder), while valuable information of relationships (distances) among words within each source are not directly considered. In this work, we instead propose a novel relation-encoder learning approach called Similarity-Preserving Meta-Embedding (SimME) that directly integrates word-pair relationships from partially overlapping embedding sources. SimME embeds words such that their similarities are learned from those observed in multiple pre-trained sources. To handle relations between words that are not present in all sources, we introduce maskout, a new loss term, that steers the learning selectively to the sources containing said relations. SimME consistently outperforms state-of-the-art methods by 10% on average and with up to 20% across several core metrics in 4 popular mining tasks on 23 datasets.

Material scientists study corrosion degradation of metallic structures due to its heavy economic and maintenance burdens. Assessing corrosion is both time consuming and labor intensive when utilizing outdoor tests under natural exposure conditions. Accelerated indoor corrosion tests are conducted in laboratory settings by material scientists to gage performance in a shorter period of time than outdoor tests. However, these indoor tests do not always correlate well with the actual performance in outdoor environments. Thus, there is a need to apply data-science methodologies to analyze and establish quantitative associations between indoor accelerated and outdoor exposure assessments to optimize artificially accelerated methods. We work with material experimental records including images, notes, meta-data and human-rated assessments collected over years. We apply data mining methods, such as Canonical Correlation Analysis (CCA) and its variants, to extract latent associations with corresponding feature mappings between the indoor and outdoor assessments in a projected data subspace. We find that CCA provides not only reliable quantitative associations but also interpretive mappings between the indoor and outdoor assessments. Further, three methods applied to control bias due to distinctive coating system stack up yield Pearson's correlation coefficients ranging from 0.70 to 0.83 in the optimized CCA subspaces, respectively. Moreover, predicting outdoor assessments from the CCA-projected indoor test data compared to using the original indoor data is shown to result in an increase in accuracy from 88% to 90% - confirming the effectiveness of our approach. Lastly, our results facilitate interesting domain-relevant discovery that could potentially lead to experimentalists better understanding corrosion resistance.

Distance metric learning has attracted much attention in recent years, where the goal is to learn a distance metric based on user feedback. Conventional approaches to metric learning mainly focus on learning the Mahalanobis distance metric on data attributes. Recent research on metric learning has been extended to sequential data, where we only have structural information in the sequences, but no attribute is available. However, real-world applications often involve attributed sequence data (e.g., clickstreams), where each instance consists of not only a set of attributes (e.g., user session context) but also a sequence of categorical items (e.g., user actions). In this paper, we study the problem of metric learning on attributed sequences. Unlike previous work on metric learning, we now need to go beyond the Mahalanobis distance metric in the attribute feature space while also incorporating the structural information in sequences. We propose a deep learning framework, called MLAS (Metric Learning on Attributed Sequences), to learn a distance metric that effectively measures dissimilarities between attributed sequences. Empirical results on real-world datasets demonstrate that the proposed MLAS framework significantly i mproves the performance of metric learning compared to state-of-the-art methods on attributed sequences.

Recurrent Neural Networks (RNNs) are the state-of-the-art approach to sequential learning. However, standard RNNs use the same amount of computation to generate their hidden states at each timestep, regardless of the input data. Recent works have begun to tackle this rigid assumption by imposing a priori-determined patterns for updating the states at each step. These approaches could lend insights into the dynamics of RNNs and possibly speed up inference. However, the pre-determined nature of the current update strategies limits their application. To overcome this, we instead design the first fully-learned approach, SA-RNN, that augments any RNN by predicting discrete update patterns at the fine granularity of individual hidden state neurons. This is achieved through the parameterization of a distribution of update-likelihoods driven by the input data. Unlike related methods, our approach imposes no assumptions on the structure of the update patterns. Better yet, our method adapts its update patterns online, allowing different dimensions to be updated conditionally based on the input. To learn which dimensions to update, the model solves a multi-objective optimization problem, maximizing task performance while minimizing the number of updates based on a unified control. Using five publicly-available datasets spanning three sequential learning settings, we demonstrate that our method consistently achieves higher accuracy with fewer updates compared to state-of-the-art alternatives. We also show the benefits of learning to sparsely-update a large hidden state as opposed to densely-update a small hidden state. As an added benefit, our method can be directly applied to a wide variety of models containing RNN architectures.

Streaming analytics deploy Kleene pattern queries to detect and aggregate event trends on high-rate data streams. Despite increasing workloads, most state-of-the-art systems process each query independently, thus missing cost-saving sharing opportunities. Sharing event trend aggregation poses several technical challenges. First, Kleene patterns are in general difficult to share due to complex nesting and arbitrarily long matches. Second, not all sharing opportunities are beneficial because sharing Kleene patterns incurs non-trivial overhead to ensure the correctness of final aggregation results. We propose MUSE (Multi-query Shared Event trend aggregation), the first framework that shares aggregation queries with Kleene patterns while avoiding expensive trend construction. To find the beneficial sharing plan, the MUSE optimizer effectively selects robust sharing candidates from the exponentially large search space. Our experiments demonstrate that MUSE increases throughput by 4 orders of magnitude compared to state-of-the-art approaches.

Scalable subsequence matching is critical for supporting analytics on big time series from mining, prediction to hypothesis testing. However, state-of-the-art subsequence matching techniques do not scale well to TB-scale datasets. Not only does index construction become prohibitively expensive, but also the query response time deteriorates quickly as the length of the query subsequence exceeds several 100s of data points. Although Locality Sensitive Hashing (LSH) has emerged as a promising solution for indexing long time series, it relies on expensive hash functions that perform multiple passes over the data and thus is impractical for big time series. In this work, we propose a lightweight distributed indexing framework, called ChainLink, that supports approximate kNN queries over TB-scale time series data. As a foundation of ChainLink, we design a novel hashing technique, called Single Pass Signature (SPS), that successfully tackles the above problem. In particular, we prove theoretically and demonstrate experimentally that the similarity proximity of the indexed subsequences is preserved by our proposed single-pass SPS scheme. Leveraging this SPS innovation, Chainlink then adopts a three-step approach for scalable index building: (1) in-place data re-organization within each partition to enable efficient record-level random access to all subsequences, (2) parallel building of hash-based local indices on top of the re-organized data using our SPS scheme for efficient search within each partition, and (3) efficient aggregation of the local indices to construct a centralized yet highly compact global index for effective pruning of irrelevant partitions during query processing. ChainLink achieves the above three steps in one single map-reduce process. Our experimental evaluation shows that ChainLink indices are compact at less than 2% of dataset size while state-of-the-art index sizes tend to be almost the same size as the dataset. Better still, ChainLink is up to 2 orders of magnitude faster in its index construction time compared to state-of-the-art techniques, while improving both the final query response time by up to 10 fold and the result accuracy by 15%.

Early multi-label classification of time series, the assignment of a label set to a time series before the series is entirely observed, is critical for time-sensitive domains such as healthcare. In such cases, waiting too long to classify can render predictions useless, regardless of their accuracy, while predicting prematurely can result in potentially costly erroneous results. When predicting multiple labels (for example, types of infections), dependencies between labels can be learned and leveraged to improve overall accuracy. Together, reliably predicting the correct label set of a time series while observing as few timesteps as possible is challenging because these goals are contradictory in that fewer timesteps often means worse accuracy. To achieve early yet sufficiently accurate predictions, correlations between labels must be accounted for since direct evidence of some labels may only appear late in the series. We design an effective solution to this open problem, the Recurrent Halting Chain (RHC), that for the first time integrates key innovations in both Early and Multi-label Classification into one multi-objective model. RHC uses a recurrent neural network to jointly model raw time series as well as correlations between labels, resulting in a novel order-free classifier chain that tackles this time-sensitive multi-label learning task. Further, RHC employs a reinforcement learning-based halting network to decide at each timestep which, if any, classes should be predicted, learning to build the label set over time. Using two real-world time-sensitive datasets and popular multi-label metrics, we show that RHC outperforms recent alternatives by predicting more-accurate label sets earlier.

The massive amounts of data series data continuously generated and collected by applications require new indices to speed up data series similarity queries on which various data mining techniques rely. However, the state-of-the-art iSAX-based indexing techniques do not scale well due to the binary fanout that leads to a highly deep index tree and suffer from accuracy degradation due to the character-level cardinality that leads to poor maintenance of the proximity. To address this problem, we recently proposed TARDIS to supports indexing and querying billion-scale data series datasets. It introduces a new iSAX-T signatures to reduce the cardinality conversion cost and corresponding sigTree to construct a compact index structure to preserve better similarity. The framework consists of one centralized index and local distributed indices to efficiently re-partition and index dimensional datasets. Besides, effective query strategies based on sigTree structure are proposed to greatly improve the accuracy. In this demonstration, we present GENET, a new interactive exploration demonstration that allows users to support Big Data Series Approximate Retrieval and Recursive Interactive Clustering in large-scale geospatial datasets using TARDIS index techniques.

Similarity search is the basis for many data analytics techniques, including k-nearest neighbor classification and outlier detection. Similarity search over large data sets relies on i) a distance metric learned from input examples and ii) an index to speed up search based on the learned distance metric. In interactive systems, input to guide the learning of the distance metric may be provided over time. As this new input changes the learned distance metric, a naive approach would adopt the costly process of re-indexing all items after each metric change. In this paper, we propose the first solution, called OASIS, to instantaneously adapt the index to conform to a changing distance metric without this prohibitive re-indexing process. To achieve this, we prove that locality-sensitive hashing (LSH) provides an invariance property, meaning that an LSH index built on the original distance metric is equally effective at supporting similarity search using an updated distance metric as long as the transform matrix learned for the new distance metric satisfies certain properties. This observation allows OASIS to avoid recomputing the index from scratch in most cases. Further, for the rare cases when an adaption of the LSH index is shown to be necessary, we design an efficient incremental LSH update strategy that re-hashes only a small subset of the items in the index. In addition, we develop an efficient distance metric learning strategy that incrementally learns the new metric as inputs are received. Our experimental study using real world public datasets confirms the effectiveness of OASIS at improving the accuracy of various similarity search-based data analytics tasks by instantaneously adapting the distance metric and its associated index in tandem, while achieving an up to 3 orders of magnitude speedup over the state-of-art techniques.

Continuous growth in sensor data and other temporal sequence data necessitates efficient retrieval and similarity search support on these big time series datasets. However, finding exact similarity results, especially at the granularity of subsequences, is known to be prohibitively costly for large data sets. In this paper, we thus propose an efficient framework for solving this exact subsequence similarity match problem, called TINN (TIme series Nearest Neighbor search). Exploiting the range interval diversity properties of time series datasets, TINN captures similarity at two levels of abstraction, namely, relationships among subsequences within each long time series and relationships across distinct time series in the data set. These relationships are compactly organized in an augmented relationship graph model, with the former relationships encoded in similarity vectors at TINN nodes and the later captured by augmented edge types in the TINN Graph. Query processing strategy deploy novel pruning techniques on the TINN Graph, including node skipping, vertical and horizontal pruning, to significantly reduce the number of time series as well as subsequences to be explored. Comprehensive experiments on synthetic and real world time series data demonstrate that our TINN model consistently outperforms state-of-the-art approaches while still guaranteeing to retrieve exact matches.

Railroad trespassing is a dangerous activity with significant security and safety risks. However, regular patrolling of potential trespassing sites is infeasible due to exceedingly high resource demands and personnel costs. This raises the need to design automated trespass detection and early warning prediction techniques leveraging state-of-the-art machine learning. To meet this need, we propose a novel framework for Automated Railroad Trespassing detection System using video surveillance data called ARTS. As the core of our solution, we adopt a CNN-based deep learning architecture capable of video processing. However, these deep learning-based methods, while effective, are known to be computationally expensive and time consuming, especially when applied to a large volume of surveillance data. Leveraging the sparsity of railroad trespassing activity, ARTS corresponds to a dual-stage deep learning architecture composed of an inexpensive pre-filtering stage for activity detection, followed by a high fidelity trespass classification stage employing deep neural network. The resulting dual-stage ARTS architecture represents a flexible solution capable of trading-off accuracy with computational time. We demonstrate the efficacy of our approach on public domain surveillance data achieving 0.87 f1score while keeping up with the enormous video volume, achieving a practical time and accuracy trade-off.

In spite of clinical notes in Electronic Health Records (EHR) providing abundant information about patient health, effective modeling of clinical notes remains in its infancy. A patient's clinical notes correspond to a sequence of free-form texts generated by health care professionals over time; with each note in turn containing a sequence of words. Additionally, notes are accompanied by external attributes at multiple layers such as the time at which each note was created (note level) or the demographics of the patient (patient level). Thus, EHR notes correspond to a nested structure of text sequences augmented with external multi-layer attributes. To model this complex problem, we propose an Attributed Hierarchical Attention model, named HAC-RNN, that integrates multiple RNN layers that encode nested sequential notes with contextual and temporal attention layers that are conditioned on the external attributes. While the bottom layer of HAC-RNN is responsible for contextual summarization of the note content, the top layer combs through the entire timeline of notes to focus on those which are most relevant. These attention layers, which are each conditioned on layer-specific hierarchical attributes, allow personalized predictions through inferring patient profiles.We evaluate HAC-RNN using three real-world medical tasks, detecting in-hospital acquired infections and predicting patient mortality using critical care database MIMIC-III. Our results demonstrate that our model significantly outperforms state-of-the-art techniques for all tasks.

Clinical notes correspond to sequences of reports about patients written over time by health-care professionals. With the availability of massive Electronic Health Record (EHR) datasets composed of such clinical notes, machine learning models on these rich text data series are being developed for patient outcome prediction from infection diagnosis to mortality. While current models focus on content in these unstructured clinical notes, we postulate that timing of the medical events that are explained in the notes are equally crucial. We thus propose a novel attention mechanism composed of dual-attention blocks based on a rich diversity of time representations. We then pair this mechanism with an LSTM, resulting in our proposed time-aware recurrent network TEND-LSTM. TEND-LSTM learns an integrated set of attention weights, with the first attention based on the content of the clinical notes and the second based on when the notes were taken. Together, they are combined using a deep-attention network layer. The proposed dual attention mechanism not only learns a function of time incorporating different aspects of the temporal nature of note instances but also automatically finds a balance between how much attention to put on content versus time. We evaluate our model on six medical tasks using data sets from the publicly-available MIMIC III database from the Beth Israel Deaconess Medical Center. Our results demonstrate that TEND-LSTM outperforms state-of-the-art methods by a large margin.

Mining tasks over sequential data, such as click-streams and gene sequences, require a careful design of embeddings usable by learning algorithms. Recent research in feature learning has been extended to sequential data, where each instance consists of a sequence of heterogeneous items with a variable length. However, many real-world applications often involve attributed sequences, where each instance is composed of both a sequence of categorical items and a set of attributes. In this paper, we study this new problem of attributed sequence embedding, where the goal is to learn the representations of attributed sequences in an unsupervised fashion. This problem is core to many important data mining tasks ranging from user behavior analysis to the clustering of gene sequences. This problem is challenging due to the dependencies between sequences and their associated attributes. We propose a deep multimodal learning framework, called NAS, to produce embeddings of attributed sequences. The embeddings are task independent and can be used on various mining tasks of attributed sequences. We demonstrate the effectiveness of our embeddings of attributed sequences in various unsupervised learning tasks on real-world datasets.

© 2019 Copyright held by the owner/author(s). Local outlier techniques are known to be effective for detecting outliers in skewed data, where subsets of the data exhibit diverse distribution properties. However, existing methods are not well equipped to support modern high-velocity data streams due to the high complexity of the detection algorithms and their volatility to data updates. To tackle these shortcomings, we propose local outlier semantics that operate at an abstraction level by leveraging kernel density estimation (KDE) to effectively detect local outliers from streaming data. A strategy to continuously detect top-N KDE-based local outliers over streams is designed, called KELOS – the first linear time complexity streaming local outlier detection approach. The first innovation of KELOS is the abstract kernel center-based KDE (aKDE) strategy. aKDE accurately yet efficiently estimates the data density at each point – essential for local outlier detection. This is based on the observation that a cluster of points close to each other tend to have a similar influence on a target point’s density estimation when used as kernel centers. These points thus can be represented by one abstract kernel center. Next, the KELOS’s inlier pruning strategy early prunes points that have no chance to become top-N outliers. This empowers KELOS to skip the computation of their data density and of the outlier status for every data point. Together aKDE and the inlier pruning strategy eliminate the performance bottleneck of streaming local outlier detection. The experimental evaluation demonstrates that KELOS is up to 6 orders of magnitude faster than existing solutions, while being highly effective in detecting local outliers from streaming data.

The massive amounts of time series data continuously generated and collected by applications warrant the need for large scale distributed time series processing systems. Indexing plays a critical role in speeding up time series similarity queries on which various analytics and applications rely. However, the state-of-the-art indexing techniques, which are iSAX-based structures, do not scale well due to the small adopted fan-out (binary) that leads to a highly deep index tree, and the expensive search cost through many internal nodes. More seriously, the iSAX character-level cardinality adopted by these indices suffers from a poor maintenance of the proximity relationships among the time series objects, which leads to severe accuracy degradation for approximate similarity queries. In this paper, we propose the TARDIS distributed indexing framework to overcome the aforementioned limitations. TARDIS introduces a novel iSAX index tree that is based on a new word-level variable cardinality. The proposed index ensures compact structure, efficient search and comparison, and good preservation of the similarity relationships. TARDIS is suitable for indexing and querying billion-scale time series datasets. TARDIS is composed of one centralized global index and local distributed indices-one per each data partition across the cluster. TARDIS uses both the global and local indices to efficiently support exact match and kNN approximate queries. The system is implemented using Apache Spark, and extensive experiments are conducted on benchmark and real-world datasets. Evaluation results demonstrate that for over one billion time series dataset (TB scale), the construction of a clustered index is about 83% faster than the existing techniques. Moreover, the average response time of exact match queries is decreased by 50%, and the accuracy of the kNN approximate queries has increased more than 10 fold (from 3% to 40%) compared to the existing techniques.

Early classification of time series is the prediction of the class label of a time series before it is observed in its entirety. In time-sensitive domains where information is collected over time it is worth sacrificing some classification accuracy in favor of earlier predictions, ideally early enough for actions to be taken. However, since accuracy and earliness are contradictory objectives, a solution must address this challenge to discover task-dependent trade-offs. We design an early classification model, called EARLIEST, which tackles this multi-objective optimization problem, jointly learning (1) to classify time series and (2) at which timestep to halt and generate this prediction. By learning the objectives together, we achieve a user-controlled balance between these contradictory goals while capturing their natural relationship. Our model consists of the novel pairing of a recurrent discriminator network with a stochastic policy network, with the latter learning a halting-policy as a reinforcement learning task. The learned policy interprets representations generated by the recurrent model and controls its dynamics, sequentially deciding whether or not to request observations from future timesteps. For a rich variety of datasets (four synthetic and three real-world), we demonstrate that EARLIEST consistently out-performs state-of-the-art alternatives in accuracy and earliness while discovering signal locations without supervision.

Classification over sequential data is important for a wide range of applications from information retrieval, anomaly detection to genomic analysis. Neural network approaches, in particular recurrent neural networks, have been widely used in such tasks due to their strong capability of feature learning. However, recent innovations in sequence classification learn from not only the sequences but also the associated attributes, called attributed sequences. While recent work shows the attributed sequences to be useful in real-world applications, neural attention models have not yet been explored for attributed sequence classification. This paper is the first to study the problem of attributed sequence classification with the neural attention mechanism. This is challenging that now we need to assess the importance of each item in each sequence considering both the sequence itself and the associated metadata. We propose a framework, called AMAS, to classify attributed sequences using the information from the sequences, metadata, and the computed attention. Empirical results on real-world datasets demonstrate that the proposed AMAS framework significantly improves the performance of classification over the state-of-the-art methods on attributed sequences.

Streaming applications from cluster monitoring to algorithmic trading deploy Kleene queries to detect and aggregate event trends. Rich event matching semantics determine how to compose events into trends. The expressive power of state-of-the-art streaming systems remains limited since they do not support many of these semantics. Worse yet, they suffer from long delays and high memory costs because they maintain aggregates at a fine granularity. To overcome these limitations, our Coarse-Grained Event Trend Aggregation (Cogra) approach supports a rich variety of event matching semantics within one system. Better yet, Cogra incrementally maintains aggregates at the coarsest granularity possible for each of these semantics. In this way, Cogra minimizes the number of aggregates -- reducing both time and space complexity. Our experiments demonstrate that Cogra achieves up to six orders of magnitude speed-up and up to seven orders of magnitude memory reduction compared to state-of-the-art approaches.

Ranking, used extensively online and as a critical tool for decision making across many domains, may embed unfair bias. Tools to measure and correct for discriminatory bias are required to ensure that ranking models do not perpetuate unfair practices. Recently, a number of error-based criteria have been proposed to assess fairness with regard to the treatment of protected groups (as determined by sensitive data attributes, e.g., race, gender, or age). However this has largely been limited to classification tasks, and error metrics used in these approaches are not applicable for ranking. Therefore, in this work we propose to broaden the scope of fairness assessment to include error-based fairness criteria for rankings. Our approach supports three criteria: Rank Equality, Rank Calibration, and Rank Parity, which cover a broad spectrum of fairness considerations from proportional group representation to error rate similarity. The underlying error metrics are formulated to be rank-appropriate, using pairwise discordance to measure prediction error in a model-agnostic fashion. Based on this foundation, we then design a fair auditing mechanism which captures group treatment throughout the entire ranking, generating in-depth yet nuanced diagnostics. We demonstrate the efficacy of our error metrics using real-world scenarios, exposing trade-offs among fairness criteria and providing guidance in the selection of fair-ranking algorithms.

ModernInternet of Things(IoT) applications generate massive amounts of time-stamped data, much of it in the form of discrete, symbolic sequences. In this work, we present a new system called TOP that deTects Outlier Patterns from these sequences. To solve the fundamental limitation of existing pattern mining semantics that miss outlier patterns hidden inside of larger frequent patterns, TOP offers new pattern semantics based oncontextual patternsthat distinguish theindependent occurrenceof a pattern from its occurrence as part of its super-pattern. We present efficient algorithms for the mining of this new class of contextual patterns. In particular, in contrast to the bottom-up strategy for state-of-the-art pattern mining techniques, our top-downReducestrategy piggy backs pattern detection with the detection of the context in which a pattern occurs. Our approach achieves linear time complexity in the length of the input sequence. Effective optimization techniques such as context-driven search space pruning and inverted index-based outlier pattern detection are also proposed to further speed up contextual pattern mining. Our experimental evaluation demonstrates the effectiveness of TOP at capturing meaningful outlier patterns in several real-world IoT use cases. We also demonstrate the efficiency of TOP, showing it to be up to 2 orders of magnitude faster than adapting state-of-the-art mining to produce this new class of contextual outlier patterns, allowing us to scale outlier pattern mining to large sequence datasets.

One-shot learning has become an important research topic in the last decade with many real-world applications. The goal of one-shot learning is to classify unlabeled instances when there is only one labeled example per class. Conventional problem setting of one-shot learning mainly focuses on the data that is already in a feature space (such as images). However, the data instances in real-world applications are often more complex and feature vectors may not be available. In this paper, we study the problem of one-shot learning on attributed sequences, where each instance is composed of a set of attributes (e.g., user profile) and a sequence of categorical items (e.g., clickstream). This problem is important for a variety of real-world applications ranging from fraud prevention to network intrusion detection. This problem is more challenging than the conventional one-shot learning since there are dependencies between attributes and sequences. We design a deep learning framework OLAS to tackle this problem. The proposed OLAS utilizes a twin network to generalize the features from pairwise attributed sequence examples. Empirical results on real-world datasets demonstrate the proposed OLAS can outperform the state-of-the-art methods under a rich variety of parameter settings.

Drug-drug interaction related adverse events (DIAE) signals are a major public health issue. Drug safety analysts must sift through thousands of adverse event reports submitted daily to U.S. Food and Drug Administration (FDA) to discover unexpected DIAE signals, which if addressed can lead to life-saving actions. To facilitate the DIAE discovery from these massive data sets, we design several technological innovations that together are integrated into an interactive visual analytics system called DEVES 1. First, our state- of-the-art DIAE mining algorithm efficiently infers potential DIAE signals from these reports, and then ranks them based on their significance score. For interpretability of these inferred DIAE signals, domain knowledge of adverse events and already known drug interactions is extracted from external authoritative data sources and then seamlessly integrated with the inferred signal set. Guided by this augmented signal model, DEVES supports advanced signal analytics - empowering the analyst to interact with linked visualizations offering complementary perspectives into the signal set and its supporting evidence in the form of reports. Our demonstration showcases the technological innovations of DEVES using real-world FDA datasets, demonstrating that DEVES effectively supports the core regulatory tasks from signal screening, signal prioritization to signal validation.

Manually constructing rankings is a tedious ad-hoc process, requiring extensive user effort to evaluate data attribute importance, and often leading to undesirable results. Meanwhile, sophisticated learning-to-rank algorithms are able to leverage large amounts of data to generate high quality rankings automatically. In this work we present RanKit, a novel technology that brings the power of automatic learning-to-rank to the public. RanKit serves as a personal recommender system for building rankings from partial user knowledge in the form of item preferences. A user-friendly rank building interface provides rich input modes for preference specification. Visual feedback on the quality of the learned ranking model is given in real time, empowering the user to guide the underlying learn-to-rank algorithm. Users are actively involved with every step of the rank generation process, developing trust in the model and producing personalized rankings suitable for real-world decision making. In this demonstration, the audience works directly with the RanKit system on public domain datasets ranging from college rankings and economic indicators to movies and sports.

Adverse drug reactions (ADRs) caused by drug-drug interactions (DDI) are a major cause of morbidity and mortality worldwide. There is a growing need for computing-supported methods that facilitate the automated signaling of DDI related ADRs (DIARs) that otherwise would remain undiscovered in millions of ADR reports. In this demonstration, we showcase our MeDIAR technology - an end-to-end DIAR signal generation, exploration and validation solution for pharmaceutical regulatory agencies to detect true DIAR signals from a drug surveillance database. MeDIAR's innovations include an efficient rule-driven learning algorithm for deriving DIAR signals from ADR reports, an innovative scoring methodology based on the proposed contextual association cluster model to rank the generated signals by their importance. Further, these ranked signals are augmented with meta information such as their significance level and their severity, along with links to their supporting ADR reports. Lastly, MeDIAR features an interactive visual analytics interface to support drug safety evaluators in reviewing and discovering unknown severe DIARs.

Domain-specific distances preferred by analysts for exploring similarities among time series tend to be "point-to-point" distances. Unfortunately, this point-wise nature limits their ability to perform meaningful comparisons between sequences of different lengths and with temporal mis-alignments. Analysts instead need "elastic" alignment tools such as Dynamic Time Warping (DTW) to perform such flexible comparisons. However, the existing alignment tools are limited in that they do not incorporate diverse distances. To address this shortcoming, our work introduces the first conceptual framework called Generalized Dynamic Time Warping (GDTW) that supports now alignment (warping) of a large array of domain-specific distances in a uniform manner. While the classic DTW and its prior extensions focus on the Euclidean Distance, our GDTW is the first method that generalizes the ubiquitous DTW and "extends" its warping capabilities to a rich diversity of point-to-point distances. Based on our GDTW paradigm that preserves the efficiency of the dynamic programming paradigm of DTW, we design an abstraction that implemented by our GDTW Design Tool enables analysts to "warp" new distances with little programming effort. Through extensive evaluation studies on 85 real public domain benchmark datasets, we show that our newly warped distances offer higher classification accuracy than the previously available distances for the majority of these datasets. Further, our case study on heart arrhythmia data illustrates the utility of the new distances enabled by our GDTW warping methodology.

Streaming systems evaluate massive workloads of event sequence aggregation queries. State-of-the-art approaches suffer from long delays caused by not sharing intermediate results of similar queries and by constructing event sequences prior to their aggregation. To overcome these limitations, our Shared Online Event Sequence Aggregation (Sharon) approach shares intermediate aggregates among multiple queries while avoiding the expensive construction of event sequences. Our Sharon optimizer faces two challenges. One, a sharing decision is not always beneficial. Two, a sharing decision may exclude other sharing opportunities. To guide our Sharon optimizer, we compactly encode sharing candidates, their benefits, and conflicts among candidates into the Sharon graph. Based on the graph, we map our problem of finding an optimal sharing plan to the Maximum Weight Independent Set (MWIS) problem. We then use the guaranteed weight of a greedy algorithm for the MWIS problem to prune the search of our sharing plan finder without sacrificing its optimality. The Sharon optimizer is shown to produce sharing plans that achieve up to an 18-fold speed-up compared to state-of-the-art approaches.

Event streams generated by smart devices common in modern Internet of Things applications must be continuously mined to monitor the behavior of the underlying system. In this work, we propose a stream pattern mining system for supporting online IoT applications. First, to solve the pattern explosion problem of existing stream pattern mining strategies, we now design pattern semantics that continuously produce a compact set of patterns that max-imumly compresses the dynamic data streams, called MDL-based Representative Patterns (MRP). We then design a one-pass SWIFT approach that continuously mines the up-to-date MRP pattern set for each stream window upon the arrival or expiration of individual events. We show that SWIFT is guaranteed to select the update operation for each individual incoming event that leads to the most compact encoding of the sequence in the current window. We further enhance SWIFT to support batch updates, called B-SWIFT. B-SWIFT adopts alazy updatestrategy that guarantees that only the minimal number of operations are conducted to process an incoming event batch for MRP pattern mining. Evaluation by our industry lighting lab collaborator demonstrates that SWIFT successfully solves their use cases and finds more representative patterns than the alternative approaches adapting the state-of-the-art static representative pattern mining methods. Our experimental study confirms that SWIFT outperforms the best existing method up to 50% in the compactness of produced pattern encodings, while providing a 4 orders of magnitude speedup.

The concept of Top-N local outlier that focuses on the detection of the N points with the largest Local Outlier Factor (LOF) score has been shown to be very effective for identifying outliers in big datasets. However, detecting Top-N local outliers is computationally expensive, since the computation of LOF scores for all data points requires a huge number of high complexity k-nearest neighbor (kNN) searches. In this work, we thus present the first distributed solution to tackle this problem of Top-N local outlier detection (DTOLF). First, DTOLF features an innovative safe elimination strategy that efficiently identifies dually-safe points, namely those that are guaranteed to (1) not be classified as Top-N outliers and (2) not be needed as neighbors of points residing on other machines. Therefore, it effectively minimizes both the processing and communication costs of the Top-N outlier detection process. Further, based on the well-accepted observation that strong correlations among attributes are prevalent in real world datasets, we propose correlation-aware optimization strategies that ensure the effectiveness of grid-based partitioning and of the safe elimination strategy in multi-dimensional datasets. Our extensive experimental evaluation on OpenStreetMap, SDSS, and TIGER datasets demonstrates the effectiveness of DTOLF - up to 10 times faster than the alternative methods and scaling to terabyte level datasets.

ONION is the first system with rich interactive support for efficiently analyzing outliers. ONION features an innovative exploration model that offers an "outlier-centric panorama'' into big datasets. The ONION system is composed of an offline preprocessing phase followed by an online exploration phase that supports rich classes of novel exploration operations. As our demonstration illustrates, this enables analysts to interactively explore outliers at near real-time speed even over large datasets. We demonstrate ONION's capabilities with urban planning applications use cases on the Open Street Maps dataset.

As datasets increase radically in size, highly scalable algorithms leveraging modern distributed infrastructures need to be developed for detecting outliers in massive datasets. In this work, we present the first distributed distance-based outlier detection approach using the MapReduce-based infrastructure, called DOD. DOD features a single-pass execution framework that minimizes communication overhead. Furthermore, DOD overturns two fundamental assumptions widely adopted in the distributed analytics literature, namely cardinality-based load balancing and one algorithm for all data. The multi-tactic strategy of DOD achieves a truly balanced workload by taking into account the data characteristics in data partitioning and assigns most appropriate algorithm for each partition based on our theoretical cost models established for distinct classes of detection algorithms. Thus, DOD effectively minimizes the end-to-end execution time. Our experimental study confirms the efficiency of DOD and its scalability to terabytes of data, beating the baseline solutions by a factor of 20x.

There is a growing need for computing-supported methods that facilitate the automated signaling of Adverse Drug Reactions (ADRs) otherwise left undiscovered from the exploding amount of ADR reports filed by patients, medical professionals and drug manufacturers. In this research, we design a Multi-Drug Adverse Reaction Analytics Strategy, called MARAS, to signal severe unknown ADRs triggered by the usage of a combination of drugs, also known as Multi-Drug Adverse Reactions (MDAR). First, MARAS features an efficient signal generation algorithm based on association rule learning that extracts non-spurious MDAR associations. Second, MARAS incorporates contextual information to detect drug combinations that are strongly associated with a set of ADRs. It groups related associations into Contextual Association Clusters (CACs) that then avail contextual information to evaluate the significance of the discovered MDAR Associations. Lastly, we use this contextual significance to rank discoveries by their notion of interestingness to signal the most compelling MDARs. To demonstrate the utility of MARAS, it is compared with state-of-the-art techniques and evaluated via case studies on datasets collected by U.S. Food and Drug Administration Adverse Event Reporting System (FAERS).

In this work, we present the first distributed solution for the Local Outlier Factor (LOF) method -- a popular outlier detection technique shown to be very effective for datasets with skewed distributions. As datasets increase radically in size, highly scalable LOF algorithms leveraging modern distributed infrastructures are required. This poses significant challenges due to the complexity of the LOF definition, and a lack of access to the entire dataset at any individual compute machine. Our solution features a distributed LOF pipeline framework, called DLOF. Each stage of the LOF computation is conducted in a fully distributed fashion by leveraging our invariant observation for intermediate value management. Furthermore, we propose a data assignment strategy which ensures that each machine is self-sufficient in all stages of the LOF pipeline, while minimizing the number of data replicas. Based on the convergence property derived from analyzing this strategy in the context of real world datasets, we introduce a number of data-driven optimization strategies. These strategies not only minimize the computation costs within each stage, but also eliminate unnecessary communication costs by aggressively pushing the LOF computation into the early stages of the DLOF pipeline. Our comprehensive experimental study using both real and synthetic datasets confirms the efficiency and scalability of our approach to terabyte level data.

Local Outlier Factor (LOF) method that labels all points with their respective LOF scores to indicate their status is known to be very effective for identifying outliers in datasets with a skewed distribution. Since outliers by definition are the absolute minority in a dataset, the concept of Top-N local outlier was proposed to discover the n points with the largest LOF scores. The detection of the Top-N local outliers is prohibitively expensive, since it requires huge number of high complexity k-nearest neighbor (kNN) searches. In this work, we present the first scalable Top-N local outlier detection approach called TOLF. The key innovation of TOLF is a multi-granularity pruning strategy that quickly prunes most points from the set of potential outlier candidates without computing their exact LOF scores or even without conducting any kNN search for them. Our customized density-aware indexing structure not only effectively supports the pruning strategy, but also accelerates the $k$NN search. Our extensive experimental evaluation on OpenStreetMap, SDSS, and TIGER datasets demonstrates the effectiveness of TOLF - up to 35 times faster than the state-of-the-art methods.

Modern applications in this digital age collect a staggering amount of time series data from economic growth rates to electrical household consumption habits. To make sense of it, domain analysts interactively sift through these time series collections in search of critical relationships between and recurring patterns within these time series. The ONEX (Online Exploration of Time Series) system supports effective exploratory analysis of time series collections composed of heterogeneous, variable-length and misaligned time series using robust alignment dynamic time warping (DTW) methods. To assure real-time responsiveness even for these complex and compute-intensive analytics, ONEX precomputes and then encodes time series relationships based on the inexpensive-to-compute Euclidean distance into the ONEX base. Thereafter, based on a solid formal foundation, ONEX uses DTW-enhanced analytics to correctly extract relevant time series matches on this Euclidean-prepared ONEX base. Our live interactive demonstration shows how our ONEX exploratory tool, supported by a rich array of visual interactions and expressive visualizations, enables efficient mining and interpretation of the MATTERS real data collection composed of economic, social, and education data trends across the fifty American states.

Event processing applications from financial fraud detection to health care analytics continuously execute event queries with Kleene closure to extract event sequences of arbitrary, statically unknown length, called Complete Event Trends (CETs). Due to common event sub-sequences in CETs, either the responsiveness is delayed by repeated computations or an exorbitant amount of memory is required to store partial results. To overcome these limitations, we define the CET graph to compactly encode all CETs matched by a query. Based on the graph, we define the spectrum of CET detection algorithms from CPU-optimal to memory-optimal. We find the middle ground between these two extremes by partitioning the graph into time-centric graphlets and caching partial CETs per graphlet to enable effective reuse of these intermediate results. We reveal cost monotonicity properties of the search space of graph partitioning plans. Our CET optimizer leverages these properties to prune significant portions of the search to produce a partitioning plan with minimal CPU costs yet within the given memory limit. Our experimental study demonstrates that our CET detection solution achieves up to 42--fold speed-up even under rigid memory constraints compared to the state-of-the-art techniques in diverse scenarios.

Streaming applications from algorithmic trading to traffic management deploy Kleene patterns to detect and aggregate arbitrarily-long event sequences, called event trends. State-of-the-art systems process such queries in two steps. Namely, they first construct all trends and then aggregate them. Due to the exponential costs of trend construction, this two-step approach suffers from both a long delays and high memory costs. To overcome these limitations, we propose the Graph-based Real-time Event Trend Aggregation (GRETA) approach that dynamically computes event trend aggregation without first constructing these trends. We define the GRETA graph to compactly encode all trends. Our GRETA runtime incrementally maintains the graph, while dynamically propagating aggregates along its edges. Based on the graph, the final aggregate is incrementally updated and instantaneously returned at the end of each query window. Our GRETA runtime represents a win-win solution, reducing both the time complexity from exponential to quadratic and the space complexity from exponential to linear in the number of events. Our experiments demonstrate that GRETA achieves up to four orders of magnitude speed-up and up to 50--fold memory reduction compared to the state-of-the-art two-step approaches.

The detection of abnormal moving objects over high-volume trajectory streams is critical for real-time applications ranging from military surveillance to transportation management. Yet this outlier detection problem, especially along both the spatial and temporal dimensions, remains largely unexplored. In this work, we propose a rich taxonomy of novel classes of neighbor-based trajectory outlier definitions that model the anomalous behavior of moving objects for a large range of real-time applications. Our theoretical analysis and empirical study on two real-world datasets—the Beijing Taxi trajectory data and the Ground Moving Target Indicator data stream—and one generated Moving Objects dataset demonstrate the effectiveness of our taxonomy in effectively capturing different types of abnormal moving objects. Furthermore, we propose a general strategy for efficiently detecting these new outlier classes called the minimal examination (MEX) framework. The MEX framework features three core optimization principles, which leverage spatiotemporal as well as the predictability properties of the neighbor evidence to minimize the detection costs. Based on this foundation, we design algorithms that detect the outliers based on these classes of new outlier semantics that successfully leverage our optimization principles. Our comprehensive experimental study demonstrates that our proposed MEX strategy drives the detection costs 100-fold down into the practical realm for applications that analyze high-volume trajectory streams in near real time.

While recurring queries over evolving data are the bedrock of the analytical applications, resources demanded to process a large amount of data for each recurring execution can be a fatal bottleneck in cost-sensitive cloud computing environments. It is thus imperative to design a system responsive to users' preferences regarding how resources should be utilized. In this work, we propose PRO, a preference-aware recurring query processing system that optimizes recurring query executions complying with user preferences. First, we show that finding an optimal is an NP-complete problem due to the cost interdependencies between consecutive executions. We propose an execution relation graph (ERG) model that effectively incorporates these dependencies between executions. This model enables us to transform our problem into a well-known graph problem. We then design a graph-based approach (called PRO-OPT) leveraging dynamic programming and pruning techniques with pseudo-polynomial complexity. Our experiments confirm that PRO consistently outperforms state-of-the-art solutions by 9 fold in processing time under a rich variety of circumstances on the Wikipedia datasets.

© 2016, Copyright is with the authors. Although existing database systems provide users an efficient means to select tuples based on attribute criteria, they however provide little means to select tuples based on whether they meet aggregate requirements. For instance, a requirement may be that the cardinality of the query result must be 1000 or the sum of a particular attribute must be < $5000. In this work, we term such queries as "Aggregation Constrained Queries" (ACQs). Aggregation constrained queries are crucial in many decision support applications to maintain a product's competitive edge in this fast moving field of data processing. The challenge in processing ACQs is the unfamiliarity of the underlying data that results in queries being either too strict or too broad. Due to the lack of support of ACQs, users have to resort to a frustrating trial-and-error query refinement process. In this paper, we introduce and define the semantics of ACQs. We propose a refinement-based approach, called ACQUIRE, to efficiently process a range of ACQs. Lastly, in our experimental analysis we demonstrate the superiority of our technique over extensions of existing algorithms. More specifically, ACQUIRE runs up to 2 orders of magnitude faster than compared techniques while producing a 2X reduction in the amount of refinement made to the input queries.

Real-time analytics of anomalous phenomena on streaming data typically relies on processing a large variety of continuous outlier detection requests, each configured with different parameter settings. The processing of such complex outlier analytics workloads is resource consuming due to the algorithmic complexity of the outlier mining process. In this work we propose a sharing-aware multi-query execution strategy for outlier detection on data streams called SOP. A key insight of SOP is to transform the problem of handling a multi-query outlier analytics workload into a single-query skyline computation problem. We prove that the output of the skyline computation process corresponds to the minimal information needed for determining the outlier status of any point in the stream. Based on this new formulation, we design a customized skyline algorithm called K-SKY that leverages the domination relationships among the streaming data points to minimize the number of data points that must be evaluated for supporting multi-query outlier detection. Based on this K-SKY algorithm, our SOP solution achieves minimal utilization of both computational and memory resources for the processing of these complex outlier analytics workload. Our experimental study demonstrates that SOP consistently outperforms the state-of-art solutions by three orders of magnitude in CPU time, while only consuming 5% of their memory footprint - a clear win-win. Furthermore, SOP is shown to scale to large workloads composed of thousands of parameterized queries.

Complex Event Processing (CEP) has emerged as a technology of choice for high performance event analytics in time-critical decision-making applications. Yet it is becoming increasingly difficult to support high-performance event processing due to the rising number and complexity of event pattern queries and the increasingly high velocity of event streams. In this work we design the SPASS framework that successfully tackles these demanding CEP workloads. Our SPASS optimizer identifies opportunities for effective shared processing among CEP queries by leveraging time-based event correlations among queries. The problem of pattern sharing is shown to be NP-hard by reducing the Minimum Substring Cover problem to our CEP pattern sharing problem. The SPASS optimizer is designed that finds a shared pattern plan in polynomial-time covering all sequence patterns while still guaranteeing an optimality bound. To execute this shared pattern plan, the SPASS runtime employs stream transactions that assure concurrent shared maintenance and re-use of sub-patterns across queries. Our experimental study confirms that the SPASS framework achieves over 16 fold performance improvement for a wide range of experiments compared to the state-of-the-art solution.

Finding similar trends among time series data is critical for applications ranging from financial planning to policy making. The detection of these multifaceted relationships, especially time warped matching of time series of different lengths and alignments is prohibitively expensive to compute. To achieve real time responsiveness on large time series datasets, we propose a novel paradigm called Online Exploration of Time Series (ONEX) employing a powerful one-time preprocessing step that encodes critical similarity relationships to support subsequent rapid data exploration. Since the encoding of a huge number of pairwise similarity relationships for all variable lengths time series segments is not feasible, our work rests on the important insight that clustering with inexpensive point-to-point distances such as the Euclidean Distance can support subsequent time warped matching. Our ONEX framework overcomes the prohibitive computational costs associated with a more robust elastic distance namely the DTW by applying it over the surprisingly compact knowledge base instead of the raw data. Our comparative study reveals that ONEX is up to 19% more accurate and several times faster than the state-of-the-art. Beyond being a highly accurate and fast domain independent solution, ONEX offers a truly interactive exploration experience supporting novel time series operations.

Because of high volumes and unpredictable arrival rates, stream processing systems cannot always keep up with input data streams, resulting in buffer overflow and uncontrolled loss of data. Load shedding and spilling, the two prevalent technologies designed to solve this overflow problem by dropping or flushing data to disk, suffer from serious shortcomings. Dropping data suffers in that partial output is lost forever, while flushing may waste precious resources due to making the strong assumption that flushed data can and will eventually still be processed. In this paper, we propose our solution, INSURE, integrating structure-based drop and flush techniques within one unified framework for XML stream systems. Our INSURE framework provides an optimized fine-grained load reduction solution that achieves high quality result production. First, the fusion candidate lattice models the space of load reduction solutions incorporating both drop and flush decisions, called fusion candidates. Second, our systematic analysis of fusion candidates and their interrelationships in the fusion candidate lattice reveals important relationships, including the monotonicity of their feasibility and profitability properties. Third, based upon this fusion candidate lattice model, a family of optimization strategies for the selection of fusion candidates is designed to successfully maximize the overall result quality. Experimental results demonstrate that INSURE consistently achieves higher quality results compared to the state-of-the-art techniques, yet with negligible overhead.

Traditional outlier detection systems process each individual outlier detection request instantiated with a particular parameter setting one at a time. This is not only prohibitively time-consuming for large datasets, but also tedious for analysts as they explore the data to hone in on the appropriate parameter setting and desired results.

With the increasing complexity of data-intensive MapReduce workloads, Hadoop must often accommodate hundreds or even thousands of recurring analytics queries that periodically execute over frequently updated datasets, e.g., latest stock transactions, new log files, or recent news feeds. For many applications, such recurring queries come with user-specified service-level agreements (SLAs), commonly expressed as the maximum allowed latency for producing results before their merits decay. The recurring nature of these emerging workloads combined with their SLA constraints make it challenging to share and optimize their execution. While some recent efforts on multi-job optimization in MapReduce have emerged, they focus on only sharing work among ad-hoc jobs on static datasets. Unfortunately, these sharing techniques neither take the recurring nature of the queries into account nor guarantee the satisfaction of the SLA requirements. In this work, we propose the first scalable multi-query sharing engine tailored for recurring workloads in the MapReduce infrastructure, called "Helix" . Helix deploys new sliced window-alignment techniques to create sharing opportunities among recurring queries without introducing additional I/O overheads or unnecessary data scans. And then, Helix introduces a cost/benefit model for creating a sharing plan among the recurring queries, and a scheduling strategy for executing them to maximize the SLA satisfaction. Our experimental results over real-world datasets confirm that Helix significantly outperforms the state-of-art techniques by an order of magnitude.

The growing demand for large-scale data analytics ranging from online advertisement placement, log processing, to fraud detection, has led to the design of highly scalable data-intensive computing infrastructures such as the Hadoop platform. Recurring queries, re-peatedly being executed for long periods of time on rapidly evolv-ing high-volume data, have become a bedrock component in most of these analytic applications. Despite their importance, the plain Hadoop along with its state-of-art extensions lack built-in support for recurring queries. In particular, they lack efficient and scal-able analytics over evolving datasets. In this work, we present the Redoop system, an extension of the Hadoop framework, designed to fill in this void. Redoop supports recurring queries as first-class citizen in Hadoop without sacrificing any of its core features. More importantly, Redoop deploys innovative window-aware opti-mization techniques for recurring query execution including adap-tive window-aware data partitioning, window-aware task schedul-ing, and inter-window caching mechanisms. Redoop retains the fault-tolerance of MapReduce via automatic cache recovery and task re-execution support. Our extensive experimental study with real datasets demonstrates that Redoop achieves significant run-time performance gains of up to 9x speedup compared to the plain Hadoop. 1.

Association rule mining typically focuses on discovering global rules valid across the entire dataset. Yet local rules valid for subsets of the dataset, while significantly different from global rules, are often also of tremendous importance to analysts. In this work, we tackle this overlooked problem of online mining of localized asso-ciation rules. We provide support for analysts to interactively mine rules that are hidden in a global context yet are locally significant. To tackle this problem we design a compact multidimensional itemset-based data partitioning (MIP-index). MIP-index offers ef-ficient mining performance by utilizing precomputed results, while still allowing the user the flexibility of selecting any data subset of interest at run-time. We design a suite of alternative execu-tion strategies for processing such localized mining requests. Op-timization principles such as selection push-up, supported R-tree filter and differential treatment of contained and partially over-lapped MIPs are proposed. We analytically and experimentally demonstrate that different execution strategies are effective for dif-ferent query scenarios. Given a localized mining query, our CO-LARM query optimizer takes a cost-based approach to identify the best strategy for execution. Through extensive experiments using benchmark data sets we demonstrate that the COLARM optimizer is highly accurate in online plan selection and discovering local-ized rules (otherwise hidden in the global context) in a diversity of localized mining requests.

Real-time analytical systems need to handle workloads comprised of expensive decision support queries with diverse quality of ser-vice requirements known as contracts. Contract driven multi-query processing, being an NP-hard problem, remains unaddressed to date. The traditional approach of blindly pipelining the entire input through a shared execution plan is not viable due to the diversity in query contracts. To tackle this challenge, we now develop a flexi-ble model to express contracts and accompany it with an effective means to measure the run-time contract satisfaction. We propose our Contract-Aware Query Execution framework CAQE. In this work, we exploit the principle that “different portions of the in-put contribute to disparate subsets of queries with varying degrees of progressiveness. ” Therefore, CAQE’s processing of the input chunks is driven by how the different query contracts are being met at run-time. To maximize the contract satisfaction of the work-load, CAQE leverages the dependencies of input chunks across the queries. This enables us to determine the impact of processing par-ticular input chunks on improving the run-time contract satisfac-tion. Our experiments demonstrate the effectiveness of CAQE in increasing the overall contract satisfaction of the workload, specifi-cally 2 fold better than existing multi-query processing techniques. 1.

The discovery of distance-based outliers from huge volumes of streaming data is critical for modern applications ranging from credit card fraud detection to moving object monitoring. In this work, we propose the first general framework to handle the three major classes of distance-based outliers in streaming environments, including the traditional distance-threshold based and the nearest-neighbor-based definitions. Our LEAP framework encompasses two general optimization principles applicable across all three outlier types. First, our “minimal probing” principle uses a lightweight probing operation to gather minimal yet sufficient evidence for outlier detection. This principle overturns the state-of-the-art methodology that requires routinely conducting expensive complete neighborhood searches to identify outliers. Second, our “lifespan-aware prioritization” principle leverages the temporal relationships among stream data points to prioritize the processing order among them during the probing process. Guided by these two principles, we design an outlier detection strategy which is proven to be optimal in CPU costs needed to determine the outlier status of any data point during its entire life. Our comprehensive experimental studies, using both synthetic as well as real streaming data, demonstrate that our methods are 3 orders of magnitude faster than state-of-the-art methods for a rich diversity of scenarios tested yet scale to high dimensional streaming data.

The detection of abnormal moving objects over high-volume trajectory streams is critical for real time applications ranging from military surveillance to transportation management. Yet this problem remains largely unexplored. In this work, we first propose classes of novel trajectory outlier definitions that model the anomalous behavior of moving objects for a large range of real time applications. Our theoretical analysis and empirical study on the Beijing Taxi and GMTI (Ground Moving Target Indicator) datasets demonstrate its effectiveness in capturing abnormal moving objects. Furthermore we propose a general strategy for efficiently detecting the new outlier classes. It features three fundamental optimization principles designed to minimize the detection costs. Our comprehensive experimental studies demonstrate that our proposed strategy drives the detection costs 100-fold down into practical realm for applications producing high volume trajectory streams to utilize.

Complex Event Processing (CEP) is a technology of choice for high performance analytics in time-critical decision-making applications. Yet while effective technologies for complex pattern detection on continuous event streams have been developed, the problem of scalable online aggregation of such patterns has been overlooked. Instead, aggregation is typically applied as a post processing step after CEP pattern detection, leading to an extremely ineffective solution. In this paper, we demonstrate that CEP aggregation can be pushed into the sequence construction process. Based on this insight our A-Seq strategy successfully aggregates sequence pattern online without ever constructing sequence matches. This drives down the complexity of the CEP aggregation problem from polynomial to linear. We further extend our A-Seq strategy to support the shared processing of concurrent CEP aggregation queries. The A-Seq solution is shown to achieve over four orders of magnitude performance improvement for a wide range of tested scenarios compared to the state-of-the-art solution.

Overloaded data stream management systems (DSMS) cannot process all tuples within their response time. For some DSMS it is crucial to allocate the precious resources to process the most significant tuples. Prior work has applied shedding and spilling to permanently drop or temporarily place to disk insignificant tuples. However neither approach considers that tuple significance can be multi-tiered nor that significance determination can be costly. These approaches consider all tuples not dropped to be equally significant. Unlike these prior works, we take a fresh stance by pulling the most significant tuples forward throughout the query pipeline. Proactive Promotion (PP), a new DSMS methodology for preferential CPU resource allocation, selectively pulls the most significant tuples ahead of less significant tuples. Our optimizer produces an optimal PP plan that minimizes the processing latency of tuples in the most significant tiers in this multi-tiered precedence scheme by strategically placing significance determination operators throughout the query pipeline at compile-time and by agilely activating them at run-time. Our results substantiate that PP lowers the latency and increases the throughput for significant results when compared to the state-of-the-art shedding and traditional DSMS approaches (between 2 and 18 fold for a rich diversity of datasets) with negligible overhead.

We demonstrate our VSOutlier system for supporting interactive exploration of outliers in big data streams. VSOutlier not only supports a rich variety of outlier types supported by innovative and efficient outlier detection strategies, but also provides a rich set of interactive interfaces to explore outliers in real time. Using the stock transactions dataset from the US stock market and the moving objects dataset from MITRE, we demonstrate that the VSOutlier system enables analysts to more efficiently identify, understand, and respond to phenomena of interest in near real-time even when applied to high volume streams.

This demonstration presents the Redoop infrastructure, the first full-fledged MapReduce framework with native support for recurring big data queries. Recurring queries, repeatedly being executed for long periods of time over evolving high-volume data, have become a bedrock component in most large-scale data analytic applications. Redoop is a comprehensive extension to Hadoop that pushes the support and optimization of recurring queries into Hadoop's core functionality. While backward compatible with regular MapReduce jobs, Redoop achieves an order of magnitude better performance than Hadoop for recurring workloads. Redoop employs innovative window-aware optimization techniques for such recurring workloads including adaptive window-aware data partitioning, cache-aware task scheduling, and inter-window caching mechanisms. We will demonstrate Redoop's capabilities on a compute cluster against real life workloads including click-stream and sensor data analysis.

We demonstrate our SPIRE technology for supporting interactive mining of both positive and negative rules at the speed of thought. It is often misleading to learn only about positive rules, yet extremely revealing to find strongly supported negative rules. Key technical contributions of SPIRE including region-wise abstractions of rules, positive-negative rule relationship analysis, rule redundancy management and rule visualization supporting novel exploratory queries will be showcased. The audience can interactively explore complex rule relationships in a visual manner, such as comparing negative rules with their positive counterparts, that would otherwise take prohibitive time. Overall, our SPIRE system provides data analysts with rich insights into rules and rule relationships while significantly reducing manual effort and time investment required.

Distributed stream processing systems must function efficiently for data streams that fluctuate in their arrival rates and data distributions. Yet repeated and prohibitively expensive load reallocation across machines may make these systems ineffective, potentially resulting in data loss or even system failure. To overcome this problem, we propose a comprehensive solution, called the Robust Load Distribution (RLD) strategy, that is resilient under data fluctuations. RLD provides ϵ-optimal query performance under an expected range of load fluctuations without suffering from the performance penalty caused by load migration. RLD is based on three key strategies. First, we model robust distributed stream processing as a parametric query optimization problem in a parameter space that captures the stream fluctuations. The notions of both robust logical and robust physical plans that work together to proactively handle all ranges of expected fluctuations in parameters are abstracted as overlays of this parameter space. Second, our Early-terminated Robust Partitioning ( ERP ) finds a combination of robust logical plans that together cover the parameter space, while minimizing the number of prohibitively expensive optimizer calls with a probabilistic bound on the space coverage. Third, we design a family of algorithms for physical plan generation. Our GreedyPhy exploits a probabilistic model to efficiently find a robust physical plan that sustains most frequently used robust logical plans at runtime. Our CorPhy algorithm exploits operator correlations for the robust physical plan optimization. The resulting physical plan smooths the workload on each node under all expected fluctuations. Our OptPrune algorithm, using CorPhy as baseline, is guaranteed to find the optimal physical plan that maximizes the parameter space coverage with a practical increase in optimization time. Lastly, we further expand the capabilities of our proposed RLD framework to also appropriately react under so-called “space drifts”, that is, a space drift is a change of the parameter space where the observed runtime statistics deviate from the expected optimization-time statistics. Our RLD solution is capable of adjusting itself to the unexpected yet significant data fluctuations beyond those planned for via covering the parameter space. Our experimental study using stock market and sensor network streams demonstrates that our RLD methodology consistently outperforms state-of-the-art solutions in terms of efficiency and effectiveness in highly fluctuating data stream environments.

While significant strides have been made on efficient association rule mining, the usability of mining systems woefully lags behind. In particular, the usability of rule mining systems is limited by the lack of support for interactive exploration of the relationships among rule results produced with various parameter settings. Based on a novel parameter space-driven approach, our proposed Framework for Interactive Rule Exploration (FIRE) addresses the usability shortcoming. FIRE features innovative visual displays and effective interactions that enable analysts to conduct rule exploration at the speed of thought. Particularly, the parameter space view (PSpace) displays the distribution of rules produced for diverse parameter settings. This not only facilitates user parameter selection but also empowers analyst's to understand rule relationships in the parameter space context. Our user study with 22 subjects establishes the usability and effectiveness of the proposed features and interactions of FIRE using benchmark datasets. Overall, this research encompasses significant contributions at the intersection of data mining, knowledge management and visual analytics.

We demonstrate our SPHINX system that not only derives but also visualizes evidence-hypotheses relationships on a parameter space of belief and plausibility. SPHINX facilitates the analyst to interactively explore the contribution of different pieces of evidence towards the hypotheses. The key technical contributions of SPHINX include both computational and visual dimensions. The computational contributions cover (a.) flexible computational model selection; and (b.) real-time incremental strength computations. The visual contributions include (a.) sense-making over parameter space; (b.) filtering and abstraction options; (c.) novel visual displays such as evidence glyph and skyline views. Using two real datasets, we will demonstrate that the SPHINX system provides the analysts with rich insights into evidence-hypothesis relationships facilitating the discovery and decision making process.

Complex Event Processing (CEP) has become increasingly important for tracking and monitoring anomalies and trends in event streams emitted from business processes such as supply chain management to online stores in e-commerce. These monitoring applications submit complex event queries to track sequences of events that match a given pattern. While the state-of-the-art CEP systems mostly focus on the execution of flat sequence queries, we instead support the execution of nested CEP queries specified by the (NEsted Event Language) NEEL. However the iterative execution often results in the repeated recomputation of similar or even identical results for nested subexpressions as the window slides over the event stream. In this work we thus propose to optimize NEEL execution performance by caching intermediate results. In particular we design two methods of applying selective caching of intermediate results. The first is the Continuous Sliding Caching technique. The second is a further optimization of the previous technique which we call the Interval-Driven Semantic Caching. Techniques for incrementally loading, purging and exploiting the cache content are described. Our experimental study using real-world stock trades evaluates the performance of our proposed caching strategies for different query types.

Recent years have witnessed the emergence of real-time object monitoring applications driven by the explosion of small inexpensive sensors. In many real-world applications, not all sensed events carry the identification of the object whose action they report on, so called "non-ID-ed" events. Reasons range from heterogeneous sensing devices to human's choosing to conceal their identifications. Such non-ID-ed events prevent us from performing object-based analytics, such as tracking, alerting and pattern matching. We propose a probabilistic inference framework, called FISS, to tackle this problem by inferring the missing object identification associated with an event. Specifically, as a foundation we design a time-varying graphic model to capture correspondences between sensed events and objects. Upon this formal model, we elaborate how to adapt the Forward-backward (FB) inference algorithm to continuously infer probabilistic identifications for non-ID-ed events. However, we demonstrate that FB is neither scalable nor efficient over event streams. To overcome this deficiency, we propose a suite of strategies for optimizing its performance, including the selective smoothing technique that significantly reduces the number of random variables that need to be smoothed, and the finish-flag mechanism that enables early termination of backward computations. Our experimental results, using large-volume streams of a real-world healthcare application, demonstrate the accuracy, efficiency, and scalability of FISS. Especially FISS achieves on average 15x higher throughput than our basic FB inference.

Distributed stream processing systems must function efficiently for data streams that fluctuate in their arrival rates and data distributions. Yet repeated and prohibitively expensive load re-allocation across machines may make these systems ineffective, potentially resulting in data loss or even system failure. To overcome this problem, we instead propose a load distribution (RLD) strategy that is robust to data fluctuations. RLD provides ϵ-optimal query performance under load fluctuations without suffering from the performance penalty caused by load migration. RLD is based on three key strategies. First, we model robust distributed stream processing as a parametric query optimization problem. The notions of robust logical and robust physical plans then are overlays of this parameter space. Second, our Early-terminated Robust Partitioning (ERP) finds a set of robust logical plans, covering the parameter space, while minimizing the number of prohibitively expensive optimizer calls with a probabilistic bound on the space coverage. Third, our OptPrune algorithm maps the space-covering logical solution to a single robust physical plan tolerant to deviations in data statistics that maximizes the parameter space coverage at runtime. Our experimental study using stock market and sensor networks streams demonstrates that our RLD methodology consistently outperforms state-of-the-art solutions in terms of efficiency and effectiveness in highly fluctuating data stream environments.

We demonstrate our PARAS technology for supporting interactive association mining at near real-time speeds. Key technical innovations of PARAS, in particular, stable region abstractions and rule redundancy management supporting novel parameter space-centric exploratory queries will be showcased. The audience will be able to interactively explore the parameter space view of rules. They will experience near real-time speeds achieved by PARAS for operations, such as comparing rule sets mined using different parameter values, that would otherwise take hours of computation and much manual investigation. Overall, we will demonstrate that the PARAS system provides a rich experience to data analysts through parameter tuning recommendations while significantly reducing the trial-and-error interactions.

Complex Event Processing (CEP) has emerged as a technology for monitoring event streams in search of user specified event patterns. When a CEP system is deployed in sensitive environments the user may wish to mitigate leaks of private information while ensuring that useful nonsensitive patterns are still reported. In this paper we consider how to suppress events in a stream to reduce the disclosure of sensitive patterns while maximizing the detection of nonsensitive patterns. We first formally define the problem of utility-maximizing event suppression with privacy preferences, and analyze its computational hardness. We then design a suite of real-time solutions to solve this problem. Our first solution optimally solves the problem at the event-type level. The second solution, at the event-instance level, further optimizes the event-type level solution by exploiting runtime event distributions using advanced pattern match cardinality estimation techniques. Our user study and experimental evaluation over both real-world and synthetic event streams show that our algorithms are effective in maximizing utility yet still efficient enough to offer near real-time system responsiveness.

State-of-the-art optimizers produce one single optimal query plan for all stream data, in spite of such a singleton plan typically being sub-optimal or even poor for highly correlated data. Recently a new stream processing paradigm, called multi-route approach, has emerged as a promising approach for tackling this problem. Multi-route first divides data streams into several partitions and then creates a separate query plan for each combination of partitions. Unfortunately current approaches suffer from severe shortcomings, in particular, the lack of an effective partitioning strategy and the prohibitive query optimization expense. In this work we propose the first practical multi-route optimizer named correlation-aware multi-route stream query optimizer (or CMR) that solves both problems. By exploiting both intra- and inter-stream correlations of streams, CMR produces effective partitions without having to undertake repeated expensive query plan generation. The produced partitions not only are best served by distinct optimal query plans, but also leverage the partition-driven pruning opportunity. Experimental results with both synthetic and real life stream data confirm that CMR outperforms the state-of-the-art solutions up to an order of magnitude in both the query optimization time and the run-time execution performance.

Association rule mining is known to be computationally intensive, yet real-time decision-making applications are increasingly intolerant to delays. In this paper, we introduce the parameter space model, called PARAS. PARAS enables efficient rule mining by compactly maintaining the final rulesets. The PARAS model is based on the notion of stable region abstractions that form the coarse granularity ruleset space. Based on new insights on the redundancy relationships among rules, PARAS establishes a surprisingly compact representation of complex redundancy relationships while enabling efficient redundancy resolution at query-time. Besides the classical rule mining requests, the PARAS model supports three novel classes of exploratory queries. Using the proposed PSpace index, these exploratory query classes can all be answered with near real-time responsiveness. Our experimental evaluation using several benchmark datasets demonstrates that PARAS achieves 2 to 5 orders of magnitude improvement over state-of-the-art approaches in online association rule mining.

We will demonstrate the visual analytics system V istreamT, that supports interactive mining of complex patterns within and across live data streams and stream pattern archives. Our system is equipped with both computational pattern mining and visualization techniques, which allow it to not only efficiently discover and manage patterns but also effectively convey the mining results to human analysts through visual displays. In our demonstration, we will illustrate that with V istreamT, analysts can easily submit, monitor and interact with a broad range of query types for pattern mining. This includes novel strategies for extracting complex patterns from streams in real time, summarizing neighbour-based patterns using multi-resolution compression strategies, selectively pushing patterns into the stream archive, validating the popularity or rarity of stream patterns by stream archive matching, and pattern evolution tracking to link patterns across time.

Complex Event Processing (CEP) over event streams has become increasingly important for real-time applications ranging from healthcare to supply chain management. In such applications, arbitrarily complex sequence patterns as well as non existence of such complex situations must be detected in real time. To assure real-time responsiveness for detection of such complex pattern over high volume high-speed streams, efficient processing techniques must be designed. Unfortunately the efficient processing of complex sequence queries with negations remains a largely open problem to date. To tackle this shortcoming, we designed optimized strategies for handling nested CEP query. In this demonstration, we propose to showcase these techniques for processing and optimizing nested pattern queries on streams. In particular our demonstration showcases a platform for specifying complex nested queries, and selecting one of the alternative optimized techniques including sub-expression sharing and intermediate result caching to process them. We demonstrate the efficiency of our optimized strategies by graphically comparing the execution time of the optimized solution against that of the default processing strategy of nested CEP queries. We also demonstrate the usage of the proposed technology in several healthcare services.

In diverse applications ranging from stock trading to traffic monitoring, data streams are continuously monitored by multiple analysts for extracting patterns of interest in real time. These analysts often submit similar pattern mining requests yet customized with different parameter settings. In this work, we present shared execution strategies for processing a large number of neighbor-based pattern mining requests of the same type yet with arbitrary parameter settings. Such neighbor-based pattern mining requests cover a broad range of popular mining query types, including detection of clusters, outliers, and nearest neighbors. Given the high algorithmic complexity of the mining process, serving multiple such queries in a single system is extremely resource intensive. The naive method of detecting and maintaining patterns for different queries independently is often infeasible in practice, as its demands on system resources increase dramatically with the cardinality of the query workload. In order to maximize the efficiency of the system resource utilization for executing multiple queries simultaneously, we analyze the commonalities of the neighbor-based pattern mining queries, and identify several general optimization principles which lead to significant system resource sharing among multiple queries. In particular, as a preliminary sharing effort, we observe that the computation needed for the range query searches (the process of searching the neighbors for each object) can be shared among multiple queries and thus saves the CPU consumption. Then we analyze the interrelations between the patterns identified by queries with different parameters settings, including both pattern-specific and window-specific parameters. For that, we first introduce an incremental pattern representation, which represents the patterns identified by queries with different pattern-specific parameters within a single compact structure. This enables integrated pattern maintenance for multiple queries. Second, by leveraging the potential overlaps among sliding windows, we propose a metaquery strategy which utilizes a single query to answer multiple queries with different window-specific parameters. By combining these three techniques, namely the range query search sharing, integrated pattern maintenance, and metaquery strategy, our framework realizes fully shared execution of multiple queries with arbitrary parameter settings. It achieves significant savings of computational and memory resources due to shared execution. Our comprehensive experimental study, using real data streams from domains of stock trades and moving object monitoring, demonstrates that our solution is significantly faster than the independent execution strategy, while using only a small portion of memory space compared to the independent execution. We also show that our solution scales in handling large numbers of queries in the order of hundreds or even thousands under high input data rates.

A continuous top-k query retrieves the k most preferred objects in a data stream according to a given preference function. These queries are important for a broad spectrum of applications ranging from web-based advertising to financial analysis. In various streaming applications, a large number of such continuous top-k queries need to be executed simultaneously against a common popular input stream. To efficiently handle such top-k query workload, we present a comprehensive framework, called MTopS.Within this MTopS framework, several computational components work collaboratively to first analyze the commonalities across the workload; organize the workload for maximized sharing opportunities; execute the workload queries simultaneously in a shared manner; and output query results whenever any input query requires. In particular, MTopS supports two proposed algorithms, MTopBand and MTopList, which both incrementally maintain the top-k objects over time for multiple queries. As the foundation, we first identify the minimal object set from the data stream that is both necessary and sufficient for accurately answering all top-k queries in the workload. Then, the MTopBand algorithm is presented to incrementally maintain such minimum object set and eliminate the need for any recomputation from scratch. To further optimize MTop-Band, we design the second algorithm, MTopList which organizes the progressive top-k results of workload queries in a compact structure. MTopList is shown to be memory optimal and also more efficient in terms of CPU time usage than MTopBand. Our experimental study, using real data streams from domains of stock trades and moving object monitoring, demonstrates that both the efficiency and scalability of our proposed techniques are clearly superior to the state-of-the-art solutions.

Although various mining algorithms have been proposed in the literature to efficiently compute clusters, few strides have been made to date in helping analysts to interactively explore such patterns in the stream context. We present a framework called CLUES to both computationally and visually support the process of real-time mining of density-based clusters. CLUES is composed of three major components. First, as foundation of CLUES, we develop an evolution model of density-based clusters in data streams that captures the complete spectrum of cluster evolution types across streaming windows. Second, to equip CLUES with the capability of efficiently tracking cluster evolution, we design a novel algorithm to piggy-back the evolution tracking process into the underlying cluster detection process. Third, CLUES organizes the detected clusters and their evolution interrelationships into a multidimensional pattern space - presenting clusters at different time horizons and across different abstraction levels. It provides a rich set of visualization and interaction techniques to allow the analyst to explore this multi-dimensional pattern space in real-time. Our experimental evaluation, including performance studies and a user study, using real streams from ground group movement monitoring and from stock transaction domains confirm both the efficiency and effectiveness of our proposed CLUES framework.

Continuous top-k queries, which report a certain number (k) of top preferred objects from data streams, are important for a broad class of real-time applications, ranging from financial analysis to network traffic monitoring. Existing solutions for tackling this problem aim to reduce the computational costs by incrementally updating the top-k results upon each window slide. However, they all suffer from the performance bottleneck of periodically requiring a complete recomputation of the top-k results from scratch. Such an operation is not only computationally expensive but also causes significant memory consumption, as it requires keeping all objects alive in the query window. To solve this problem, we identify the "Minimal Top-K candidate set" (MTK), namely the subset of stream objects that is both necessary and sufficient for continuous top-k monitoring. Based on this theoretical foundation, we design the MinTopk algorithm that elegantly maintains MTK and thus eliminates the need for recomputation. We prove the optimality of the MinTopk algorithm in both CPU and memory utilization for continuous top-k monitoring. Our experimental study shows that both the efficiency and scalability of our proposed algorithm is clearly superior to the state-of-the-art solutions.

Data stream management systems (DSMS) processing long-running queries over large volumes of stream data must typically deliver time-critical responses. We propose the first semantic query optimization (SQO) approach that utilizes dynamic substream metadata at runtime to find a more efficient query plan than the one selected at compilation time. We identify four SQO techniques guaranteed to result in performance gains. Based on classic satisfiability theory we then design a lightweight query optimization algorithm that efficiently detects SQO opportunities at runtime. At the logical level, our algorithm instantiates multiple concurrent SQO plans, each processing different partially overlapping substreams. Our novel execution paradigm employs multi-modal operators to support the execution of these concurrent SQO logical plans in a single physical plan. This highly agile execution strategy reduces resource utilization while supporting lightweight adaptivity. Our extensive experimental study in the CAPE stream processing system using both synthetic and real data confirms that our optimization techniques significantly reduce query execution times, up to 60%, compared to the traditional approach.

Complex event processing (CEP) over event streams has become increasingly important for real-time applications ranging from health care, supply chain management to business intelligence. These monitoring applications submit complex queries to track sequences of events that match a given pattern. As these systems mature the need for increasingly complex nested sequence query support arises, while the state-of-art CEP systems mostly support the execution of flat sequence queries only. To assure real-time responsiveness and scalability for pattern detection even on huge volume high-speed streams, efficient processing techniques must be designed. In this paper, we first analyze the prevailing nested pattern query processing strategy and identify several serious shortcomings. Not only are substantial subsequences first constructed just to be subsequently discarded, but also opportunities for shared execution of nested subexpressions are overlooked. As foundation, we introduce NEEL, a CEP query language for expressing nested CEP pattern queries composed of sequence, negation, AND and OR operators. To overcome deficiencies, we design rewriting rules for pushing negation into inner subexpressions. Next, we devise a normalization procedure that employs these rules for flattening a nested complex event expression. To conserve CPU and memory consumption, we propose several strategies for efficient shared processing of groups of normalized NEEL subexpressions. These strategies include prefix caching, suffix clustering and customized “bit-marking” execution strategies. We design an optimizer to partition the set of all CEP subexpressions in a NEEL normal form into groups, each of which can then be mapped to one of our shared execution operators. Lastly, we evaluate our technologies by conducting a performance study to assess the CPU processing time using real-world stock trades data. Our results confirm that our NEEL execution in many cases performs 100 fold faster than the traditional iterative nested execution strategy for real stock market query workloads.

Given the nature of high volume streaming environments, not all tuples can be processed within the required response time. In such instances, it is crucial to dedicate resources to producing the most important results. We will demonstrate the Proactive Promotion Engine (PP) which employs a new preferential resource allocation methodology for priority processing of stream tuples. Our key contributions include: 1) our promotion continuous query language allows the specification of priorities within a query, 2) our promotion query algebra supports proactive promotion query processing, 3) our promotion query optimization locates an optimized PP query plan, and 4) our adaptive promotion control adapts online which subset of tuples are given priority online within a single physical query plan. Our “Portland Home Arrest” demonstration facilitates the capture of in-flight criminals using data generated by the Virginia Tech Network Dynamics and Simulation Science Laboratory via simulation-based modeling techniques.

Due to copyright restrictions, the access to the full text of this article is only available via subscription.

State-of-the-art Complex Event Processing technology (CEP), while effective for pattern query execution, is limited in its capability of reacting to opportunities and risks detected by pattern queries. Especially reactions that affect the query results in turn have not been addressed in the literature. We propose to tackle these unsolved problems by embedding active rule support within the CEP engine, henceforth called Active CEP (ACEP). Active rules in ACEP allow us to specify a pattern query's dynamic condition and real-time actions. The technical challenge is to handle interactions between queries and reactions to queries in the high-volume stream execution. We hence introduce a novel stream-oriented transactional model along with a family of stream transaction scheduling algorithms that ensure the correctness of concurrent stream execution. We demonstrate the power of ACEP technology by applying it to the development of a healthcare system being deployed in UMass Medical School hospital. Through extensive performance experiments using real data streams, we show that our unique Low-Water-Mark stream transaction scheduler, customized for streaming environments, successfully achieves near-real-time system responsiveness and gives orders-of-magnitude better throughput than our alternative schedulers.

Density-based cluster mining is known to serve a broad range of applications ranging from stock trade analysis to moving object monitoring. Although methods for efficient extraction of density-based clusters have been studied in the literature, the problem of summarizing and matching of such clusters with arbitrary shapes and complex cluster structures remains unsolved. Therefore, the goal of our work is to extend the state-of-art of density-based cluster mining in streams from cluster extraction only to now also support analysis and management of the extracted clusters. Our work solves three major technical challenges. First, we propose a novel multi-resolution cluster summarization method, called Skeletal Grid Summarization (SGS), which captures the key features of density-based clusters, covering both their external shape and internal cluster structures. Second, in order to summarize the extracted clusters in real-time, we present an integrated computation strategy C-SGS, which piggybacks the generation of cluster summarizations within the online clustering process. Lastly, we design a mechanism to efficiently execute cluster matching queries, which identify similar clusters for given cluster of analyst's interest from clusters extracted earlier in the stream history. Our experimental study using real streaming data shows the clear superiority of our proposed methods in both efficiency and effectiveness for cluster summarization and cluster matching queries to other potential alternatives.

Many modern applications including tag based mass transit systems, RFID-based supply chain management systems and online financial feeds require special purpose event stream processing technology to analyze vast amounts of sequential multi-dimensional data available in real-time data feeds. Traditional online analytical processing (OLAP) systems are not designed for real-time pattern-based operations, while Complex Event Processing (CEP) systems are designed for sequence detection and do not support OLAP operations. We will demonstrate a novel E-Cube model that combines CEP and OLAP techniques for multi-dimensional event pattern analysis at different abstraction levels. A London transit scenario will be given to demonstrate the utility and performance of this proposed technology.

Multi-criteria decision support (MCDS) is crucial in many business and web applications such as web searches, B2B portals and on-line commerce. Such MCDS applications need to report results early; as soon as they are being generated so that they can react and formulate competitive decisions in near real-time. The ease in expressing user preferences in web-based applications has made Pareto-optimal (skyline) queries a popular class of MCDS queries. However, state-of-the-art techniques either focus on handling skylines on single input sets (i.e., no joins) or do not tackle the challenge of producing progressive early output results. In this work, we propose a progressive query evaluation framework ProgXe that transforms the execution of queries involving skyline over joins to be non-blocking, i.e., to be progressively generating results early and often. In ProgXe the query processing (join, mapping and skyline) is conducted at multiple levels of abstraction, thereby exploiting the knowledge gained from both input as well as mapped output spaces. This knowledge enables us to identify and reason about abstract-level relationships to guarantee correctness of early output. It also provides optimization opportunities previously missed by current techniques. To further optimize ProgXe, we incorporate an ordering technique that optimizes the rate at which results are reported by translating the optimization of tuple-level processing into a job-sequencing problem. Our experimental study over a wide variety of data sets demonstrates the superiority of our approach over state-of-the-art techniques.

The federated database architecture has been introduced to maintain the autonomy of individual data sources yet accomplish federated task for diverse applications from traditional enterprises to computational sciences. We identify two challenging problems of query optimization in large-scale database federation systems. First, run-time conditions of data sources have a profound effect on the performance of database federations, yet the distributed environment of database federations makes it prohibitively expensive for the optimizer to gather rapidly fluctuating run-time conditions from remote data sources. Second, large-scale database federation systems are often widely distributed and built on heterogeneous networks, thus efficiently utilizing network resources is of ever increasing importance for query scheduling. In this paper, we propose to exploit the clustered hierarchical structure of database federations to solve these two problems. Our Cluster-and-Conquer strategy coordinates hierarchical clusters of data sources to optimize and process queries cooperatively. Within each cluster we employ an I/O-bound cost model with run-time conditions being accessible with relatively little delay. While among clusters a network-bound cost model is instead utilized to capture the network heterogeneity and optimize the query plans for efficient network utilization. The experimental study on the prototype database federation system with real-world network settings shows the effectiveness of our Cluster-and-Conquer strategy for scheduling data-intensive queries, as well as demonstrates the performance benefits of our proposed strategies over existing state-of-art solutions.

We demonstrate ProgXe, a practical approach to support Multi-Criteria Decision Support (MCDS) applications that need to report results as they are being generated to enable the user to make competitive decisions. ProgXe transforms the execution of MCDS queries involving skyline over joins to be non-blocking by progressively generating results early and often. The demonstration highlights key features of our progressive execution framework that optimizes for early output generation by: (1) evaluating the query at multiple levels of abstraction, (2) exploiting the skyline knowledge gained from both input as well as mapped output spaces. The audience will be able to submit MCDS queries. We provide visualization tools that enable the user to make quick decisions, compare alternative techniques, and provide capability to fine-tune the query predicates based on the early output results.

In many business and consumer applications, queries have cardinality constraints. However, current database systems provide minimal support for cardinality assurance. Consequently, users must adopt a cumbersome trial-and-error approach to find queries that are close to the original query but also attain the desired cardinality. In this demonstration, we present QRelX a novel framework to automatically generate alternate queries that meet the cardinality and closeness criteria. QRelX employs an innovative query space transformation strategy, proximity-based search and incremental cardinality estimation to efficiently find alternate queries. Our demonstration is an interactive game that allows the audience to compete with QRelX via manual query refinement. We illustrate the importance of cardinality assurance through real-time comparisons between manual refinement and QRelX. We also highlight the novelty of our solution by visualizing the core algorithms of QRelX.

We will demonstrate our system, called V iStream, supporting interactive visual exploration of neighbor-based patterns [7] in data streams. V iStream does not only apply innovative multi-query strategies to compute a broad range of popular patterns, such as clusters and outliers, in a highly efficient manner, but it also provides a rich set of visual interfaces and interactions to enable real-time pattern exploration. With ViStream, analysts can easily interact with pattern mining processes by navigating along the time horizons, abstraction levels and parameter spaces, and thus better understand the phenomena of interest.

Our analysis of many real-world event based applications has revealed that existing Complex Event Processing technology (CEP), while effective for efficient pattern matching on event stream, is limited in its capability of reacting in realtime to opportunities and risks detected or environmental changes. We are the first to tackle this problem by providing active rule support embedded directly within the CEP engine, henceforth called Active Complex Event Processing technology, or short, Active CEP. We design the Active CEP model and associated rule language that allows rules to be triggered by CEP system state changes and correctly executed during the continuous query process. Moreover we design an Active CEP infrastructure, that integrates the active rule component into the CEP kernel, allowing fine-grained and optimized rule processing. We demonstrate the power of Active CEP by applying it to the development of a collaborative project with UMass Medical School, which detects potential threads of infection and reminds healthcare workers to perform hygiene precautions in real-time.

Because of high volumes and unpredictable arrival rates, stream processing systems are not always able to keep up with input data - resulting in buffer overflow and uncontrolled loss of data. To produce eventually complete results, load spilling, which pushes some fractions of data to disks temporarily, is commonly employed in relational stream engines. In this work, we now introduce "structure-based spilling", a spilling technique customized for XML streams by considering the partial spillage of possibly complex XML elements. Such structure-based spilling brings new challenges. When a path is spilled, multiple paths may be affected. We analyze possible spilling effects on the query paths and how to execute the "reduced" query to produce partial results. To select the reduced query that maximizes output quality, we develop three optimization strategies, namely, OptR, OptPrune and ToX. We also examine the clean-up stage to guarantee that an entire result set is eventually generated by producing supplementary results. Our experimental study demonstrates that our proposed solutions consistently achieve higher quality results compared to the state-of-the-art techniques.

In real-life applications, different subsets of data may have distinct statistical properties, e.g., various websites may have diverse visitation rates, different categories of stocks may have dissimilar price fluctuation patterns. For such applications, it can be fruitful to eliminate the commonly made single execution plan assumption and instead execute a query using several plans, each optimally serving a subset of data with particular statistical properties. Furthermore, in dynamic environments, data properties may change continuously, thus calling for adaptivity. The intriguing question is: can we have an execution strategy that (1) is plan-based to leverage on all the benefits of traditional plan-based systems, (2) supports multiple plans each customized for different subset of data, and yet (3) is as adaptive as "plan-less" systems like Eddies? While the recently proposed Query Mesh (QM) approach provides a foundation for such an execution paradigm, it does not address the question of adaptivity required for highly dynamic environments. In this work, we fill this gap by proposing a Self-Tuning Query Mesh (ST-QM) --- an adaptive solution for content-based multi-plan execution engines. ST-QM addresses adaptive query processing by abstracting it as a concept drift problem --- a well-known subject in machine learning. Such abstraction allows to discard adaptivity candidates (i.e., the cases indicating a change in the environment) early in the process if they are insignificant or not "worthwhile" to adapt to, and thus minimize the adaptivity overhead. A unique feature of our aproach is that all logical transformations to the execution strategy get translated into a single inexpensive physical operation --- the classifier change. Our experimental evaluation using a continuous query engine shows the performance benefits of ST-QM approach over the alternatives, namely the non-adaptive and the Eddies-based solutions.

Multi-way stream joins with expensive join predicates lead to great challenge for real-time (or close to real-time) stream processing. Given the memory- and CPU-intensive nature of such stream join queries, scalable processing on a cluster must be employed. This paper proposes a novel scheme for distributed processing of generic multi-way joins with window constraints, called Pipelined State Partitioning (PSP). We target generic joins with arbitrarily join conditions, which are used in non-trivial stream applications such as image matching and biometric recognizing. The PSP scheme partitions the states into disjoint slices in the time domain, and then distributes the fine-grained states in the cluster, forming a virtual computation ring. Compared to replication-based distribution of non-equi-joins, PSP scheme is superior since: (1) zero state duplication and thus no repeated computations, (2) pipelined processing of every input tuple on multiple nodes to achieve low response time, and (3) cost-based adaptive workload distribution. We have implemented the proposed PSP schemes within the CAPE DSMS. Our experimental study demonstrates the significant performance improvements compared to the state-of-the-art generic distributed stream join algorithms.

The discovery of complex patterns such as clusters, outliers, and associations from huge volumes of streaming data has been recognized as critical for many domains. However, pattern detection with sliding window semantics, as required by applications ranging from stock market analysis to moving object tracking remains largely unexplored. Applying static pattern detection algorithms from scratch to every window is prohibitively expensive due to their high algorithmic complexity. This work tackles this problem by developing the first solution for incremental detection of neighbor-based patterns specific to sliding window scenarios. The specific pattern types covered in this work include density-based clusters and distance-based outliers. Incremental pattern computation in highly dynamic streaming environments is challenging, because purging a large amount of to-be-expired data from previously formed patterns may cause complex pattern changes including migration, splitting, merging and termination of these patterns. Previous incremental neighbor-based pattern detection algorithms, which were typically not designed to handle sliding windows, such as incremental DBSCAN, are not able to solve this problem efficiently in terms of both CPU and memory consumption. To overcome this, we exploit the "predictability" property of sliding windows to elegantly discount the effect of expiring objects on the remaining pattern structures. Our solution achieves minimal CPU utilization, while still keeping the memory utilization linear in the number of objects in the window. Our comprehensive experimental study, using both synthetic as well as real data from domains of stock trades and moving object monitoring, demonstrates superiority of our proposed strategies over alternate methods in both CPU and memory utilization.

Complex event processing has become increasingly important in modern applications, ranging from RFID tracking for supply chain management to real-time intrusion detection. A key aspect of complex event processing is to extract patterns from event streams to make informed decisions in real-time. However, network latencies and machine failures may cause events to arrive out-of-order at the event processing engine. State-of-the-art event stream processing technology experiences significant challenges when faced with out-of-order data arrival including output blocking, huge system latencies, memory resource overflow, and incorrect result generation. To address these problems, we propose two alternate solutions: aggressive and conservative strategies respectively to process sequence pattern queries on out-of-order event streams. The aggressive strategy produces maximal output under the optimistic assumption that out-of-order event arrival is rare. In contrast, to tackle the unexpected occurrence of an out-of-order event and with it any premature erroneous result generation, appropriate error compensation methods are designed for the aggressive strategy. The conservative method works under the assumption that out-of-order data may be common, and thus produces output only when its correctness can be guaranteed. A partial order guarantee (POG) model is proposed under which such correctness can be guaranteed. For robustness under spiky workloads, both strategies are supplemented with persistent storage support and customized access policies. Our experimental study evaluates the robustness of each method, and compares their respective scope of applicability with state-of-art methods.

We propose to demonstrate the StreamShield, a system designed to address the problem of security and privacy in the context of Data Stream Management Systems (DSMSs). In StreamShield, continuous access control is enforced by taking a novel "stream-centric" approach towards security. Security policies are not persistently stored on the server, but rather are depicted by security metadata, called "security punctuations", and get embedded into streams together with the data. We distinguish between two types of security punctuations: (1) the "data security punctuations" (dsps) describing the data-side security policies, and (2) the "query security punctuations" (qsps) representing the query-side security policies. The advantages of such stream-centric security model include flexibility, dynamicity and speed of enforcement. Furthermore, DSMSs can adapt to not only data-related but also to security-related selectivities, which helps reduce the waste of resources, when few subjects have access to streaming data.

This demonstration presents a complex event processing system which focuses on out-of-order handling. State-of-the-art event stream processing technology experiences significant challenges when faced with out-of-order data arrival including huge system latencies, missing results, and incorrect result generation. We propose two out-of-order handling techniques, conservative and aggressive strategies. We will show the efficiency of our techniques and how they can satisfy various QoS requirements of different applications.

In recent years, data streams have become ubiquitous as technology is improving and the prices of portable devices are falling, e.g., sensor networks, location-based services. Most data streams transmit only data tuples based on which continuous queries are evaluated. In this paper, we propose to enrich data streams with a new type of metadata called streaming tags or short tick-tags . The fundamental premise of tagging is that users can label data using uncontrolled vocabulary, and these tags can be exploited in a wide variety of applications, such as data exploration, data search, and to produce "enriched" with additional semantics, thus more informative query results. In this paper we focus primarily on the problem of continuous query processing with streaming tags and tagged objects, and address the tick-tag semantic issues as well as efficiency concerns. Our main contributions are as follows. First, we specify a general and flexible Stream Tag Framework (or short STF) that supports a stream-centric approach to tagging, and where tick-tags , attached to streaming objects are treated as first-class citizens. Second, under STF, users can query tags explicitly as well as implicitly by outputting the tags of the base data together with query results. Finally, we have implemented STF in a prototype Data Stream Management System, and through a set of performance experiments, we show that the cost of stream tagging is small and the approach is scalable to a large percentage of tagged objects.

We propose to demonstrate a practical alternative approach to the current state-of-the-art query processing techniques, called the " Query Mesh " (or QM , for short). The main idea of QM is to compute multiple routes (i.e., query plans), each designed for a particular subset of data with distinct statistical properties. Based on the execution routes and the data characteristics, a classifier model is induced and is used to partition new data tuples to assign the best routes for their processing. We propose to demonstrate the QM framework in the streaming context using our demo application, called the " Ubi-City ". We will illustrate the innovative features of QM , including: the QM optimization with the integrated machine learning component, the QM execution using the efficient " Self-Routing Fabric " infrastructure, and finally, the QM adaptive component that performs the online adaptation of QM with near-zero runtime overhead.

In diverse applications ranging from stock trading to traffic monitoring, popular data streams are typically monitored by multiple analysts for patterns of interest. These analysts may submit similar pattern mining requests, such as cluster detection queries, yet customized with different parameter settings. In this work, we present an efficient shared execution strategy for processing a large number of density-based cluster detection queries with arbitrary parameter settings. Given the high algorithmic complexity of the clustering process and the real-time responsiveness required by streaming applications, serving multiple such queries in a single system is extremely resource intensive. The naive method of detecting and maintaining clusters for different queries independently is often in-feasible in practice, as its demands on system resources increase dramatically with the cardinality of the query workload. To overcome this, we analyze the interrelations between the cluster sets identified by queries with different parameters settings, including both pattern-specific and window-specific parameters. We introduce the notion of the growth property among the cluster sets identified by different queries, and characterize the conditions under which it holds. By exploiting this growth property we propose a uniform solution, called Chandi , which represents identified cluster sets as one single compact structure and performs integrated maintenance on them -- resulting in significant sharing of computational and memory resources. Our comprehensive experimental study, using real data streams from domains of stock trades and moving object monitoring, demonstrates that Chandi is on average four times faster than the best alternative methods, while using 85% less memory space in our test cases. It also shows that Chandi scales in handling large numbers of queries on the order of hundreds or even thousands under high input data rates.

Continuous time-series sequence matching, specifically, matching a numeric live stream against a set of redefined pattern sequences, is critical for domains ranging from fire spread tracking to network traffic monitoring. While several algorithms exist for similarity matching of static time-series data, matching continuous data poses new, largely unsolved challenges including online real-time processing requirements and system resource limitations for handling infinite streams. In this work, we propose a novel live stream matching framework, called n-Snippet Indices Framework (in short, SNIF), to tackle these challenges. SNIF employs snippets as the basic unit for matching streaming time-series. The insight is to perform the matching at two levels of granularity: bag matching of subsets of snippets of the live stream against prefixes of the patterns, and order checking for maintaining successive candidate snippet bag matches. We design a two-level index structure, called SNIF index, which supports these two modes of matching. We propose a family of online two-level prefix matching algorithms that trade off between result accuracy and response time. The effectiveness of SNIF to detect patterns has been thoroughly tested through experiments using real datasets from the domains of fire monitoring and sensor motes. In this paper, we also present a study of SNIF's performance, accuracy and tolerance to noise compared against those of the state-of-the-art Continuous Query with Prediction (CQP) approach.

Detecting complex patterns in event streams, i.e., complex event processing (CEP), has become increasingly important for modern enterprises to react quickly to critical situations. In many practical cases business events are generated based on pre-defined business logics. Hence constraints, such as occurrence and order constraints, often hold among events. Reasoning using these known constraints enables us to predict the non-occurrences of certain future events, thereby helping us to identify and then terminate the long running query processes that are guaranteed to not lead to successful matches. In this work, we focus on exploiting event constraints to optimize CEP over large volumes of business transaction streams. Since the optimization opportunities arise at runtime, we develop a runtime query unsatisfiability (RunSAT) checking technique that detects optimal points for terminating query evaluation. To assure efficiency of RunSAT checking, we propose mechanisms to precompute the query failure conditions to be checked at runtime. This guarantees a constant-time RunSAT reasoning cost, making our technique highly scalable. We realize our optimal query termination strategies by augmenting the query with Event-Condition-Action rules encoding the pre-computed failure conditions. This results in an event processing solution compatible with state-of-the-art CEP architectures. Extensive experimental results demonstrate that significant performance gains are achieved, while the optimization overhead is small.

The management of privacy and security in the context of data stream management systems (DSMS) remains largely an unaddressed problem to date. Unlike in traditional DBMSs where access control policies are persistently stored on the server and tend to remain stable, in streaming applications the contexts and with them the access control policies on the real-time data may rapidly change. A person entering a casino may want to immediately block others from knowing his current whereabouts. We thus propose a novel ";stream-centric"; approach, where security restrictions are not persistently stored on the DSMS server, but rather streamed together with the data. Here, the access control policies are expressed via security constraints (called security punctuations, or short, sps) and are embedded into data streams. The advantages of the sp model include flexibility, dynamicity and speed of enforcement. DSMSs can adapt to not only data-related but also security-related selectivities, which helps reduce the waste of resources, when few subjects have access to data. We propose a security-aware query algebra and new equivalence rules together with cost estimations to guide the security-aware query plan optimization. We have implemented the sp framework in a real DSMS. Our experimental results show the validity and the performance advantages of our sp model as compared to alternative access control enforcement solutions for DSMSs.

XML stream applications bring the novel challenge of efficiently processing queries on sequentially accessible token-based input streams. Our Raindrop project is the first to accommodate token-based stream processing using an algebraic framework where both tokens and tuples are modeled in a uniform manner. In this paper, we illustrate how the stream loading model of our system on the fly conducts XML navigation over the input stream via concurrently constructing a minimized light-weight XML tree representation, which is called navigation-free data instance. These captured XML fragments are minimized in terms of buffer consumption. Based on the compact representation of the navigation-free data instances, we propose techniques for subsequent algebraic query evaluation, in particular, effective strategies for supporting multi-mode query operators and alternative data output semantics. The proposed stream loading model requires a much smaller buffer footprint, compared to alternative solutions in the literature such as Y-Filter. And the proposed algebra-based evaluation techniques offer effective ways to handle data recursion over XML streams, i.e., avoiding overhead from the structural join operators. Our stream loading and query evaluation techniques have been implemented as part of the Raindrop system. Experimental results based on the Raindrop system are also reported in this paper.

Because of the high volume and unpredictable arrival rate, stream processing systems may not always be able to keep up with the input data streams - resulting in buffer overflow and uncontrolled loss of data. Load shedding, the prevalent strategy for solving this overflow problem, has so far only been considered for relational stream processing, but not for XML. Shedding applied to XML stream processing brings new opportunities and challenges due to complex nested nature of XML structures. In this paper, we tackle this unsolved XML shedding problem using a three-pronged approach. First, we develop an XQuery preference model that enables users to specify the relative importance of preserving different subpatterns in the XML result structure. This transforms shedding into the problem of rewriting the user query into shed queries that return approximate query answers with utility as measured by the given user preference model. Second, we develop a cost model to compare the performance of alternate shed queries. Third, we develop two shedding algorithms, OptShed and FastShed. OptShed guarantees to find an optimal solution however at the cost of exponential complexity. FastShed, as confirmed by our experiments, achieves a close-to-optimal result in a wide range of test cases. Finally we describe the in-automaton shedding mechanism for XQuery stream engines. The experiments show that our proposed utility-driven shedding solutions consistently achieve higher utility results compared to the existing relational shedding techniques.

Queries issued by casual users or specialists exploring a dataset often point us to important subsets of the data, be it clusters, outliers or other meaningful features. Capturing and caching such queries (henceforth called nuggets) has many potential benefits, including the optimization of the system performance and the search experience of users. Unfortunately, current visual exploration systems have not yet tapped into this potential resource of identifying and sharing important queries. In this paper, we introduce a query consolidation strategy aimed at solving the general problem of isolating important queries from the potentially huge amount of queries submitted. Our solution clusters redundant queries caused by exploration-style query specification, which is prevalent in data exploration systems. To measure the similarity between queries, we designed an effective distance metric that incorporates both the query specification and the actual query result. To overcome its high complexity when comparing queries with large result sets, we designed an approximation method, which is efficient while still providing excellent accuracy. A user study conducted on multivariate data sets comparing our proposed technique to others in the literature confirms that the proposed distance metric indeed matches well with users' intuition. As proof of feasibility, we integrated our proposed query consolidation solution into the Nugget Management System (NMS) framework [22], which is based on a visual exploration system XmdvTool. A second user study indicates that both the efficiency and accuracy of users' visual exploration are enhanced when supported by NMS.

This demonstration presents FireStream, a sensor stream processing system which provides services for run-time detection, monitoring and visualization of fire spread in intelligent buildings that can be of great benefit to first responders. Our system can effectively handle large heterogeneous sensor streams using shared window execution and dynamic participant handling to yield a high-ary MJoin solution.

In this work, we describe our approach for making the interactive data exploration system, called XmdvTool, quality-aware to assure informed decision-making. XmdvToolQ, makes quality or lack thereof explicit for all stages of the data exploration process from raw data, to abstracted data, to the final visual displays, allowing users to query and navigate through data-, structure- and quality-spaces.

This paper describes a graphical data mining system called AutoDomainMine. It is based on our proposed approach of integrating clustering and classification to mine scientific data stored in a database. The data consists of input conditions of scientific experiments and graphs plotted as their results. This system mines the stored data in order to submit exact or approximate ranked responses to user queries intended to optimize the scientific processes.

In scientific domains, knowledge is often discovered from experiments by grouping or clustering them based on the similarity of their output. The causes of similarity are analyzed based on the input conditions characterizing a given type of output, i.e., a given cluster. This analysis helps in applications such as decision support in industry. Cluster representatives form at-a-glance depictions for such applications. Randomly selecting a set of conditions in a cluster as its representative is not sufficient since distinct combinations of inputs could lead to the same cluster. In this paper, an approach called DesCond is proposed to design semantics-preserving cluster representatives for scientific input conditions. We define a notion of distance for conditions to capture semantics based on the types of their attributes and their relative importance. Using this distance, methods of building candidate cluster representatives with different levels of detail are proposed. Candidates are compared using the DesCond Encoding proposed in this paper that assesses their complexity and information loss, given user interests. The candidate with the lowest encoding for each cluster is returned as its designed representative. DesCond is evaluated with real data from Materials Science. Evaluation with domain expert interviews and formal user surveys shows that designed representatives consistently outperform randomly selected ones and different candidates suit different users.

Materializing the contents of views has important applications including providing fast access to derived database repositories, optimizing query processing based on cached results, and increasing availability. Maintaining the consistency between materialized views and their base data in the presence of source updates is important to ensure that the materialized views are up-to-date. The straightforward solution for this problem is to recompute the view from scratch over the updated sources.

Both XML-relational systems and native XML systems support creating XML wrapper views and querying against them. However, update operations against such virtual XML views in most cases are not supported yet.

Main memory is a critical resource when processing long-running queries over data streams with state intensive operators. In this work, we investigate state spill strategies that handle run-time memory shortage when processing such complex queries by selectively pushing operator states into disks. Unlike previous solutions which all focus on one single operator only, we instead target queries with multiple state intensive operators. We observe an interdependency among multiple operators in the query plan when spilling operator states. We illustrate that existing strategies, which do not take account of this interdependency, become largely ineffective in this query context. Clearly, a consolidated plan level spill strategy must be devised to address this problem. Several data spill strategies are proposed in this paper to maximize the run-time query throughput in memory constrained environments. The bottom-up state spill strategy is an operator-level strategy that treats all data in one operator state equally. More sophisticated partition-level data spill strategies are then proposed to take different characteristics of the input data into account, including the local output, the global output and the global output with penalty strategies. All proposed state spill strategies have been implemented in the D-CAPE continuous query system. The experimental results confirm the effectiveness of our proposed strategies. In particular, the global output strategy and the global output with penalty strategy have shown favorable results as compared to the other two more localized strategies.

Data integration over multiple heterogeneous data sources has become increasingly important for modern applications. The integrated data is usually stored as materialized views to allow better access, performance, and high availability. In loosely coupled environments, such as the data grid, the data sources are autonomous. Hence, tie source updates can be concurrent and cause erroneous results during view maintenance. State-of-the-art maintenance strategies apply compensating queries to correct such errors, making the restricting assumption that all source schemata remain static over time. However, in such dynamic environments, the data sources may change not only their data but also their schema. Consequently, either the maintenance queres or the compensating queries may fail. In this paper, we propose a novel framework called DyDa that overcomes these limitations and handles both source data updates and schema changes. We identify three types of maintenance anomalies, caused by either source data updates, data-preserving schema changes, or non-data-preserving schema changes. We propose a compensation algorithm to solve the first two types of anomalies. We show that the third type of anomaly is caused by the violation of dependencies between maintenance processes. Then, we propose dependency detection and correction algorithms to identify and resolve the violations. Put together, DyDa extends prior maintenance solutions to solve all types of view maintenance anomalies. The experimental results show that DyDa imposes a minimal overhead on data update processing while allowing for the extended functionality to handle concurrent schema changes.

Materialized views defined over distributed data sources are critical for many applications to ensure efficient access, reliable performance, and high availability. Materialized views need to be maintained upon source updates since stale view extents may not serve well or may even mislead user applications. Thus, view maintenance performance is one of the keys to the success of these applications. In this work, we investigate two maintenance strategies, extended batching and view graph transformation, for maintaining general join views where join conditions may exist between any pairs of data sources possibly with cycles. Many choices are available for maintaining cyclic join views. We thus propose a cost-driven view maintenance framework which generates optimized maintenance plans tuned to the environmental settings. The proposed framework has been implemented in the TxnWrap system. Experimental studies illustrate that our proposed optimization techniques significantly improve the view maintenance performance in a distributed environment.

Efficient continuous query processing is critical for many applications, including monitoring remote sensors network traffic management, and online transaction processing. To overcome resource limitations and achieve real-time responsiveness, continuous query systems research focuses on issues such as punctuation-driven operator-state purging [4], load shedding, operator scheduling [7] and plan optimization and on-line migration [9]. However, when real-time yet accurate results are critical such as in stock market analysis, then there is a limitation to what any of the above optimization techniques can accomplish. Hence, distributed processing must be applied to support required scalability. It has been already proven in traditional database systems [3] that distributed processing results in high scale-up and speed-up capabilities due to aggregated resources. The design of a distributed continuous query system is characterized by an extra complexity, considered in the design of our D-Cape engine. In such a system, data streams may be infinite and initial cost statistics about the data streams are typically unknown. Moreover, cost statistics continue to change over time. Our research on distributed stream processing addresses two critical questions: (1) How to initially distribute query plans given little or possibly no cost information, and (2) How to efficiently adapt the query distribution corresponding to runtime environmental changes. Even though research is now under way in designing distributed continuous query systems [2], [1], results to date, as far as we know, are based on simulations. Our work offers empirical results of distributed continuous query processing using an actual software system [5], [6]. D-Cape, a distributed continuous query processing architecture, employs stream query engines over a cluster of shared-nothing processors. We employ a dedicated distribution manager to manage

Data warehousing and on-line analytical processing (OLAP) are essential for decision support applications. Common OLAP operations include for example drill down, roll up, pivot and unpivot. Typically, such queries are fairly complex and are often executed over huge volumes of data. The solution in practice is to use materialized views to reduce the query cost. Utilizing materialized views that incorporate not just traditional simple SELECT-PROJECT-JOIN operators but also complex OLAP operators such as pivot and unpivot is crucial to improve the OLAP query performance but as of now unexplored topic. In this work, we demonstrate that the efficient maintenance of views with pivot and unpivot operators requires the definition of more generalized operators, which we call GPIVOT and GUNPIVOT. We propose rewriting rules, combination rules and propagation rules for such operators. We also design a novel view maintenance framework for applying these rules to obtain an efficient maintenance plan. Our query transformation rules are thus dual purpose serving both view maintenance and query optimization. This paves the way for the inclusion of the GPIVOT and GUNPIVOT into any DBMS engine.

Maintaining materialized views that have join conditions between arbitrary pairs of data sources possibly with cycles is critical for many applications. In this paper, we model view maintenance as the process of answering a set of inter-related distributed multi-join queries. We illustrate two strategies for maintaining as well as optimizing such general join views. We propose a cost-driven view maintenance framework which generates optimized maintenance plans tuned to a given environmental settings. This framework can significantly improve view maintenance performance especially in a distributed environment.

Many applications, like materialized view maintenance and stream query processing, construct views incrementally over data sources. This results in computed pieces of objects that need to be merged by fusing corresponding objects together. This problem is challenging when dealing with XML data for many reasons including the hierarchical and semi-structured nature of XML data. Also XML query languages (e.g., XQuery) are capable of performing complex operations and transformations such as arbitrary nesting and result reconstruction. Moreover, since XML is an ordered data model, XML order has to be taken into consideration when constructing XML results incrementally. In this paper we study the problem of how to fuse XML pieces (fragments) generated by incrementally processing XML data into XML results. We consider an expressive subset of XQuery language transformations and propose an id-based solution for this problem that supports XML order. We prove the correctness of our approach, in particular that using our mechanism we can correctly yet incrementally merge XML result fragments. We have implemented our proposed semantic identifiers solution. Our experimental results show that it comes with a very small overhead to the query execution time.

Modern computer applications from business decision support to scientific data analysis use visualization techniques. However, visual exploration tools do not scale well for large data sets due to screen clutter. Visualization tools have thus been extended to support hierarchical views of the data, with support for focusing and drilling-down using interactive brushes. We now investigate how best to couple such a near real-time responsive visualization tool with database support. For this, we have developed a tree labeling method, called MinMax tree, that allows the movement of the on-line recursive processing of visual user interactions on hierarchical data sets into an off-line precomputation step. Using MinMax tree we map the recursive processing at the interface level to two dimensional range queries that can be answered efficiently using spatial indexes. We also employ caching and prefetching at the client side to cope with the real-time response requirements. The techniques have been incorporated into XmdvTool, a free software package for multi-variate data visualization and exploration. Our experimental results show 70% to 80% reduction in response time latency even with limited system resources.

Adaptive operator scheduling algorithms for continuous query processing are usually designed to serve a single performance objective, such as minimizing memory usage or maximizing query throughput. We observe that different performance objectives may sometimes conflict with each other. Also due to the dynamic nature of streaming environments, the performance objective may need to change dynamically. Furthermore, the performance specification defined by users may itself be multi-dimensional. Therefore, utilizing a single scheduling algorithm optimized for a single objective is no longer sufficient. In this paper, we propose a novel adaptive scheduling algorithm selection framework named AMoS. It is able to leverage the strengths of existing scheduling algorithms to meet multiple performance objectives. AMoS employs a lightweight learning mechanism to assess the effectiveness of each algorithm. The learned knowledge can be used to select the algorithm that probabilistically has the best chance of improving the performance. In addition, AMoS has the flexibility to add and adapt to new scheduling algorithms, query plans and data sets during execution. Our experimental results show that AMoS significantly outperforms the existing scheduling algorithms with regard to satisfying both uni-objective and multi-objective performance requirements.

The XML data is order-sensitive. The order problem, that is how ordered XML documents and order-sensitive queries over it can be efficiently supported when mapped into the unordered relational data model, has not yet been adequately addressed. In this paper, we present a general approach for supporting order-sensitive XQuery-to-SQL translation that works irrespective of the chosen XML-to-relational data mapping and the selected order-encoding method. Our approach, called XSOT, utilizes an order-aware XML algebra representation. We propose order-sensitive rewriting rules at the algebraic level to eliminate the dependency of the order determining operators on the implicit XML view order. Furthermore, we introduce a series of order-sensitive optimization steps to transform the XML algebra tree for the purpose of efficient SQL translation. Lastly, we utilize a template-based approach using SQL-99 order features to generate SQL statements.

Semantic caching is an important technology for improving the response time of future user queries specified over re-mote servers. This paper deals with the fundamental query containment problem in an XQuery-based semantic caching system. To our best knowledge, the impact of subtle dif-ferences in XQuery semantics caused by different ways of specifying variables on query containment has not yet been studied. We introduce the concept of variable binding de-pendencies for representing the hierarchical element depen-dencies preserved by an XQuery. We analyze the problem of XQuery containment in the presence of such dependencies. We propose a containment mapping technique for nested XQuery in presence of variable binding dependencies. The implication of the nested block structure on XQuery con-tainment is also considered. We mention the performance gains achieved by a semantic caching system we build based on the proposed technique.

We explore join optimizations in the presence of both time-based constraints (sliding windows) and value-based constraints (punctuations). We present the first join solution named PWJoin that exploits such combined constraints to shrink the runtime join state and to propagate punctuations to benefit downstream operators. We design a state structure for PWJoin that facilitates the exploitation of both constraint types. We also explore optimizations enabled by the interactions between window and punctuation, e.g., early punctuation propagation. The costs of the PWJoin are analyzed using a cost model. We also conduct an experimental study using CAPE continuous query system. The experimental results show that in most cases, by exploiting punctuations, PWJoin outperforms the pure window join with regard to both memory overhead and throughput. Our technique complements the joins in the literature, such as symmetric hash join or window join, to now require less runtime resources without compromising the accuracy of the result.

Materialized views defined over distributed data sources are a well recognized technology for modern applications. State-of the-art incremental view maintenance requires O(n2) or more maintenance queries to remote data sources with n being the number of data sources in the view definition. In this poster, we illustrate basic ideas of novel view maintenance strategies that dramatically reduce the number of maintenance queries. Such reduction brings the tradeoff between the number of maintenance queries and the complexity of each query. These algorithms have been implemented in a working prototype system. Experimental studies illustrate major performance improvement in terms of total processing time compared with existing batch algorithms.

Data integration over multiple heterogeneous data sources has become increasingly important for modern applications. The integrated data is usually stored in materialized views for high availability and better performance. Such views must be maintained after the data sources change. In a loosely-coupled and dynamic environment, such as the Data Grid, the sources may autonomously change not only their data but also their schema, query capabilities or semantics, which may consequently cause the ongoing view maintenance fail. We analyze the maintenance errors and classify them into different classes of dependencies. We then propose several dependency detection and correction algorithms to handle these new classes of concurrency. Our techniques are not tied to specific maintenance algorithms nor to a particular data model. To our knowledge, this is the first complete solution to the view maintenance concurrency problems for both data and schema changes. We have implemented the proposed solutions and experimentally evaluated the impact of anomalies on maintenance performance and trade-offs between different dependency detection algorithms.

Dynamic plan migration is concerned with the on-the-fly transition from one continuous query plan to a semantically equivalent yet more efficient plan. Migration is important for stream monitoring systems where long-running queries may have to withstand fluctuations in stream workloads and data characteristics. Existing migration methods generally adopt a pause-drain-resume strategy that pauses the processing of new data, purges all old data in the existing plan, until finally the new plan can be plugged into the system. However, these existing strategies do not address the problem of migrating query plans that contain stateful operators, such as joins. We now develop solutions for online plan migration for continuous stateful plans. In particular, in this paper, we propose two alternative strategies, called the moving state strategy and the parallel track strategy, one exploiting reusability and the second employs parallelism to seamlessly migrate between continuous join plans without affecting the results of the query. We develop cost models for both migration strategies to analytically compare them. We embed these migration strategies into the CAPE [7], a prototype system of a stream query engine, and conduct a comparative experimental study to evaluate these two strategies for window-based join plans. Our experimental results illustrate that the two strategies can vary significantly in terms of output rates and intermediate storage spaces given distinct system configurations and stream workloads.

The integration of data, especially from heterogeneous sources, is a hard and widely studied problem. One particularly challenging issue is the integration of sources that are semantically equivalent but schematically heterogeneous. While two such data sources may represent the same information, one may store the information inside tuples (data) while the other may store it in attribute or relation names (schema). The SchemaSQL query language is a recent solution to this problem powerful enough to restructure such sources into each other without the loss of information. We propose the first incremental view maintenance strategy for such schema-restructuring views. Our strategy, based on an algebraic representation of the view query, correctly transforms a data update or a schema change to a source into sequences of schema and data updates to be applied to the view. We also introduce an optimization of incremental maintenance using batching. We present a proof of correctness of the propagation approach. We also describe the implementation of our SchemaSQL Query Processor and View Maintainer. Last, our experimental results demonstrate that, in many cases, incremental SchemaSQL view maintenance is significantly faster than complete view recomputation.

Materialized views can be maintained by submitting maintenance queries to the data sources. However, the query results may be erroneous due to concurrent source updates. State-of-the-art maintenance strategies typically apply compensations to resolve such conflicts and assume all source schemata remain stable over time. In a loosely coupled dynamic environment, the sources may autonomously change not only their data but also their schema or semantics. Consequently, either the maintenance or the compensation queries may be broken. Unlike compensation-based approaches found in the literature, we instead model the complete materialized view maintenance process as a view maintenance transaction (VM_Transaction). This way, the anomaly problem can be rephrased as the serializability of VM_Transactions. To achieve VM_Transaction serializability, we propose a multiversion concurrency control algorithm, called TxnWrap , which is shown to be the appropriate design for loosely coupled environments with autonomous data sources. TxnWrap is complementary to the maintenance algorithms proposed in the literature, since it removes concurrency issues from consideration allowing the designer to focus on the maintenance logic. We show several optimizations of TxnWrap, in particular, (1) space optimizations on versioned data materialization and (2) parallel maintenance scheduling. With these optimizations, TxnWrap even outperforms state-of-the-art view maintenance solutions in terms of refresh time. Further, several design choices of TxnWrap are studied each having its respective advantages for certain environmental settings. A correctness proof based on transaction theory for TxnWrap is also provided. Last, we have implemented TxnWrap. The experimental results confirm that TxnWrap achieves predictable performance under a varying rate of concurrency.

Effective indexing for XML must consider both the query requirements of the XPath language and the dynamic nature of XML. We introduce MASS, a Multiple Axis Storage Structure, to provide scalable indexing for XPath expressions with guaranteed update performance. We describe the building blocks of MASS and provide results that demonstrate MASS's scalability. We show that MASS can outperform other state-of-the-art XML indexing solutions, even with constrained system resources.

XML stream applications bring the challenge of efficiently processing queries on sequentially accessible token-based data. While the automata model is naturally suited for pattern matching on tokenized XML streams, the algebraic model in contrast is a well-established technique for set-oriented processing of self-contained tuples. However, neither automata nor algebraic models are well-equipped to handle both computation paradigms.

Integration of multiple heterogeneous data sources continues to be a critical problem for many application domains and a challenge for researchers world-wide. One aspect of integration is the translation of schema and data across data model boundaries. Researchers in the past have looked at both customized algorithmic approaches as well as generic meta-modeling approaches as viable solutions. We now take the meta-modeling approach the next step-forward. In this paper we propose a flexible, extensible and re-usable transformation modeling framework which allows users to (1) model their transformations; (2) to choose from a set of possible execution strategies to translate the underlying schema and data; and (3) to access and re-use a library of transformation generators. In this paper we present the core of our modeling framework - a set of cross algebra operators that covers the class of linear transformations, and two different techniques of composing these operators into larger transformation expressions. We also present an evaluation strategy to execute the modeled transformation, and thereby transform the input schema and data into the target schema and data assuming that data model wrappers are provided for each data model. The proposed framework has been implemented, and we give an overview of this prototype system.

Modern computer applications, from business decision support to scientific data analysis, utilize data visualization tools to support exploratory activities. Visual exploration tools typically do not scale well when applied to huge data sets, partially because being interactive necessitates real-time responses. However, we observe that interactive visual explorations exhibit several properties that can be exploited for data access optimization, including locality of exploration, contiguous queries, and significant delays between user operations. We thus apply semantic caching of active query sets on the client side to exploit some of the above characteristics. We also introduce several prefetching strategies, each exploiting characteristics of our visual exploration environment. We have incorporated caching and prefetching strategies into XmdvTool, a public-domain tool for visual exploration of multivariate data sets. Experimental studies using synthetic as well as real user traces are conducted. Our results demonstrate that these proposed optimization techniques achieve significant performance improvements in our exploratory analysis system.

Determining relationships such as functional or inclusion dependencies within and across databases is important for many applications in information integration. When such information is not available as explicit meta data, it is possible to discover potential dependencies from the source database extents. However, the complexity of such discovery problems is typically exponential in the number of attributes. We have developed an algorithm for the discovery of inclusion dependencies across high-dimensional relations in the order of 100 attributes. This algorithm is the first to efficiently solve the inclusion-dependency discovery problem. This is achieved by mapping it into a progressive series of clique-finding problems in k-uniform hypergraphs and solving those. Extensive experimental studies confirm the algorithm's efficiency on a variety of real-world data sets.

No abstract available.

Accessing data stored in persistent memory represents a bottleneck for current visual exploration applications. Semantic caching of frequent queries at the client-side along with prefetching can improve performance of such systems. However, a prefetching setup that only uses one prefetching strategy may be insufficient because (1) different users have different exploration patterns, and (2) a user's pattern may be changing within the same session. To solve this, existing research focuses on refining a single prefetching strategy. We, on the other hand, now propose a framework wherein prefetching strategies are adaptively selected over time across and within one user session. This work is the first to study adaptive prefetching in the context of visual data exploration. Specifically, we have implemented our proposed approach within XmdvTool, a freeware visualization system for multivariate data, and evaluated it using real user traces. Our results confirm that our approach improves system performance by dynamically selecting the most appropriate combination of prefetching strategies that adapts to the user's changing patterns.

Data warehouse view maintenance is an important issue due to the growing use of warehouse technology for information integration and data analysis. Given the dynamic nature of modern distributed environments, both data updates and schema changes are likely to occur in different data sources. In applications that the real-time refreshment of data warehouse extent under source changes is not critical, the source updates are usually maintained in a batch fashion to reduce the maintenance overhead. However, most prior work can only deal with batch source data updates. In this paper, we provide a solution strategy that is capable of batching both source data updates and schema changes. We propose techniques to first preprocess the initial source updates to summarize delta changes for each source. We then design a view adaptation algorithm to adapt the warehouse view under these delta changes. We have implemented our solutions and incorporated into an existing data warehouse prototype system. The experimental studies demonstrate excellent performance achievable by our batch techniques.

A wide range of Web applications retrieve desired information from remote XML data sources across the Internet, which is usually costly due to transmission delays for large volumes of data. Therefore we propose to apply the ideas of semantic caching to XML query processing systems [2], in particular the XQuery engine. Semantic caching [3] implies view-based query answering and cache management. While it is well studied in the traditional database context, query containment for XQuery is left unexplored due to its complexity coming with the powerful expressiveness of hierarchy, recursion and result construction. We hence have developed the first solution for XQuery processing using cached views.We exploit the connections between XML and tree automata, and use subtype relations between two regular expression types to tackle the XQuery containment mapping problem. Inspired by XDuce [1], which explores the use of tree-automata-based regular expression types for XML processing, we have designed a containment mapping process to incorporate type inference and subtyping mechanisms provided by XDuce to establish containment mappings between regular-expression-type-based pattern variables of two queries. We have implemented a semantic caching system called XCache (see Figure 1), to realize the proposed containment and rewriting techniques for XQuery.The main modules of XCache include: (1) Query Decomposer. An input query is is decomposed into source-specific subqueries explicitly represented by matching patterns and return structures. (2) Query Pattern Register. By registering a few queries into semantic regions, we warm up XCache at its initialization phase. (3) Query Containment Mapper. The XDuce subtyper is incorporated into the containment mapper for establishing query containment mappings between variables of a new query and each cached query. (4) Query Rewriter. We implement the classical bucket algorithm and further apply heuristics to decide on an "optimal" rewriting plan if several valid ones exist. (5) Replacement Manager. We free space for new regions by both complete and partial replacement. (6) Region Coalescer. We apply a coalescing strategy to control the region granularity over time.

No abstract available.

The construction and maintenance of data warehouses (views) in large-scale environments composed of numerous distributed and evolving information sources (ISs) such as the WWW has received great attention recently. Such environments are plagued with changing information because ISs tend to continuously evolve by modifying not only their content but also their query capabilities and interface and by joining or leaving the environment at any time. We are the first to introduce and address the problem of schema changes of ISs, while previous work in this area, such as incremental view maintenance, has mainly dealt with data changes at ISs. We outline our solution approach to this challenging new problem of how to adapt views in such evolving environments. We identify a new view adaptation problem for view evolution in the context of ISs schema changes, which we call view synchronization. We also outline the Evolvable View Environment (EVE) approach that we propose as framework for solving the view synchronization problem, along with our decisions concerning the key design issues surrounding EVE. The main contributions of this paper are: 1) we provide an E-SQL view definition language with which the view definer can direct the view evolution process, 2) we introduce a model for information source description which allows a large class of ISs to participate in our system dynamically, 3) we formally define what constitutes a legal view rewriting, 4) we develop replacement strategies for affected view components which are designed to meet the preferences expressed by E-SQL, 5) we prove the correctness of the replacement strategies, and 6) we provide a set of view synchronization algorithms based on those strategies. A prototype of our EVE system has successfully been built using Java, JDBC, Oracle, and MS Access.

Modern ad-hoc data mining queries often run on databases over a terabyte in size. At this scale, large data pages are required to obtain sufficient disk performance. Unfortunately, these large data pages greatly increase update costs, especially for packed structures such as the B+ tree. In a frequently updated warehouse, users are often forced to decide between query performance and update performance in order to meet maintenance time windows. Solutions that provide both are welcome.In this paper, we analyze and measure the memory related costs of B+ Tree updates with large data pages. We introduce the RB+ (Red-Black+) tree as a practical replacement for the B+ tree. The RB+ tree uses persistent red-black binary trees instead of sorted records for leaf pages. This organization improves memory performance up to 3,000% for updates and provides query performance comparable to a B+ tree, making it practical for large, frequently updated warehouses.

No abstract available.

The need to provide effective tools for analyzing and querying spatial data is becoming increasingly important with the explosion of data in applications such as geographic information systems, image databases, CAD, and remote sensing. The SEE (Spatial Exploration Environment) is the first effort at applying direct-manipulation visual information seeking (VIS) techniques to spatial data analysis by visually querying as well as browsing spatial data and reviewing the visual results for trend analysis. The SEE system incorporates a visual query language (SVIQUEL) that allows users to specify the relative spatial position (both topology and direction) between objects using direct manipulation. The quantitative SVIQVEL sliders (S-sliders) are complemented by the qualitative active-picture-for-querying (APIQ) interface that allows the user to specify qualitative relative position queries. APIQ provides qualitative visual representations of the quantitative query specified by the S-sliders. This increases the utility of the system for spatial browsing and spatial trend discovery with no particular query in mind. The SVIQUEL queries are processed using a k-Bucket index structure specifically tuned for incremental processing of the multidimensional range queries that represent the class of queries that can be expressed by SVIQUEL. We have also designed a tightly integrated map visualization that helps to preserve the spatial context and a bar visualization that provides a qualitative abstraction of aggregates.

No abstract available.

Powerful solutions enabling interoperability must allow applications to evolve and the requirements of shared databases to change, while minimizing such changes on other integrated applications. Several approaches have been proposed to make interoperability possible by using object-oriented techniques. These approaches may generate a large number of schema versions over time, resulting in an excessive build-up of classes and underlying object instances, not all being necessarily still in use. This results in degradation of system performance due to the view maintenance and the storage overhead costs. In this paper, we address the problem of removing obsolete view schemas. We characterize four potential problems of schema consistency that could be caused by the removal of a single derived class. We demonstrate that schema version removal is sensitive to the order in which individual classes are processed, and present a formal dependency model that captures all dependencies between classes as logic clauses and manipulates them to make decisions on class deletions and non-deletions while guaranteeing the consistency of the schema. We have also developed and proven consistent a dependency graph (DG) representation of the formal model. Lastly, we present a cost model for evaluating alternative removal patterns on a DG to assure selection of the optimal solution. The proposed techniques have been implemented in our Schema View Removal (SVR) tool. Lastly, we report experimental findings for applying our techniques for consistent schema version removal on the MultiView/TSE (Transparent Schema Evolution) system.

Some of the most recently proposed algorithms for the incremental maintenance of materialized data warehouses (DW), such as SWEEP and PSWEEP, offer several significant advantages over previous solutions, such as high-performance, no potential for infinite waits and reduced remote queries and thus reduced network and information source (IS) loads. However, similar to many other algorithms, they still have the restricting assumption that each IS can be composed of just one single relation. This is unrealistic in practice. In this paper, we hence propose a solution to overcome this restriction. The Multi-Relation Encapsulation (MRE) Wrapper supports multiple relations in ISs in a manner transparent to the rest of the environment. The MRE Wrapper treats one IS composed of multiple relations as if it were a single relation from the DW point of view; thus any existing incremental view maintenance algorithms can now be applied even to such complex ISs without any changes. Hence, our method maintains all advantages offered by existing algorithms in particular SWEEP and PSWEEP, while also achieving the additional desired features of being non-intrusive, efficient, flexible and well-behaved.

Query rewriting with relaxed semantics has been proposed as a means of retaining the validity of a data warehouse (i.e., materialized queries) in a changing environment. Attributes in the query interface can be classified as essential or dispensable (if it cannot be retained) according to the query definer's preferences. Similarly, preferences for query extent can be specified, for example, to indicate whether a subset of the original result is acceptable or not. The paper discusses the trade-off between quality and cost of query rewriting.

Summary form only given. Data warehouses (DW) are built by gathering information from several information sources (IS) and integrating it into one repository customized to users' needs. ISs are typically owned by different information providers and hence are independent and autonomous. This implies they will update their data and schemas independently and without any concern for how this may affect the DW defined upon them. Hence, solutions for data warehouse maintenance are needed that can handle such IS updates. We have developed a first comprehensive solution that successfully tackles this problem (X. Zhang et al., 1998). In particular, to guarantee the correctness of concurrent view definition evolution and view extent maintenance of a data warehouse, we introduce a framework called the SDCC (Schema change and Data update Concurrency Control) system. SDCC integrates various algorithms designed to address different individual view maintenance subproblems into one system, such as algorithms for view extent maintenance after IS data updates, for view definition evolution after IS schema changes, and for view extent adaptation after view definition changes.

While current view technology assumes that information systems (ISs) do not change their schemas, our Evolvable View Environment (EVE) project addresses this problem by evolving the view definitions affected by IS schema changes, which we call view synchronization. In EVE, the view synchronizer rewrites the view definitions by replacing view components with suitable components from other ISs. However, after such a view redefinition process, the view extents, if materialized, must also be brought up to date. In this paper, we propose strategies to address this incremental adaptation of the view extent after view synchronization. One key idea of our approach is to regard the complex changes done to a view definition after synchronization as an atomic unit; another is to exploit knowledge of how the view definition was synchronized, especially the containment information between the old and new views. Our techniques would successfully adapt views under the unavailability of base relations, while currently known maintenance strategies from the literature would fail.

Recently proposed view maintenance algorithms tackle the problem of concurrent data updates happening at different autonomous information systems (ISs), whereas the EVE (Evolvable View Environment) system addresses the maintenance of a data warehouse (DW) after IS schema changes. The concurrency of schema changes and data updates still remains an unexplored problem, however. This paper provides a solution that guarantees concurrent view definition evolution and view extent maintenance of a DW defined over distributed ISs. For this problem, we introduce a framework called SDCC (Schema change and Data update Concurrency Control) system. SDCC integrates existing algorithms designed to address view maintenance subproblems (such as view extent maintenance after IS data updates, view definition evolution after IS schema changes, and view extent adaptation after view definition changes) into one system by providing protocols that enable them to correctly co-exist and collaborate. SDCC tracks any potential faulty updates of the DW caused by conflicting concurrent IS changes, and compensates for such conflicting updates by a local correction strategy called local compensation.

Supporting independent ISs and integrating them in distributed data warehouses (materialized views) is becoming more important with the growth of the WWW. However, views defined over autonomous ISs are susceptible to schema changes. In the EVE project we are developing techniques to support the maintenance of data warehouses defined over distributed dynamic ISs [5, 6, 7]. The EVE system is the first to allow views to survive schema changes of their underlying ISs while also adapting to changing data in those sources. EVE achieves this is two steps: applying view query rewriting algorithms that exploit information about alternative ISs and the information they contain, and incrementally adapting the view extent to the view definition changes. Those processes are referred to as view synchronization and view adaption, respectively. They increase the survivability of materialized views in changing environments and reduce the necessity of human interaction in system maintenance.

Article SERF: schema evolution through an extensible, re-usable and flexible framework Share on Authors: Kajal T. Claypool Department of Computer Science, Worcester Polytechnic Institute, Worcester, MA Department of Computer Science, Worcester Polytechnic Institute, Worcester, MAView Profile , Jing Jin Department of Computer Science, Worcester Polytechnic Institute, Worcester, MA Department of Computer Science, Worcester Polytechnic Institute, Worcester, MAView Profile , Elke A. Rundensteiner Department of Computer Science, Worcester Polytechnic Institute, Worcester, MA Department of Computer Science, Worcester Polytechnic Institute, Worcester, MAView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 314–321https://doi.org/10.1145/288627.288672Online:01 November 1998Publication History 39citation359DownloadsMetricsTotal Citations39Total Downloads359Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Material&d views (data warehouses) are becoming increasingly important in the context of distributed modem environments such as the World Wide Web.Information sources (I%) in such an environment may change their capabilities (schema), causing a data warehouse to become undefined.This process to evolve (rewrite) view queries after capability changes of ISs is referred to ss view synchronization.Current view synchronization algorithms generate a potentially large number of valid solutions for the rewriting of a view query and according to our analysis in this paper have high complexity (in O(n!)).We propose to reduce this complexity by representing the synchronization problem as a graph traversal problem.Once this mapping has been applied, the problem can be reduced to a single-source shortestpath problem in graphs, which can be solved with O(n3) complexity using the Bellman-Ford algorithm.

We have developed a MultiMedia Visual Information Seeking (MMVIS) Environment designed to support an integrated approach to direct manipulation temporal querying and browsing of temporal relationship results. We address the optimization of queries specified via our visual query interface. Queries in MMVIS are incrementally specified and continuously refined multidimensional range queries. We present our k-Array index structure and its bucket based counterpart, the k-Bucket, as new indexes optimized for processing these direct manipulation queries. In an experimental evaluation comparing our k-Array and k-Bucket solutions to alternate techniques from the literature, we show that the k-Bucket performs generally equal to or better than the other techniques and is the best overall approach for such environments.

This paper presents a paradigm for the interactive selection (querying) of data from a structured grid of data points for exploratory visualization. The paradigm is based on specifying and iteratively adjusting the Focus, Extent, and Density (FED) of the data attributes. The FED model supports highly complex queries of structured data in an intuitive fashion, and is augmented with a visual interface composed of a set of simple yet powerful user interface controls for query specification. In addition, statistical aggregations are supported by the model. Finally, the FED model is compared to the SQL paradigm, and is shown to be well suited for mapping to a direct-manipulation graphical interface.

Challenging issues for processing queries specified over large-scale information spaces (e.g., Digital Libraries or the World Wide Web) include the diversity of the information sources in terms of their structures, query interfaces and search capabilities, as well as the dynamics of sources continuously being added, removed or upgraded. In this paper, we give an innovative solution for query planning in such environments. The foundation of our solution is the Dynamic Information Integration Model (DIIM) which supports the specification of not only content but also capabilities of resources without requiring the establishment of a uniform integration schema. Besides the development of the DIIM model, contributions of this paper include: (1) the introduction of the notion of fully specified queries that are semantically equivalent to a loosely-specified query; (2) a translation algorithm of a loosely-specified query into a set of semantically equivalent feasible query plans that are consistent with the binding patterns of query templates of the individual sources (capability descriptions in DIIM) and with interrelationships between informations sources (expressed as join constraints in DIIM); and (3) a search restriction algorithm for optimizing query processing by pruning the search space into the relevant subspace of a query. The plans obtained by the proposed query planning process which is composed of the search restriction and translation algorithms can be shown to correspond to query plans semantically equivalent to the initial loosely-specified input query.

Efficient path computation is essential for applications such as intelligent transportation systems (ITS) and network routing. In ITS navigation systems, many path requests can be submitted over the same, typically huge, transportation network within a small time window. While path precomputation (path view) would provide an efficient path query response, it raises three problems which must be addressed: 1) precomputed paths exceed the current computer main memory capacity for large networks; 2) disk-based solutions are too inefficient to meet the stringent requirements of these target applications; and 3) path views become too costly to update for large graphs (resulting in out-of-date query results). We propose a hierarchical encoded path view (HEPV) model that addresses all three problems. By hierarchically encoding partial paths, HEPV reduces the view encoding time, updating time and storage requirements beyond previously known path precomputation techniques, while significantly minimizing path retrieval time. We prove that paths retrieved over HEPV are optimal. We present complete solutions for all phases of the HEPV approach, including graph partitioning, hierarchy generation, path view encoding and updating, and path retrieval. In this paper, we also present an in-depth experimental evaluation of HEPV based on both synthetic and real GIS networks. Our results confirm that HEPV offers advantages over alternative path finding approaches in terms of performance and space efficiency.

View materialization is a promising technique for achieving the data sharing and virtual restructuring capabilities needed by advanced applications such as data warehousing and workflow management systems. Much existing work addresses the problem of how to maintain the consistency of materialized relational views under update operations. However, little progress has been made thus far regarding the topic of view materialization in object-oriented databases (OODBs). In this paper, we demonstrate that there are several significant differences between the relational and object-oriented paradigms that can be exploited when addressing the object-oriented view materialization problem. First, we propose techniques that prune update propagation by exploiting knowledge of the subsumption relationships between classes to identify branches of classes to which we do not need to propagate updates and by using derivation ordering to eliminate self-cancelling propagation. Second, we use encapsulated interfaces, combined with the fact that any unique database property is inherited from a single location, to provide a "registration service" by which virtual classes can register their interest in specific properties and be notified upon modification of those properties. Third, we introduce the notion of hierarchical registrations that further optimizes update propagation by organizing the registration structures according to the class generalization hierarchy, thereby pruning the set of classes that are notified of updates. We have successfully implemented all proposed techniques in the MultiView system on top of the GemStone OODBMS. To the best of our knowledge, MultiView is the first OODB view system to provide updatable materialized virtual classes and virtual schemata. In this paper, we also present a cost model for our update algorithms, and we report results from the experimental studies we have run on the MultiView system, measuring the impact of various optimization strategies incorporated into our materialization update algorithms.

In many design applications, it is common practice to store corn-pfex hierarchical objects in a compactfolded form to save storage space and to reduce processing costs for accessing the objects.In these folded representations, complex objects are built up from identical and otherwise indistinguishable objects.Howevec it is o&en necessary, especially during the refinement of data, to distinguish between these identicul forCtd objects by personakkg a subset of them.The established practice is IO eqficitfy unfold the hierarchical objects and thus create space in which to store distinct personalization data for each object occurrence.However, this explicit unfolding is costly and time consuming, resulting in a potentiaZfy much larger structure, and substantially increasing the costs of querying and updating the design.Therefore, we propose an unfold operator that supports access to data in a virtua& Unfolded view.We describe how to updare customized values for each hierarchical sub-object through the unfolded view.We propose alternative strategies for the maintenance of personalization values, representing various portions of the view materialization spectrutn.We present a performance evaluation comparing these strategies as well as the traditional explicit unfolding approach.Our evaluation indicates the trade-ofi inn.terms of storage and query costs and compares the costs to do implicit unfolding Jhrough a view rather than explicit unfolding of compkx hierarchical objects. Iutroductiou and Probiem DescriptionIntroduction.An increasing number of applications must be able to store, query, and retrieve complex hierarchical objects.Objects containing repeated subparts can be represented compactly by folding them along a part-of relationship, using multiple references to identical subparts instead of repIic%ing fiem.In the folded implementation occurrence paths represent distinct objects impIicitfy, rather than through explicit object instances.For example, Figure I(a) shows a stack of cubes cl and ~2, each containing 6 faces.The bottom face of cube cl is represented by the occurrence path cl: :bottam Similarly, each of the.16 full-adders (FA) in the object of Figure l(b) exists as a path, e.g., a3 : : f 3. Folded hierarchical objects are a powerful construct used in many domains such as mechanical and electronic design, genome databases, and graphical applications.During the design process a user eventually requires an unfolded view of the data.While OODB systems can represent folded hierarchical structures, they do not explicitly model the semantics of the folding relationship.As a consequence the data-

Investigates optimization strategies for processing path queries with embedded spatial constraints, such as avoiding areas with certain characteristics. To resolve complex spatial constraints during path finding, we consider two decisions: (1) the spatial relation operations (e.g. intersection) between areas and links can be pre-processed or intermixed with path-finding, and (2) areas satisfying the query constraint can be pre-filtered or dynamically selected during path-finding. Based on these two decisions, we propose and implement the resulting four integrated query processing strategies, utilizing state-of-the-art technologies such as spatial joins for intersect computation, R-tree access structure for spatial overlap searching, and spatial clustering for efficient path searching. In this paper, we also report an experimental evaluation to show which strategies perform best in different scenarios.

The development of a cost model for predicting the performance of spatial joins has been identified in the literature as an important and difficult problem. The authors present the first cost model that can predict the performance of spatial joins using R-trees. Based on two existing R-trees (join targets), the model first estimates the number of expected I/Os for the join process by assuming a zero buffer size. The method for this estimation extends the cost model for R-tree window queries (developed by Kamel and Faloutsos (1993) and by Pagel et al. (1993)) to also handle spatial joins (which are more complex). In the context of spatial join processing, this number of zero-buffer expected I/Os is not practical for performance prediction in a buffered environment. To model the buffer impact, they use an (exponential) distribution function to measure the probability that a bufferless I/O would cause a page fault in a buffered environment. Based on this probability and the zero-buffer expected I/O cost, the estimated number of I/Os for an R-tree join can then be computed. The comparisons between the predictions from the cost model and the actual results from the experiments based on real GIS maps show that the average relative error ratio is about 10% with a maximum of about 20% for a wide range of buffer sizes. Therefore, our model is a useful tool for the query optimization of spatial join queries.

Challenging issues for processing queries specified over large-scale information spaces (for example, Digital Libraries or the World Wide Web) include the diversity of the information sources in terms of their structures, query interfaces and search capabilities, as well as the dynamics of sources continuously being added, removed or upgraded. In this paper, we give an innovative solution for query planning in such environments. The foundation of our solution is the Dynamic Information Integration Model (DIIM) which supports the specification of not only content but also capabilities of resources without requiring the establishment of a uniform integration schema. Besides the development of the DIIM model, contributions of this paper include: (1) the introduction of the notion of fully specified queries that are semantically equivalent to a loosely-specified query; (2) a translation algorithm of a loosely-specified query into a set of semantically equivalent feasible query plans that are consistent with the binding patterns of query templates of the individual sources (capability descriptions in DIIM) and with interrelationships between information sources (expressed as join constraints in DIIM); and (3) a search restriction algorithm for optimizing query processing by pruning the search space into the relevant subspace of a query. The plans obtained by the proposed query planning process which is composed of the search restriction and translation algorithms can be shown to correspond to query plans semantically equivalent to the initial loosely-specified input query.

When a database is shared by many users, updates to the database schema are almost always prohibited because there is a risk of making existing application programs obsolete when they run against the modified schema. The paper addresses the problem by integrating schema evolution with view facilities. When new requirements necessitate schema updates for a particular user, then the user specifies schema changes to his personal view, rather than to the shared base schema. Our view schema evolution approach then computes a new view schema that reflects the semantics of the desired schema change, and replaces the old view with the new one. We show that our system provides the means for schema change without affecting other views (and thus without affecting existing application programs). The persistent data is shared by different views of the schema, i.e., both old as well as newly developed applications can continue to interoperate. The paper describes a solution approach of realizing the evolution mechanism as a working system, which as its key feature requires the underlying object oriented view system to support capacity augmenting views. We present algorithms that implement the complete set of typical schema evolution operations as view definitions. Lastly, we describe the transparent schema evolution system (TSE) that we have built on top of GemStone, including our solution for supporting capacity augmenting view mechanisms.

Database schemata often experience considerable changes during the development and initial use phases of database systems for advanced applications such as manufacturing automation and computer-aided design. An automated schema evolution system can significantly reduce the amount of effort and potential errors related to schema changes. Although schema evolution for nonreal-time databases was the subject of previous research, its impact on real-time database systems remains unexplored. These advanced applications typically utilize object-oriented data models to handle complex data types. However, there exists no agreed-upon real-time object-oriented data model that can be used as a foundation to define a schema-evolution framework. Therefore, the authors first design a conceptual real-time object-oriented data model, called Real-time Object Model with Performance Polymorphism (ROMPP). It captures the key characteristics of real-time applications-namely, timing constraints and performance polymorphism-by utilizing specialization-dimension and letter-class hierarchy constructs, respectively. They then re-evaluate previous (nonreal-time) schema evolution support in the context of real-time databases. This results in modifications to the semantics of schema changes and to the needs of schema change resolution rules and schema invariants. Furthermore, they expand the schema change framework with new constructs-including new schema change operators, new resolution rules, and new invariants-necessary for handling the real-time characteristics of ROMPP.

In this paper, we present an experimental evaluation of graph clustering strategies in terms of their effectiveness in optimizing I/O for path query processing in digital map databases.Clustering optimization is attractive because it does not incurs any run-time cost, and is complimentary to many of the existing techniques in path query optimization.We first propose a novel graph clustering technique, called Spatial Partition Clustering (SPC), that creates balanced partitions of links based on the spatial proximity of their origin nodes.We then select three alternative clustering techniques from the literature, namely two-way partitioning, approximately topological clustering, and random clustering, to compare their performance in path query processing with SPC.Experimental evahration indicatesthat our SPC performs the best for the high-locality graphs (such as GIS maps), whereas the two-way partitioning approach performs the best for no-locality random graphs.

Efficient path query processing is a key requirement for advanced database applications including GIS (Geographic Information Systems) and ITS (Intelligent Transportation Systems).We study the problem in the context of automobile navigation systems where a large number of path requests can be submitted over the tmrtsportation network within a short period of time.To guarantee efficient responsefor path queries, we employ a path view materiatization strategy for precomputing the best paths.We tackle the following three issues: (1) memory-resident solutions quickly exceed cr.nrentcomputer storage capacity for networks of thousands of nodes, (2) diskbased solutions have been found inefficient to meet the stringent performance requirements, and (3) path views become too costly to update for large graphs.We propose the HEPV (Hierarchical Encoded Path View) approach that addressesthese problems while guaranteeing the optimality of path retrieval.Our experimental fesuks reveaf that HEPV is more efficient than previously known path finding approaches.

View materialization is known to be a valuable technique for performance optimization in relational databases, and much work has been done addressing the problem of consistently maintaining relational views under update operations. However, little progress has been made thus far regarding the topic of view materialization in object-oriented databases (OODBs). In this paper, we demonstrate that there are several significant differences between the relational and object-oriented paradigms that can be exploited when addressing the object-oriented view materialization problem. We use the subsumption relationships between classes to identify branches of classes to which we do not need to propagate updates. Similarly, we use encapsulated interfaces combined with the fact that any unique database property is inherited from a single location to provide a "registration/notification" service for optimizing incremental view updates. We also report results from the experimental studies we have run on the MultiView system measuring the impact of these optimization strategies.

No abstract available.

Simulatingschema evoiution using views offers many advantages over the direct modification of the schema.However, this view approach towards transparent schema evolution has not yet been implemented.One reason for this may be that views can 't simulate capacity-augmenting schema changes due to the inherent limitation of view mechanisms that do not augment the underlying schema.One potential solution for this problem is to develop capac@- augmenhngview support.However, existing 00 view mechanisms do currently not support this capacityaugmenting feature.This paper thus proposes an alternative, more practical, solution to this problem.This solution is neither confined to object-preserving schema changes nor requires capacdy-augmentmg views.Note that our proposed solution is the first to aJso support hard changes such as converting values into an object, splitting two classes vertically, etc., in a transparent fashion.We demonstrate the feasibility of our solution by presenting general algorithms for hard schema changes as well as primitive ones.

When a database is shared by many users, updates to the database schema are almost always prohibited because there is a risk of making existing application programs obsolete when they run against the modified schema. This paper addresses the problem by integrating schema evolution with view facilities. When new requirements necessitate schema updates for a particular user, the user specifies schema changes to the personal view rather than to the shared base schema. Our view evolution approach then computes a new view schema that reflects the semantics of the desired schema change, and replaces the old view with the new one. We present algorithms that implement the set of schema evolution operations typically supported by OODB systems as view definitions. This approach provides the means for schema change without affecting other views (and thus without affecting existing application programs). The persistent data is shared by different views of the schema, i.e., both old as well as newly developed applications can continue to interoperate. In this paper, we present examples that demonstrate our approach.>

In recent years, object-oriented (OO) views have been recognized as a powerful mechanism for customizing the structural as well as behavioral aspects of interfaces to object-oriented databases (OODBs) for diverse users. In this context, classification is concerned with the integration of virtual classes derived using an OO query into one unifying schema. Existing approaches either require the user to explicitly specify the relationship between a virtual class and existing base classes, or they relate a virtual class directly with its source class(es) or with the root of the schema. In this paper, we propose a solution to this classification problem that accomplishes the following goals: (1) generate maximally informative, and thus comprehensible, schemas that explicitly model the subclass relationships between base and virtual classes, and (2) support efficient type resolution for shared property functions by supporting upwards inheritance for both base and virtual classes. Correctness and complexity of the classification algorithm are also discussed.

Many real world systems and applications require information management components that provide support for managing imprecise data. There have thus been several proposals for extending relational database systems in order to represent as well as query such imprecise data. Little work, however, has been done in modeling uncertainty at the conceptual schema level and in developing design methodologies for developing fuzzy relational databases (FRDBs). To fill this gap, a design methodology for FRDBs is proposed. This methodology contains extensions for representing the imprecision of data in the entity-relationship (ER) data model, and a set of steps for the derivation of a FRDB from this extended ER model. As a case study, this methodology has been applied to the design of a control database for semiconductor manufacturing.>

We describe the design and implementation of a scientific database for the map assembly tasks performed by the geneticists at the University of Michigan Human Genome Center. Our system manages complex genomic data and supports the automation of the associated map assembly tasks. For the former, we present a genomic object model that integrates both experimental and derived data. For the latter, we describe operators to automate some of the analysis steps. To develop a framework for implementing our rule-based approach to physical mapping, we have designed and implemented an active object-oriented database (OODB) system, called Crystal, on GemStone. Crystal seamlessly integrates inference capabilities with complex object modeling and other typical database capabilities as required for physical mapping. We also discuss the implementation of a physical map assembly tool on top of Crystal. In conclusion, we provide a walk-through example that demonstrates how our approach can be used to effectively support physical contig assembly.>

Most research on semantic integrity has taken place in the traditional database fields, specifically the relational data model. Advanced models, such as semantic and object-oriented data models, have developed higher level abstractions to increase their expressive power in order to meet the needs of newly emerging application domains. This allows them to incorporate some semantic constraints directly into their schemas. There are, however, many types of restrictions that cannot be expressed solely by these high-level constructs. Therefore we extend the potential of advanced models by augmenting their abstractions with useful set restrictions. In particular, we identify and formulate four of their most common semantic groupings: set groupings, is-a related set groupings, power set groupings, and Cartesian product groupings. For each, we define a number of restrictions that control its structure and composition. We exploit the notion of object identity for the definition of these semantic restrictions. This permits each grouping to capture more subtle distinctions of the concepts in the application environment, as demonstrated by numerous examples throughout this paper. The resulting set of restrictions forms a general framework for integrity constraint management in advanced data models.>

Article An information model for genome map representation and assembly Share on Authors: A. J. Lee Department of EECS, University of Michigan, Ann Arbor, Ann Arbor, MI Department of EECS, University of Michigan, Ann Arbor, Ann Arbor, MIView Profile , E. A. Rendensteiner Department of EECS, University of Michigan, Ann Arbor, Ann Arbor, MI Department of EECS, University of Michigan, Ann Arbor, Ann Arbor, MIView Profile , S. Thomas Information Technology and Networking, University of Michigan Medical Center, Human Genome Center, 2570C MSRB II Information Technology and Networking, University of Michigan Medical Center, Human Genome Center, 2570C MSRB IIView Profile , S. Lafortune Department of EECS, University of Michigan, Ann Arbor, Ann Arbor, MI Department of EECS, University of Michigan, Ann Arbor, Ann Arbor, MIView Profile Authors Info & Claims CIKM '93: Proceedings of the second international conference on Information and knowledge managementDecember 1993 Pages 75–84https://doi.org/10.1145/170088.170107Published:01 December 1993 5citation1,221DownloadsMetricsTotal Citations5Total Downloads1,221Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

This paper discusses two aspects of the objectoriented view management system, Multi View, which we Proofs of correctness of these algorithms can be shown.1 database specialists.00 views promise to be more powerful than relational views, since they can customize not only data structures but also the associated operations.Furthermore, they can be used to restructure the generalization hierarchy to classify objects in a manner most meaningful for a particular user group.Lastly, the view

The semantics of set operations are not adequate for the richer data models of object-based database systems that include object-oriented and semantic data modeling concepts. The reason is that precise semantics of set operations on complex objects require a clear distinction between the dual notions of a set and a type, both of which are present in the class construct found in object-based data models. This gap is filled here by a framework for executing set theoretic operations on the class construct. The proposed set operations, including set difference, union, intersection and symmetric difference, determine both the type description of the derived class as well as its set membership. For the former, inheritance rules are developed for property characteristics such as single-valued versus multivalued and required versus optional. For the latter, the object identity concept is developed if borrowed from data modeling research. The framework allows for property inheritance among classes that are not necessarily IS-A related.>

Three of the most common fundamental groupings that are utilized in semantic database models are considered: set groupings, power set groupings, and Cartesian aggregation groupings. For each, useful restrictions that control its structure and composition are defined. This permits each grouping to capture more subtle distinctions of the concepts or situations in the application environment. The resulting set of restrictions forms a framework for integrity constraints in semantic data models. This framework is targeted towards advanced applications, such as computer-aided design, office automation, and artificial intelligence, which require the support of more sophisticated relationships among data than traditional database domains.>