Efficient storage and query processing over tabular data, while balancing storage cost, query latency, and memory footprint, remains a fundamental challenge in the database community. In this work, we propose DeepMapping++, a neural-based data representation that leverages the memorization capability of deep neural networks to support efficient query processing in resource-constrained environments. DeepMapping++ has two flavors: DeepMapping-L for lossless look-up queries on categorical data and DeepMapping-R for approximate range aggregation queries on numerical data. To efficiently handle data modifications, DeepMapping-L integrates a lightweight auxiliary structure to correct prediction errors and support data modification operations, including insertions, deletions, and updates. DeepMapping-R further incorporates a buffer structure for caching partially aggregated values to reduce the need for model retraining. Experiments on real-world, synthetic, and benchmark datasets, demonstrated the effectiveness of DeepMapping-L and DeepMapping-R.

Due to the critical role causality plays in decision-making, the state of-the-art in machine learning for causality is rapidly evolving. With rapid development and deployment of new models, datasets, and metrics, it is increasingly difficult for researchers and practitioners to identify the most suitable approach for their problem. Models exhibit different performances when they train on different data or even when they are used under different hardware/software platforms, making it challenging for users to select the appropriate setup pertinent to their problem. To address these difficulties, we present a computing framework, CausalBench-ER that serves, not only as a benchmarking platform for causal machine learning models, but also as a resource that can explain benchmarking results across different metrics, software, and hardware setups. Furthermore, CausalBench-ER recommends additional scenarios to consider to help pave the way towards more robust benchmarking.

Recent advances in causal machine learning introduced a plethora of new causal discovery and causal inference models to tackle decision support problems. Yet, these models exhibit different performance when they train on different data, and even different hardware/software platforms, making it challenging for users to select the appropriate setup pertinent to their specific problem instance. The situation is complicated by the fact that, until recently, the field lacked a unified, publicly available, and configurable platform that supports all major causal inference tasks, including causal discovery, causal effect estimation, and causal inference. CausalBench is a comprehensive benchmarking tool for causal machine learning that facilitates accurate and reproducible benchmarking of causal models across metrics and deployment contexts and helps users to select the most appropriate set up (such as hyper-parameter configuration) for the specific problem setting. This tutorial is intended to familiarize attendees from diverse backgrounds, who are interested in causal learning models and with the capabilities of CausalBench. The tutorial begins with an introduction to ''causality'' and causal machine learning, and then provides hands-on experience with CausalBench to equip attendees with the knowledge necessary to utilize CausalBench for their causal learning problems.

Understanding the underlying dynamics of emerging phenomena are increasingly critical in various application domains, from social media trends to predicting geo-temporal evolution of epidemics to helping reduce energy footprints of buildings. Addressing the most pressing societal challenges requires (a) a deep understanding of the relationships and interactions among diverse, spatially and temporally distributed entities and (b) the capability to develop, and explain, informed forecasts based on such an understanding. In this talk, I argue that achieving these necessitates the ability to use spatio-temporal information to gain causal situational awareness and also to leverage such causal information to tackle both aleatoric and epistemic uncertainties in decision making. Despite the apparent promise of such a causally-grounded approach, the core technologies required to achieve this are in their early stages and frameworks to realize their potential are still lacking. In this keynote, I argue for a vision for causal awareness in algorithms and applications and highlight our community's role in this context.

Streamflow plays an essential role in the sustainable planning and management of national water resources. Traditional hydrologic modeling approaches simulate streamflow by establishing connections across multiple physical processes, such as rainfall and runoff. These data, inherently connected both spatially and temporally, possess intrinsic causal relations that can be leveraged for robust and accurate forecasting. Recently, spatio-temporal graph neural networks (STGNNs) have been adopted, excelling in various domains, such as urban traffic management, weather forecasting, and pandemic control, and they also promise advances in streamflow management. However, learning causal relationships directly from vast observational data is theoretically and computationally challenging. In this study, we employ a river flow graph as prior knowledge to facilitate the learning of the causal structure and then use the learned causal graph to predict streamflow at targeted sites. The proposed model, Causal Streamflow Forecasting (CSF) is tested in a real-world study in the Brazos River basin in Texas. Our results demonstrate that our method outperforms regular spatio-temporal graph neural networks and achieves higher computational efficiency compared to traditional simulation methods. By effectively integrating river flow graphs with STGNNs, this research offers a novel approach to streamflow prediction, showcasing the potential of combining advanced neural network techniques with domain-specific knowledge for enhanced performance in hydrologic modeling.

Wetlands are important to communities, offering benefits ranging from water purification, and flood protection to recreation and tourism. Therefore, identifying and prioritizing potential wetland areas is a critical decision problem. While data-driven solutions are feasible, this is complicated by significant data sparsity due to the low proportion of wetlands (3-6%) in many areas of interest in the southwestern US. This makes it hard to develop data-driven models that can help guide the identification of additional wetland areas. To solve this limitation, we propose two strategies: (1) knowledge transfer from regions with rich wetlands (such as the Eastern US) to regions with sparser wetlands (such as the Southwestern area). , and (2) spatial data enrichment strategy that relies on an adaptive propagation mechanism. This mechanism differentiates between node pairs that have positive and negative impacts on each other for Graph Neural Networks (GNNs). We conduct rigorous experiments to substantiate our proposed method's effectiveness, robustness, and scalability compared to state-of-the-art baselines. Additionally, an ablation study demonstrates that each module is essential in prioritizing potential wetlands.

Factorization machines (FMs) are a class of general predictors for sparse data. One major benefit of FMs is their ability to capture the interactions across features when making recommendations. In this paper, we note that the interactions captured by existing FMs generally represent correlations in the data and we argue that such correlations, unless informed by the true causality structures underlying the data, may be spurious and may result in unwanted bias. To tackle this challenge, we propose a Causally-Informed Factorization Machine (CIFM) model that introduces a novel causal injection mechanism. CIFM leverages a priori causal knowledge, described in the form of a causal graph, to boost the representational ability of FMs and achieve better predictions. Specifically, given a (potentially learned) causal graph which describes the causal relationships among features, CIFM distills this structural information into a pairwise causal impact matrix and guides the learning process to ensure that the learned representations capture those relationships that are consistent with the causal relationships. Extensive evaluations of CIFM, along with its integrations with NeuralFM and DeepFM, conducted with synthetic and real-world data sets, demonstrate the effectiveness of causal injection in generating better recommendations.

Storing tabular data to balance storage and query efficiency is a long-standing research question in the database community. In this work, we argue and show that a novel DeepMapping abstraction, which relies on the impressive memorization capabilities of deep neural networks, can provide better storage cost, better latency, and better run-time memory footprint, all at the same time. Such unique properties may benefit a broad class of use cases in capacity-limited devices. Our proposed DeepMapping abstraction transforms a dataset into multiple key-value mappings and constructs a multi-tasking neural network model that outputs the corresponding values for a given input key. To deal with memorization errors, DeepMapping couples the learned neural network with a lightweight auxiliary data structure capable of correcting mistakes. The auxiliary structure design further enables DeepMapping to efficiently deal with insertions, deletions, and updates even without retraining the mapping. We propose a multi-task search strategy for selecting the hybrid DeepMapping structures (including model architecture and auxiliary structure) with a desirable trade-off among memorization capacity, size, and efficiency. Extensive experiments with a real-world dataset, synthetic and benchmark datasets, including TPC-H and TPC-DS, demonstrated that the DeepMapping approach can better balance the retrieving speed and compression ratio against several cutting-edge competitors.

Tensor Train (TT) is a tensor decomposition technique designed to resolve the curse of dimensionality and the intermediate memory blow-up problems in traditional techniques for high-dimensional data analysis. Tensor train process provides linear space complexity by creating a sequential tensor network of low modalities. However, the selected sequence of decomposition order can have a significant impact on the accuracy and representativeness of the final decomposition and, unfortunately, choosing a good order for the TT representation is not a trivial task. In this paper, we observe that the causal structure underlying the data can impact the tensor train process and that a rough estimate of causality can be used to inform the order of the latent spaces to consider. Enlightened by this observation, we propose a novel causally informed tensor train decomposition (CTT) approach to tackle the sequence selection problem in TT-decomposition. CTT leverages the structural information in a given causal graph and recommends a suitable causally-informed decomposition sequence for TT-decomposition.

The capacity to anticipate streamflow is critical to the efficient functioning of reservoir systems as it gives vital information to reservoir operators about water release quantities as well as help quantify the impact of environmental factors on downstream water quality. Yet, streamflow modelling is difficult owing to the intricate interactions between different watershed outlets. In this paper, we argue that one possible solution to this problem is to identify the causal structure of these outlets, which would allow for the identification of crucial watershed outlets while capturing the spatiotemporally informed complex relationships leading to improved hydrological resource management. However, due to the inherent complexity of spatiotemporal causal learning problems, extending existing causal discovery methods to a whole basin is a major hurdle. To address these issues, we offer STREAMS, a new framework that uses Reinforcement Learning (RL) to optimize the search space for causal discovery and an LSTM-GCN based autoencoder to infer spatiotemporal causal features for streamflow rate prediction. We conduct extensive experiments on the Brazos river basin carried out within the scope of a US Army Corps of Engineers, Engineering With Nature Initiative project, including empirical studies of generalization performance to verify the nature of the inferred relationships.

We are excited to welcome you to Volume 1 of a brand new journal - Proceedings of the ACM on Management of Data, PACMMOD. This new journal is concerned with the principles, algorithms, techniques, systems, and applications of database management systems, data management technology, and science and engineering of data and will include articles reporting cutting-edge data management, data engineering, and data science research. Articles published at PACMMOD address data challenges at various stages of the data lifecycle, from modeling, acquisition, cleaning, integration, indexing, querying, analysis, exploration, visualization, interpretation, and explanation. They focus on data-intensive components of data pipelines; and solve problems in areas of interest to our community (e.g., data curation, optimization, performance, storage, systems), operating within accuracy, privacy, fairness, and diversity constraints. Articles reporting deployed systems and solutions to data science pipelines and/or fundamental experiences and insights from evaluating real-world data engineering problems are especially encouraged.

We are excited to welcome you to the second issue of Volume 1 of the Proceedings of the ACM on Management of Data, PACMMOD. In addition to the 76 research track articles (out of 279 Cycle C submissions), this issue also includes peer-reviewed industrial track papers.

Online user engagement is highly influenced by various machine learning models, such as recommender systems. These systems recommend new items to the user based on the user’s historical interactions. Implicit recommender systems reflect a binary setting showing whether a user interacted (e.g., clicked on) with an item or not. However, the observed clicks may be due to various causes such as user’s interest, item’s popularity, and social influence factors. Traditional recommender systems consider these causes under a unified representation, which may lead to the emergence and amplification of various biases in recommendations. However, recent work indicates that by disentangling the unified representations, one can mitigate bias (e.g., popularity bias) in recommender systems and help improve recommendation performance. Yet, prior work in causal disentanglement in recommendations does not consider a crucial factor, that is, social influence. Social theories such as homophily and social influence provide evidence that a user’s decision can be highly influenced by the user’s social relations. Thus, accounting for the social relations while disentangling leads to less biased recommendations. To this end, we identify three separate causes behind an effect (e.g., clicks): (a) user’s interest, (b) item’s popularity, and (c) user’s social influence. Our approach seeks to causally disentangle the user and item latent features to mitigate popularity bias in implicit feedback–based social recommender systems. To achieve this goal, we draw from causal inference theories and social network theories and propose a causality-aware disentanglement method that leverages both the user–item interaction network and auxiliary social network information. Experiments on real-world datasets against various state-of-the-art baselines validate the effectiveness of the proposed model for mitigating popularity bias and generating de-biased recommendations.

In many fields of computer science, tensor decomposition techniques are increasingly being adopted as the core of many applications that rely on multi-dimensional datasets for implementing knowledge discovery tasks. Unfortunately, a major shortcoming of state-of-the-art tensor analyses is that, despite their effectiveness when the data is certain, these operations become difficult to apply, or altogether inapplicable, in the presence of uncertainty in the data, a circumstance common to many real-world scenarios. In this paper we propose a way to address this issue by extending the known Tensor-Train technique for tensor factorization in order to deal with uncertain data, here modeled as intervals. Working with interval-valued data, however, presents numerous challenges, since many algebraic operations that form the building blocks of the factorization process, as well as the properties that make these procedures useful for knowledge discovery, cannot be easily extended from their scalar counterparts, and often require some approximation (including, though it is not only the case, for keeping computational costs manageable). These challenges notwithstanding, our proposed techniques proved to be reasonably effective, and are supported by a thorough experimental validation.

Physical process-based hydrological models are widely adopted to simulate the water quantity or quality. One of the most commonly used hydrological models is Soil and Water Assessment Tool (SWAT). SWAT models for a large watershed can have over tens of thousands of Hydrological Resource Units (HRUs) which necessitates considerable computational resources. One way to speed up applications of the SWAT model could be to leverage machine learning techniques to identify the crucial features for the prediction task – feature selection. However, majority of the feature selection techniques rely on correlations or some form of a score metric (e.g. mutual information). Furthermore, since correlation does not imply causation, it is important to identify the causal features to improve the prediction accuracy while enhancing the interpretability of machine learning models. However, the SWAT model uses multiple data inputs and features that typically vary by space/HRUs, but may or may not vary over time. This makes it difficult to directly utilize causal discovery models to infer the causal relations. Furthermore, due to the lack of the ground truth causal graph for the SWAT model it is difficult to comment on the validity of the learned causal relations. To overcome these problems, we propose a novel framework that first infers the causal relations for the daily scale of the SWAT data using causal discovery algorithms. Then, it utilizes a community detection module to group similar features together for better interpretability. Finally, it identifies the stable causal relations that appear most often across all the timesteps and leverage them for the prediction of the water quantity. By utilizing only the causal features for the prediction of the target variable can lead to high accuracy as it removes the reliance on spurious correlations. Furthermore, we conduct extensive experiments to validate the effectiveness of the proposed framework along with a real-world case study to evaluate whether the selected features are interpretable or not.

Causal learning has become an essential attribute in majority of the machine learning models. One of the widely studied fields in causal learning is causal discovery which aims to identify potential cause-effect relationships from observational data. Temporal causal discovery models are specifically curated to enforece the temporal constraints while discovering the causal relationships. However, in physical systems such as hydrological systems, there are additional constraints such as spatial constraints that play a crucial role in deciding whether a node is a causal parent for another node or not. Failing to enforce these additional constraints may mislead the model to classify an irrelevant relationship as a causal relationship. Furthermore, causal discovery models are evaluated against a ground truth causal graph. However, the hydrological systems contain a huge number of features making it challenging to obtain a ground-truth causal graph. To deal with the aforementioned problems, in this study we propose a new Spatio-Temporal Causal Discovery Framework named, STCD. By enforcing temporal and spatial constraints STCD aims at identifying meaningful causal relationships. Furthermore, to evaluate the causal relations inferred by STCD in the absence of the ground-truth causal graph, we utilize only the causal parents of a target variable for prediction across different years. We demonstrate that utilizing only the causal features identified by STCD to predict the flow-rate for a target location attains superior performance.

Causal inference is a critical task in various fields such as healthcare, economics, marketing and education. Recently, there have been significant advances through the application of machine learning techniques, especially deep neural networks. Unfortunately, to-date many of the proposed methods are evaluated on different (data, software/hardware, hyperparameter) setups and consequently it is nearly impossible to compare the efficacy of the available methods or reproduce results presented in original research manuscripts. In this paper, we propose a causal inference toolbox (CauseBox) that addresses the aforementioned problems. At the time of publication, the toolbox includes seven state of the art causal inference methods and two benchmark datasets. By providing convenient command-line and GUI-based interfaces, the CauseBox toolbox helps researchers fairly compare the state of the art methods in their chosen application context against benchmark datasets. The code is made public at github.com/paras2612/CauseBox.

With many applications relying on multi-dimensional datasets for decision making, matrix factorization (or decomposition) is becoming the basis for many knowledge discoveries and machine learning tasks, from clustering, trend detection, anomaly detection, to correlation analysis. Unfortunately, a major shortcoming of matrix analysis operations is that, despite their effectiveness when the data is scalar, these operations become difficult to apply in the presence of non-scalar data, as they are not designed for data that include non-scalar observations, such as intervals. Yet, in many applications, the available data are inherently non-scalar for various reasons, including imprecision in data collection, conflicts in aggregated data, data summarization, or privacy issues, where one is provided with a reduced, clustered, or intentionally noisy and obfuscated version of the data to hide information. In this paper, we propose matrix decomposition techniques that consider the existence of interval-valued data. We show that naive ways to deal with such imperfect data may introduce errors in analysis and present factorization techniques that are especially effective when the amount of imprecise information is large.

Deep neural networks (DNNs), especially convolutional neural networks (CNNs), have been effective in various data-driven applications. Yet, DNNs suffer from several major challenges; in particular, in many applications where the input data is relatively sparse, DNNs face the problems of overfitting to the input data and poor generalizability. This brings up several critical questions: "Are all inputs equally importantƒ" "Can we selectively focus on parts of the input data in a way that reduces overfitting to irrelevant observationsƒ" Recently, attention networks showed some success in helping the overall process focus onto parts of the data that carry higher importance in the current context. Yet, we note that the current attention network design approaches are not sufficiently informed about the key data characteristics in identifying salient regions in the data. We propose an innovative robust feature learning framework, scale-invariant attention networks (SAN), that identifies salient regions in the input data for the CNN to focus on. Unlike the existing attention networks, SAN concentrates attention on parts of the data where there is major change across space and scale. We argue, and experimentally show, that the salient regions identified by SAN lead to better network performance compared to state-of-the-art (attentioned and non-attentioned) approaches, including architectures such as LeNet, VGG, ResNet, and LSTM, with common benchmark datasets, MNIST, FMNIST, CIFAR10/20/100, GTSRB, ImageNet, Mocap, Aviage, and GTSDB for tasks such as image/time series classification, time series forecasting and object detection in images.

With many applications relying on multi-dimensional datasets for decision making, matrix factorization (or decomposition) is becoming the basis for many knowledge discovery and machine learning tasks, from clustering, trend detection, anomaly detection, to correlation analysis. Unfortunately, a major shortcoming of matrix analysis operations is that, despite their effectiveness when the data is scalar, these operations become difficult to apply in the presence of non-scalar data, as they are not designed for data that include non-scalar observations, such as intervals. In this paper, we propose matrix decomposition techniques that consider the existence of interval-valued data. We show that naive ways to deal with such imperfect data may introduce errors in analysis and present factorization techniques that are especially effective when the amount of imprecise information is large.

Deep neural networks have demonstrated unprecedented success in various multimedia applications. However, the networks created are often very complex, with large numbers of trainable edges that require extensive computational resources. We note that many successful networks nevertheless often contain large numbers of redundant edges. Moreover, many of these edges may have negligible contributions towards the overall network performance. In this paper, we propose a novel iSparse framework and experimentally show, that we can sparsify the network without impacting the network performance. iSparse leverages a novel edge significance score, E, to determine the importance of an edge with respect to the final network output. Furthermore, iSparse can be applied both while training a model or on top of a pre-trained model, making it a retraining-free approach - leading to a minimal computational overhead. Comparisons of iSparse against Dropout, L1, DropConnect, Retraining-Free, and Lottery-Ticket Hypothesis on benchmark datasets show that iSparse leads to effective network sparsifications.

Deep architectures are trained on massive amounts of labeled data to guarantee the performance of classification. In the absence of labeled data, domain adaptation often provides an attractive option given that labeled data of a similar nature but from a different domain is available. Previous work has chiefly focused on learning domain invariant representations but overlooked the issues of label imbalance in a single domain or across domains, which are common in many machine learning applications such as fake news detection. In this paper, we study a new cross-domain classification problem where data in each domain can be imbalanced (data imbalance), i.e., the classes are not evenly distributed, and the ratio of the number of positive over negative samples varies across domains (domain imbalance). This cross-domain problem is challenging as it entails covariate bias in the input feature space and representation bias in the latent space where domain invariant representations are learned. To address the challenge, in this paper, we propose an effective approach that leverages a doubly balancing strategy to simultaneously control these two types of bias and learn domain invariant representations. To this end, the proposed method aims to learn representations that are (i) robust to data and domain imbalance, (ii) discriminative between classes, and (iii) invariant across domains. Extensive evaluations of two important real-world applications corroborate the effectiveness of the proposed framework.

Despite their impressive success when these hyper-parameters are suitably fine-tuned, the design of good network architectures remains an art-form rather than a science: while various search techniques, such as grid-search, have been proposed to find effective hyper-parameter configurations, often these parameters are hand-crafted (or the bounds of the search space are provided by a user). In this paper, we argue, and experimentally show, that we can minimize the need for hand-crafting, by relying on the dataset itself. In particular, we show that the dimensions, distributions, and complexities of localized features extracted from the data can inform the structure of the neural networks and help better allocate limited resources (such as kernels) to the various layers of the network. To achieve this, we first present several hypotheses that link the properties of the localized image features to the CNN and RCNN architectures and then, relying on these hypotheses, present a RACKNet framework which aims to learn multiple hyper-parameters by extracting information encoded in the input datasets. Experimental evaluations of RACKNet against major benchmark datasets, such as MNIST, SVHN, CIFAR10, COIL20 and ImageNet, show that RACKNet provides significant improvements in the network design and robustness to change in the network.

Efficient implementations of range and nearest neighbor queries are critical in many large multimedia applications. Locality Sensitive Hashing (LSH) is a popular technique for performing approximate searches in high-dimensional multimedia, such as image or sensory data. Often times, these multimedia data are represented as a collection of important spatio-temporal features which are extracted by using localized feature extraction algorithms. When a user wants to search for a given entity (object, event, or observation), individual similarity search queries, which collectively form a set query, need to be performed on the features that represent the particular search entity. Existing LSH techniques require that users provide an accuracy guarantee for each query in the set query, instead of an overall guarantee for the entire set query, which can lead to misses or wasteful work. We propose a novel index structure, Point Set LSH (PSLSH), which is able to execute a similarity search for a given set of search points in the high-dimensional space with a user-provided guarantee for the entire set query. Experimental evaluation shows significant gains in efficiency and accuracy trade-offs for executing set queries in high-dimensional spaces.

Data-and model-driven computer simulations are increasingly critical in many application domains. These simulations may track 10s or 100s of parameters, affected by complex inter-dependent dynamic processes. Moreover, decision makers usually need to run large simulation ensembles, containing 1000s of simulations. In this paper, we rely on a tensor-based framework to represent and analyze patterns in large simulation ensemble data sets to obtain a high-level understanding of the dynamic processes implied by a given ensemble of simulations.We, further, note that the inherent sparsity of the simulation ensembles (relative to the space of potential simulations one can run) constitutes a significant problem in discovering these underlying patterns. To address this challenge, we propose a partition-stitch sampling scheme, which divides the parameter space into subspaces to collect several lower modal ensembles, and complement this with a novel Multi-Task Tensor Decomposition (M2TD), technique which helps effectively and efficiently stitch these subensembles back. Experiments showed that, for a given budget of simulations, the proposed structured sampling scheme leads to significantly better overall accuracy relative to traditional sampling approaches, even when the user does not have a perfect information to help guide the structured partitioning process.

Data- and model-driven computer simulations are increasingly critical in many application domains. Yet, several critical data challenges remain in obtaining and leveraging simulations in decision making. Simulations may track 100s of parameters, spanning multiple layers and spatial-temporal frames, affected by complex inter-dependent dynamic processes. Moreover, due to the large numbers of unknowns, decision makers usually need to generate ensembles of stochastic realizations, requiring 10s-1000s of individual simulation instances. The situation on the ground evolves unpredictably, requiring continuously adaptive simulation ensembles. We introduce the DataStorm framework for simulation ensemble management, and demonstrate its DataStorm-FE data- and decision-flow and coordination engine for creating and maintaining coupled, multi-model simulation ensembles. DataStorm-FE enables end-to-end ensemble planning and optimization, including parameter-space sampling, output aggregation and alignment, and state and provenance data management, to improve the overall simulation process. It also aims to work efficiently, producing results while working within a limited simulation budget, and incorporates a multivariate, spatiotemporal data browser to empower decision-making based on these improved results.

Data- and model-driven computer simulations are increasingly critical in many application domains. These simulations may track 100s or 1000s of inter-dependent parameters, spanning multiple layers and spatial-temporal frames, affected by complex dynamic processes operating at different resolutions. Because of the size and complexity of the data and the varying spatial and temporal scales at which the key processes operate, experts often lack the means to analyze results of large simulation ensembles, understand relevant processes, and assess the robustness of conclusions driven from the resulting simulations. Moreover, data and\nmodels dynamically evolve over time requiring continuous adaptation of simulation ensembles. The simDMS platform aims to address the key challenges underlying the creation and use of large simulation ensembles and enables (a) execution, storage, and indexing of large ensemble simulation data sets and the corresponding models; and (b) search, analysis, and exploration of ensemble simulation data sets to enable ensemble-based decision support.

Measures of node ranking, such as personalized PageRank, are utilized in many web and social-network based prediction and recommendation applications. Despite their effectiveness when the underlying graph is certain, however, these measures become difficult to apply in the presence of uncertainties, as they are not designed for graphs that include uncertain information, such as edges that mutually exclude each other. While there are several ways to naively extend existing techniques (such as trying to encode uncertainties as edge weights or computing all possible scenarios), as we discuss in this paper, these either lead to large degrees of errors or are very expensive to compute, as the number of possible worlds can grow exponentially with the amount of uncertainty. To tackle with this challenge, in this paper, we propose an efficient Uncertain Personalized PageRank (UPPR) algorithm to approximately compute personalized PageRank values on an uncertain graph with edge uncertainties. UPPR avoids enumeration of all possible worlds, yet it is able to achieve comparable accuracy by carefully encoding edge uncertainties in a data structure that leads to fast approximations. Experimental results show that UPPR is very efficient in terms of execution time and its accuracy is comparable or better than more costly alternatives.

Tensor decomposition is used for many web and user data analysis operations from clustering, trend detection, anomaly detection, to correlation analysis. However, many of the tensor decomposition schemes are sensitive to noisy data, an inevitable problem in the real world that can lead to false conclusions. The problem is compounded by over-fitting when the user data is sparse. Recent research has shown that it is possible to avoid over-fitting by relying on probabilistic techniques. However, these have two major deficiencies: (a) firstly, they assume that all the data and intermediary results can fit in the main memory, and (b) they treat the entire tensor uniformly, ignoring potential non-uniformities in the noise distribution. In this paper, we propose a Noise-Profile Adaptive Tensor Decomposition (nTD) method, which aims to tackle both of these challenges. In particular, nTD leverages a grid-based two-phase decomposition strategy for two complementary purposes: firstly, the grid partitioning helps ensure that the memory footprint of the decomposition is kept low; secondly (and perhaps more importantly) any a priori knowledge about the noise profiles of the grid partitions enable us to develop a sample assignment strategy (or s-strategy) that best suits the noise distribution of the given tensor. Experiments show that nTD's performance is significantly better than conventional CP decomposition techniques on noisy user data tensors.

With many applications relying on multi-dimensional datasets for decision making, tensors (or multi-dimensional arrays) are emerging as a popular data representation to support diverse types of data, such as sensor streams and social networks. Consequently, tensor decomposition forms the basis for many data analysis and knowledge discovery tasks, from clustering, trend detection, anomaly detection, to correlation analysis. In applications where data evolves over time and the tensor-based analysis results need to be continuously maintained, re-computation of the whole tensor decomposition with each update will cause high computational costs and incur large memory overheads. In this paper, we propose a two-phase block-incremental CP-based tensor decomposition technique, BICP, that efficiently and effectively maintains tensor decomposition results in the presence of dynamically evolving tensor data. In its first phase, instead of repeatedly conducting ALS on each sub-tensor, BICP only revises the decompositions of the tensors that contain updated data. Moreover, when updates are relatively small with respect to the block size, BICP relies on a incremental factor tracking to avoid re-decomposition the updated sub-tensor. In its second phase, BICP limits the block-centric refinement process to only those blocks that are critical given the update. Experiment results show that the proposed method significantly reduces the execution time while assuring high accuracy.

Tensors are multi-dimensional arrays - consequently, tensor decomposition operations (CP and Tucker) are the bases for many high-dimensional data analysis tasks, from clustering, trend detection, anomaly detection, to correlation analysis in various application domains, including science and engineering1. One key problem with tensor decomposition is its computational complexity and space requirements. Especially, as the relevant data sets get denser, in-memory schemes for tensor decomposition become increasingly ineffective; therefore out-of-core (secondary-memory supported, potentially parallel) computing is necessitated. However, existing techniques do not consider the I/O and network data exchange costs that out-of-core execution of the tensor decomposition operation will incur. In this paper, we note that when this operation is implemented with the help of secondary-memory and/or multiple servers to tackle the memory limitations, we would need intelligent buffer-management and task-scheduling techniques which take into account the cost of bringing the relevant blocks into the buffer to minimize I/O in the system. In this paper, we introduce 2PCP, a two-phase, block-based CP decomposition system with intelligent buffer sensitive task scheduling and buffer management mechanisms. 2PCP aims to reduce I/O costs in the analysis of relatively dense tensors common in scientific and engineering applications. Experiment results compare with current state of art tensor decomposition algorithms and show that our algorithms can significantly reduce the amount of I/O and execution time while maintaining decomposition accuracy.

Presents the introductory editorial for this issue of the publication.

Understanding how a given pair of graphs align with each other (also known as the graph matching problem) is a critical task in many search, classification, and analysis applications. Unfortunately, the problem of maximum common subgraph isomorphism between two graphs is a well known NP-hard problem, rendering it impractical to search for exact graph alignments. While there are several heuristics, most of these analyze and encode global and local structural information for every node of the graph and then rank pairs of nodes across the two graphs based on their structural similarities. Moreover, many algorithms involve a post-processing (or refinement) step which aims to improve the initial matching accuracy. In this paper we note that the expensive refinement phase of graph matching algorithms is not practical in any application where scalability is critical. It is also impractical to seek structural similarity between all pairs of nodes. We argue that a more practical and scalable solution is to seek structural keynodes of the input graphs that can be used to limit the amount of time needed to search for alignments. Naturally, these keynodes need to be selected carefully to prevent any degradations in accuracy during the alignment process. Given this motivation, in this paper, we first present a structural keynode extraction (SKE) algorithm and then use structural keynodes obtained during off-line processing for keynode-driven scalable graph matching (KSGM). Experiments show that the proposed keynode-driven scalable graph matching algorithms produce alignments that are as accurate as (or better than) the state-of-the-art algorithms, with significantly faster online executions.

In most spatial data management applications, objects are represented in terms of their coordinates in a 2-dimensional space and search queries in this space are processed using spatial index structures. On the other hand, bitmap-based indexing, especially thanks to the compression opportunities bitmaps provide, has been shown to be highly effective for query processing workloads including selection and aggregation operations. In this paper, we show that bitmap-based indexing can also be highly effective for managing spatial data sets. More specifically, we propose a novel compressed spatial hierarchical bitmap (cSHB) index structure to support spatial range queries. We consider query workloads involving multiple range queries over spatial data and introduce and consider the problem of bitmap selection for identifying the appropriate subset of the bitmap files for processing the given spatial range query workload. We develop cost models for compressed domain range query processing and present query planning algorithms that not only select index nodes for query processing, but also associate appropriate bitwise logical operations to identify the data objects satisfying the range queries in the given workload. Experiment results confirm the efficiency and effectiveness of the proposed compressed spatial hierarchical bitmap (cSHB) index structure and the range query planning algorithms in supporting spatial range query workloads.

Efficient processing of skyline queries has been an area of growing interest. Many of the earlier skyline techniques assumed that the skyline query is applied to a single data table. Naturally, these algorithms were not suitable for many applications in which the skyline query may involve attributes belonging to multiple data sources. In other words, if the data used in the skyline query are stored in multiple tables, then join operations would be required before the skyline can be searched. The task of computing skylines on multiple data sources has been coined as the skyline-join problem and various skyline-join algorithms have been proposed. However, the current proposals suffer several drawbacks: they often need to scan the input tables exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. In this article, we aim to address these shortcomings by proposing two novel skyline-join algorithms, namely skyline-sensitive join (S 2 J) and symmetric skyline-sensitive join (S 3 J), to process skyline queries over two data sources. Our approaches compute the results using a novel layer/region pruning technique ( LR-pruning ) that prunes the join space in blocks as opposed to individual data points, thereby avoiding excessive pairwise point-to-point dominance checks. Furthermore, the S 3 J algorithm utilizes an early stopping condition in order to successfully compute the skyline results by accessing only a subset of the input tables. In addition to S 2 J and S 3 J, we also propose the S 2 J-M and S 3 J-M algorithms. These algorithms extend S 2 J's and S 3 J's two-way skyline-join ability to efficiently process skyline-join queries over more than two data sources. S 2 J-M and S 3 J-M leverage the extended concept of LR-pruning , called M -way LR-pruning , to compute multi-way skyline-joins in which more than two data sources are integrated during skyline processing. We report extensive experimental results that confirm the advantages of the proposed algorithms over state-of-the-art skyline-join techniques.

Network based recommendation systems leverage the topology of the underlying graph and the current user context to rank objects in the database. Random-walk based techniques, such as PageRank, encode the structure of the graph in the form of a transition matrix of a stochastic process from which the significances of the nodes in the graph are inferred. Personalized PageRank (PPR) techniques complement this with a seed node set which serves as the personalization context. In this paper, we note (and experimentally show) that PPR algorithms that do not differentiate among the seed nodes may not properly rank nodes in situations where the seed set is incomplete and/or noisy. To tackle this problem, we propose alternative robust personalized PageRank (RPR) strategies, which are insensitive to noise in the set of seed nodes and in which the rankings are not overly biased towards the seed nodes. In particular, we show that novel teleportation discounting and seed-set maximal PPR techniques help eliminate harmful bias of individual seed nodes and provide effective seed differentiation to lead to more accurate rankings.

Non-negative matrix factorization (NMF) is a well known method for obtaining low rank approximations of data sets, which can then be used for efficient indexing, classification, and retrieval. The non-negativity constraints enable probabilistic interpretation of the results and discovery of generative models. One key disadvantage of the NMF, however, is that it is costly to obtain and this makes it difficult to apply NMF in applications where data is dynamic. In this paper, we recognize that many applications involve redundancies and we argue that these redundancies can and should be leveraged for reducing the computational cost of the NMF process: Firstly, online applications involving data streams often include temporal redundancies. Secondly, and perhaps less obviously, many applications include integration of multiple data streams (with potential overlaps) and/or involves tracking of multiple similar (but different) queries; this leads to significant data and query redundancies, which if leveraged properly can help alleviate computational cost of NMF. Based on these observations, we introduce Group Incremental Non-Negative Matrix Factorization (GI-NMF) which leverages redundancies across multiple NMF tasks over data streams. The proposed algorithm relies on a novel group multiplicative update rules (G-MUR) method to significantly reduce the cost of NMF. GMUR is further complemented to support incremental update of the factors where data evolves continuously. Experiments show that GI-NMF significantly reduces the processing time, with minimal error overhead.

As the relevant data sets get large, existing in-memory schemes for tensor decomposition become increasingly ineffective and, instead, memory-independent solutions, such as in-database analytics, are necessitated. In this paper, we present techniques for efficient implementations of in-database tensor decompositions on chunk-based array data stores. The proposed static and incremental in-database tensor decomposition operators and their optimizations address the constraints imposed by the main memory limitations when handling large and high-order tensor data. Firstly, we discuss how to implement alternating least squares operations efficiently on a chunk-based data storage system. Secondly, we consider scenarios with frequent data updates and show that compressed matrix multiplication techniques can be effective in reducing the incremental tensor decomposition maintenance costs. To the best of our knowledge, this paper presents the first attempt to develop efficient and optimized in-database tensor decomposition operations. We evaluate the proposed algorithms on tensor data sets that do not fit into the available memory and results show that the proposed techniques significantly improve the scalability of this core data analysis.

Today's data management systems increasingly need to support both tensor-algebraic operations (for analysis) as well as relational-algebraic operations (for data manipulation and integration). Tensor decomposition techniques are commonly used for discovering underlying structures of multi-dimensional data sets. However, as the relevant data sets get large, existing in-memory schemes for tensor decomposition become increasingly ineffective and, instead, memory-independent solutions, such as in-database analytics, are necessitated. We introduce an in-database analytic system for efficient implementations of in-database tensor decompositions on chunk-based array data stores, so called, TensorDB. TensorDB includes static in-database tensor decomposition and dynamic in-database tensor decomposition operators. TensorDB extends an array database and leverages array operations for data manipulation and integration. TensorDB supports complex data processing plans where multiple relational algebraic and tensor algebraic operations are composed with each other.

Tensor decomposition operation is the basis for many data analysis tasks from clustering, trend detection, anomaly detection, to correlation analysis. One key problem with tensor decomposition, however, is its computational complexity -- especially for dense data sets, the decomposition process takes exponential time in the number of tensor modes; the process is relatively faster for sparse tensors, but decomposition is still a major bottleneck in many applications. While it is possible to reduce the decomposition time by trading performance with decomposition accuracy, a drop in accuracy may not always be acceptable. In this paper, we first recognize that in many applications, the user may have a focus of interest -- i.e., part of the data for which the user needs high accuracy -- and beyond this area focus, accuracy may not be as critical. Relying on this observation, we propose a novel Personalized Tensor Decomposition(PTD) mechanism for accounting for the user's focus: PTD takes as input one or more areas of focus and performs the decomposition in such a way that, when reconstructed, the accuracy of the tensor is boosted for these areas of focus. We discuss alternative ways PTD can be implemented. Experiments show that PTD helps boost accuracy at the foci of interest, while reducing the overall tensor decomposition time.

When data are large and query processing workloads consist of data selection and aggregation operations (as in online analytical pro-cessing), column-oriented data stores are generally the preferred choice of data organization, because they enable effective data compression, leading to significantly reduced IO. Most column-store architectures leverage bitmap indices, which themselves can be compressed, for answering queries over data columns. Column-domains (e.g., geographical data, categorical data, biological tax-onomies, organizational data) are hierarchical in nature, and it may be more advantageous to create hierarchical bitmap indices, that can help answer queries over different sub-ranges of the domain. However, given a query workload, it is critical to choose the ap-propriate subset of bitmap indices from the given hierarchy. Thus, in this paper, we introduce the cut-selection problem, which aims to help identify a subset (cut) of the nodes of the domain hierar-chy, with the appropriate bitmap indices. We discuss inclusive, ex-clusive, and hybrid strategies for cut-selection and show that the hybrid strategy can be efficiently computed and returns optimal (in terms of IO) results in cases where there are no memory constraints. We also show that when there is a memory availability constraint, the cut-selection problem becomes difficult and, thus, present effi-cient cut-selection strategies that return close to optimal results, es-pecially in situations where the memory limitations are very strict (i.e., the data and the hierarchy are much larger than the available memory). Experiment results confirm the efficiency and effective-ness of the proposed cut-selection algorithms. 1.

Many applications generate and/or consume multi-variate temporal data, yet experts often lack the means to adequately and systematically search for and interpret multi-variate observations. In this paper, we first observe that multi-variate time series often carry localized multi-variate temporal features that are robust against noise. We then argue that these multi-variate temporal features can be extracted by simultaneously considering, at multiple scales, temporal characteristics of the time-series along with external knowledge, including variate relationships, known a priori. Relying on these observations, we develop algorithms to detect robust multi-variate temporal (RMT) features which can be indexed for efficient and accurate retrieval and can be used for supporting analysis tasks, such as classification. Experiments confirm that the proposed RMT algorithm is highly effective and efficient in identifying robust multi-scale temporal features of multi-variate time series.

Singular Value Decomposition (SVD) is computationally costly and therefore a naive implementation does not scale to the needs of scenarios where data evolves continuously. While there are various on-line analysis and incremental decomposition techniques, these may not accurately represent the data or may be slow for the needs of many applications. To address these challenges, in this paper, we propose a Low-rank, Windowed, Incremental SVD (LWI-SVD) algorithm, which (a) leverages efficient and accurate low-rank approximations to speed up incremental SVD updates and (b) uses a window-based approach to aggregate multiple incoming updates (insertions or deletions of rows and columns) and, thus, reduces on- line processing costs. We also present an LWI-SVD with restarts (LWI2-SVD) algorithm which leverages a novel highly efficient partial reconstruction based change detection scheme to support timely refreshing of the decomposition with significant changes in the data and prevent accumulation of errors over time. Experiment results, including comparisons to other state of the art techniques on different data sets and under different parameter settings, confirm that LWI-SVD and LWI2-SVD are both efficient and accurate in maintaining decompositions.

Personalized PageRank (PPR) based measures of node proximity have been shown to be highly effective in many prediction and recommendation applications. The use of personalized PageRank for large graphs, however, is difficult due to its high computation cost. In this paper, we propose a Locality-sensitive, Re-use promoting, approximate personalized PageRank (LR-PPR) algorithm for efficiently computing the PPR values relying on the localities of the given seed nodes on the graph: (a) The LR-PPR algorithm is locality sensitive in the sense that it reduces the computational cost of the PPR computation process by focusing on the local neighborhoods of the seed nodes. (b) LR-PPR is re-use promoting in that instead of performing a monolithic computation for the given seed node set using the entire graph, LR-PPR divides the work into localities of the seeds and caches the intermediary results obtained during the computation. These cached results are then reused for future queries sharing seed nodes. Experiment results for different data sets and under different scenarios show that LR-PPR algorithm is highly-efficient and accurate.

Did you ever return back from a conference, having met a lot of interesting folks, listened to many inspiring talks, or having your presentation welcomed with a barrage of (of course, constructive!) questions, wishing if only you managed to take record of all these during the event? We are developing the Hive Open Research Network, a social platform for fostering scientific interactions and reducing friction in scientific exchanges and the underlying integrated services supporting content personalization, preview, and social/scientific recommendations. Hive is a conference-centric, but cross-conference platform, where researchers can seed and expand their research networks, keep track of the technical research sessions they are attending, meet new colleagues, share their ideas, ask questions, give and receive comments, or simply keep and/or view records of interactions at a conference they have attended (or wanted to attend, but missed due to other commitments). In its core, Hive leverages dynamically evolving knowledge structures, including user connections, concept maps, co-authorship networks, content from papers and presentations, and contextual knowledge to create and to promote networks of peers. These peer networks support each other explicitly through direct communication or indirectly through collaborative filtering. Hive provides the following online integrated services: a) understanding the personal activity context through access patterns and analysis of user supplied content, b) context-aware resource discovery, including search, presentation, and exploration support within the scientific knowledge structures, and c) peer discovery, and peer driven resource and knowledge sharing and collaborative recommendations.

The problem of finding interesting tuples in a data set, more commonly known as the skyline problem, has been extensively studied in scenarios where the data is static. More recently, skyline research has moved towards data streaming environments, where tuples arrive/expire in a continuous manner. Several algorithms have been developed to track skyline changes over sliding windows; however, existing methods focus on skyline analysis in which all required skyline attributes belong to a single incoming data stream. This constraint renders current algorithms unsuitable for applications that require a real-time “join” operation to be carried out between multiple incoming data streams, arriving from different sources, before the skyline query can be answered. Based on this motivation, in this paper, we address the problem of computing skyline-window-join (SWJ) queries over pairs of data streams, considering sliding windows that take into account only the most recent tuples. In particular, we propose a Layered Skyline-window-Join (LSJ) operator that (a) partitions the overall process into processing layers and (b) maintains skyline-join results in an incremental manner by continuously monitoring the changes in all layers of the process. We combine the advantages of existing skyline methods (including those that efficiently maintain skyline results over a single stream, and those that compute the skyline of pairs of static data sets) to develop a novel iteration-fabric skyline-window-join processing structure. Using the iteration-fabric, LSJ eliminates redundant work across consecutive windows by leveraging shared data across all iteration layers of the windowed skyline-join processing. To the best of our knowledge, this is the first paper that addresses join-based skyline queries over sliding windows. Extensive experimental evaluations over real and simulated data show that LSJ provides large gains over naive extensions of existing schemes which are not designed to eliminate redundant work across multiple processing layers.

Efficient processing of skyline queries has been an area of growing interest over both static and stream environments. Most existing static and streaming techniques assume that the skyline query is applied to a single data source. Unfortunately, this is not true in many applications in which, due to the complexity of the schema, the skyline query may involve attributes belonging to multiple data sources. Recently, in the context of static environments, various hybrid skyline-join algorithms have been proposed. However, these algorithms suffer from several drawbacks: they often need to scan the data sources exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. On the other hand, most existing streaming methods focus on single stream skyline analysis, thus rendering these techniques unsuitable for applications that require a real-time "join" operation to be carried out before the skyline query can be answered. Based on these observations, we introduce and propose to demonstrate SkySuite: a framework of skyline-join operators that can be leveraged to efficiently process skyline-join queries over both static and stream environments. Among others, SkySuite includes (1) a novel Skyline-Sensitive Join (SSJ) operator that effectively processes skyline-join queries in static environments, and (2) a Layered Skyline-window-Join (LSJ) operator that incrementally maintains skyline-join results over stream environments.

Tensors (multidimensional arrays) are widely used for representing high-order dimensional data, in applications ranging from social networks, sensor data, and Internet traffic. Multiway data analysis techniques, in particular tensor decompositions, allow extraction of hidden correlations among multiway data and thus are key components of many data analysis frameworks. Intuitively, these algorithms can be thought of as multiway clustering schemes, which consider multiple facets of the data in identifying clusters, their weights, and contributions of each data element. Unfortunately, algorithms for fitting multiway models are, in general, iterative and very time consuming. In this article, we observe that, in many applications, there is a priori background knowledge (or metadata) about one or more domain dimensions. This metadata is often in the form of a hierarchy that clusters the elements of a given data facet (or mode). We investigate whether such single-mode data hierarchies can be used to boost the efficiency of tensor decomposition process, without significant impact on the final decomposition quality. We consider each domain hierarchy as a guide to help provide higher- or lower-resolution views of the data in the tensor on demand and we rely on these metadata-induced multiresolution tensor representations to develop a multiresolution approach to tensor decomposition. In this article, we focus on an alternating least squares (ALS)--based implementation of the two most important decomposition models such as the PARAllel FACtors (PARAFAC, which decomposes a tensor into a diagonal tensor and a set of factor matrices) and the Tucker (which produces as result a core tensor and a set of dimension-subspaces matrices). Experiment results show that, when the available metadata is used as a rough guide, the proposed multiresolution method helps fit both PARAFAC and Tucker models with consistent (under different parameters settings) savings in execution time and memory consumption, while preserving the quality of the decomposition.

Since many applications rely on time-based data, visualizing temporal data and helping experts explore large time series data sets are critical in many application domains. In this interactive system preview, we argue that time series often carry structural features that can, if efficiently identified and effectively visualized, help reduce visual overload and help the user quickly focus on the relevant portions of the data sets. Relying on this observation, we introduce a novel STFMap system, which includes four innovative query- and feature-driven time series data set visualization techniques: (a) segment-maps, (b) warp-maps, (c) stretch-maps, and (d) feature-maps. These rely on the salient temporal features of the time series and their alignments with respect to the given user query to help users explore the data set in a query-driven fashion.

For many multi-dimensional data applications, tensor operations as well as relational operations need to be supported throughout the data lifecycle. Although tensor decomposition is shown to be effective for multi-dimensional data analysis, the cost of tensor decomposition is often very high. We propose a novel decomposition-by-normalization scheme that first normalizes the given relation into smaller tensors based on the functional dependencies of the relation and then performs the decomposition using these smaller tensors. The decomposition and recombination steps of the decomposition-by- normalization scheme fit naturally in settings with multiple cores. This leads to a highly efficient, effective, and parallelized decomposition-by-normalization algorithm for both dense and sparse tensors. Experiments confirm the efficiency and effectiveness of the proposed decomposition-by-normalization scheme compared to the conventional nonnegative CP decomposition approach.

A graph neighborhood consists of a set of nodes that are nearby or otherwise related to each other. While existing definitions consider the structure (or topology) of the graph, we note that they fail to take into account the information propagation and diffusion characteristics, such as decay and reinforcement, common in many networks. In this paper, we first define the propagation efficiency of nodes and edges. We use this to introduce the novel concept of zero-erasure (or impact) neighborhood (ZEN) of a given node, n, consisting of the set of nodes that receive information from (or are impacted by) n without any decay. Based on this, we present an impact neighborhood indexing (INI) algorithm that creates data structures to help quickly identify impact neighborhood of any given node. Experiment results confirm the efficiency and effectiveness of the proposed INI algorithms.

Efficient processing of skyline queries has been an area of growing interest. Most existing techniques assume that the skyline query is applied to a single data table. Unfortunately, this is not true in many applications where, due to the complexity of the schema, the skyline query may involve attributes belonging to multiple tables. Recently, various hybrid skyline-join algorithms have been proposed. However, the current proposals suffer from several drawbacks: they often need to scan the input tables exhaustively in order to obtain the set of skyline-join results; moreover, the pruning techniques employed to eliminate the tuples are largely based on expensive pairwise tuple-to-tuple comparisons. In this paper, we aim to address these shortcomings by proposing two novel skyline-join algorithms, namely skyline-sensitive join (S 2J) and symmetric skyline-sensitive join (S 3J), to process skyline queries over multiple tables. Our approaches compute the results using a novel layer/region pruning technique (LR-pruning) that prunes the join space in blocks as opposed to individual data points, thereby avoiding excessive pairwise point-to-point dominance checks. Furthermore, the S 3J algorithm utilizes an early stopping condition in order to successfully compute the skyline results by accessing only a subset of the input tables. We report extensive experimental results that confirm the advantages of the proposed algorithms over the state-of-the-art skyline-join techniques.

Existing RDF query languages and RDF stores fail to support a large class of knowledge applications which associate utilities or costs on the available knowledge statements. A recent proposal includes (a) a ranked RDF (R2DF) specification to enhance RDF triples with an application specific weights and (b) a SPA Rank QL query language specification, which provides novel primitives on top of the SPARQL language to express top-k queries using traditional query patterns as well as novel flexible path predicates. We introduce and demonstrate R2DB, a database system for querying weighted RDF graphs. R2DB relies on the AR2Q query processing engine, which leverages novel index structures to support efficient ranked path search and includes query optimization strategies based on proximity and sub-result inter-arrival times. In addition to being the first data management system for the R2DF data model, R2DB also provides an innovative features-of-interest (FoI) based method for visualizing large sets of query results (i.e., sub graphs of the data graph).

Many applications generate and consume temporal data and retrieval of time series is a key processing step in many application domains. Dynamic time warping (DTW) distance between time series of size N and M is computed relying on a dynamic programming approach which creates and fills an N x M grid to search for an optimal warp path . Since this can be costly, various heuristics have been proposed to cut away the potentially unproductive portions of the DTW grid. In this paper, we argue that time series often carry structural features that can be used for identifying locally relevant constraints to eliminate redundant work. Relying on this observation, we propose salient feature based sDTW algorithms which first identify robust salient features in the given time series and then find a consistent alignment of these to establish the boundaries for the warp path search. More specifically, we propose alternative fixed core&adaptive width, adaptive core&fixed width , and adaptive core&adaptive width strategies which enforce different constraints reflecting the high level structural characteristics of the series in the data set. Experiment results show that the proposed sDTW algorithms help achieve much higher accuracy in DTW computation and time series retrieval than fixed core & fixed width algorithms that do not leverage local features of the given time series.

The high-dimensional nature of the textual data complicates the design of visualization tools to support exploration of large document corpora. In this article, we first argue that the Parallel Coordinates (PC) technique, which can map multidimensional vectors onto a 2D space in such a way that elements with similar values are represented as similar poly-lines or curves in the visualization space, can be used to help users discern patterns in document collections. The inherent reduction in dimensionality during the mapping from multidimensional points to 2D lines, however, may result in visual complications. For instance, the lines that correspond to clusters of objects that are separate in the multidimensional space may overlap each other in the 2D space; the resulting increase in the number of crossings would make it hard to distinguish the individual document clusters. Such crossings of lines and overly dense regions are significant sources of visual clutter, thus avoiding them may help interpret the visualization. In this article, we note that visual clutter can be significantly reduced by adjusting the resolution of the individual term coordinates by clustering the corresponding values. Such reductions in the resolution of the individual term-coordinates, however, will lead to a certain degree of information loss and thus the appropriate resolution for the term-coordinates has to be selected carefully. Thus, in this article we propose a controlled clutter reduction approach, called Parallel hierarchical Coordinates (or PhC ), for reducing the visual clutter in PC-based visualizations of text corpora. We define visual clutter and information loss measures and provide extensive evaluations that show that the proposed PhC provides significant visual gains (i.e., multiple orders of reductions in visual clutter) with small information loss during visualization and exploration of document collections.

Query processing over weighted data graphs often involves searching for a minimum weighted subgraph --a tree-- which covers the nodes satisfying the given query criteria (such as a given set of keywords). Existing works often focus on graphs where the edges have scalar valued weights. In many applications, however, edge weights need to be represented as ranges (or intervals) of possible values. In this paper, we introduce the problem of skynets, for searching minimum weighted subgraphs, covering the nodes satisfying given query criteria, over interval-weighted graphs. The key challenge is that, unlike scalars which are often totally ordered, depending on the application specific semantics of the ≤ operator, intervals may be partially ordered. Naturally, the need to maintain alternative, incomparable solutions can push the computational complexity of the problem (which is already high for the case with totally ordered scalar edge weights) even higher. In this paper, we first provide alternative definitions of the ≤ operator for intervals and show that some of these lend themselves to efficient solutions. To tackle the complexity challenge in the remaining cases, we propose two optimization criteria that can be used to constrain the solution space. We also discuss how to extend existing approximation algorithms for Steiner trees to discover solutions to the skynet problem. For efficient calculation of the results, we introduce a novel skyline union operator. Experiments show that the proposed approach achieves significant gains in efficiency, while providing close to optimal results.

In this paper, we first introduce a tensor-based relational data model and define algebraic operations on this model. We note that, while in traditional relational algebraic systems the join operation tends to be the costliest operation of all, in the tensor-relational framework presented here, tensor decomposition becomes the computationally costliest operation. Therefore, we consider optimization of tensor decomposition operations within a relational algebraic framework. This leads to a highly efficient, effective, and easy-to-parallelize join-by-decomposition approach and a corresponding KL-divergence based optimization strategy. Experimental results provide evidence that minimizing KL-divergence within the proposed join-by-decomposition helps approximate the conventional join-then-decompose scheme well, without the associated time and space costs.

Tensors (multi-dimensional arrays) are widely used for representing high-order dimensional data, in applications ranging from social networks, sensor data, and Internet traffic. Multi-way data analysis techniques, in particular tensor decompositions, allow extraction of hidden correlations among multi-way data and thus are key components of many data analysis frameworks. Intuitively, these algorithms can be thought of as multi-way clustering schemes, which consider multiple facets of the data in identifying clusters, their weights, and contributions of each data element. Unfortunately, algorithms for fitting multi-way models are, in general, iterative and very time consuming. In this paper, we observe that, in many applications, there is a priori background knowledge (or metadata) about one or more domain dimensions. This metadata is often in the form of a hierarchy that clusters the elements of a given data facet (or mode). In this paper, we investigate whether such single-mode data hierarchies can be used to boost the efficiency of tensor decomposition process, without significant impact on the final decomposition quality. We consider each domain hierarchy as a guide to help provide higher- or lower-resolution views of the data in the tensor on demand and we rely on these metadata-induced multi-resolution tensor representations to develop a multiresolution approach to tensor decomposition. In this paper, we focus on an alternating least squares (ALS) based implementation of the PARAllel FACtors (PARAFAC) decomposition (which decomposes a tensor into a diagonal tensor and a set of factor matrices). Experiment results show that, when the available metadata is used as a rough guide, the proposed multiresolution method helps fit PARAFAC models with consistent (for both dense and sparse tensor representations, under different parameters settings) savings in execution time and memory consumption, while preserving the quality of the decomposition.

The popularity of batch-oriented cluster architectures like Hadoop is on the rise. These batch-based systems successfully achieve high degrees of scalability by carefully allocating resources and leveraging opportunities to parallelize basic processing tasks. However, they are known to fall short in certain application domains such as large scale media analysis. In these applications, the utility of a given data element plays a vital role in a particular analysis task, and this utility most often depends on the way the data is collected or interpreted. However, existing batch data processing frameworks do not consider data utility in allocating resources, and hence fail to optimize for ranked/top-k query processing in which the user is interested in obtaining a relatively small subset of the best result instances. A naïve implementation of these operations on an existing system would need to enumerate more candidates than needed, before it can filter out the k best results. We note that such waste can be avoided by utilizing utility-aware task partitioning and resource allocation strategies that can prune unpromising objects from consideration. In this demonstration, we introduce RanKloud, an efficient and scalable utility-aware parallel processing system built for the analysis of large media datasets. RanKloud extends Hadoop's MapReduce paradigm to provide support for ranked query operations, such as k-nearest neighbor and k-closest pair search, skylines, skyline-joins, and top-k join processing.

We present the pattern development view (pDView) system for multidimensional scientific data visualization. The pDView system relies on a novel pattern development tree (pDTree) structure to unravel patterns in multidimensional data without having to rely on visualizations that require either significant degrees of projections that eliminate certain dimensions at the expense of the others or introduce significant visual overhead due to overly-rich multi-dimensional graphic interfaces. Instead, pDView maps data along all its relevant dimensions onto a pDTree structure, capturing and visualizing the underlying fundamental relationships. The user is able to vary contextual parameters to observe the strength and robustness of these relationships under different situations.

Taxonomies embody formalized knowledge and define aggregations between concepts/categories in a given domain, facilitating the organization of the data and making the contents easily accessible to the users. Since taxonomies have significant roles in the data annotation, search and navigation, they are often carefully engineered. However, especially in very dynamic content, they do not necessarily reflect the content knowledge. Thus, in this paper, we propose A Narrative Interpretation of Taxonomies for their Adaptation (ANITA) for re-structuring existing taxonomies to varying application contexts and we evaluate the proposed scheme by user studies that show that the proposed algorithm is able to adapt the taxonomy in a new compact and understandable structure from a human point of view.

Since the visualization real estate puts stringent constraints on how much data can be presented to the users at once, table summarization is an essential tool in helping users quickly explore large data sets. An effective summary needs to minimize the information loss due to the reduction in details. Summarization algorithms leverage the redundancy in the data to identify value and tuple clustering strategies that represent the (almost) same amount of information with a smaller number of data representatives. It has been shown that, when available, metadata, such as value hierarchies associated to the attributes of the tables, can help greatly reduce the resulting information loss. However, table summarization, whether carried out through data analysis performed on the table from scratch or supported through already available metadata, is an expensive operation. We note that the table summarization process can be significantly sped up when the metadata used for supporting the summarization itself is pre-processed to reduce the unnecessary details. The pre-processing of the metadata, however, needs to be performed carefully to ensure that it does not add significant amounts of additional loss to the table summarization process. In this paper, we propose a tRedux algorithm for value hierarchy pre-processing and reduction. Experimental evaluations show that, depending on the table and taxonomy complexity, metadata summarization can provide gains in table summarization time that can range (in absolute values) from seconds to 10s-of-1000s of seconds. Consequently, while resulting in only an extra ~ 20% reduction in table quality, tRedux can provide ~ 2x speedups in table summarization time. Experiments also show that tRedux has a better performance than alternative metadata reduction strategies in supporting table summarization; and, as the taxonomy complexity increases, the absolute gains of tRedux also increase.

Feedback process has been used extensively in document-centric applications, such as text retrieval and multimedia retrieval. Recently, there have been efforts to apply feedback to semi-structured XML document collections as well. In this paper, we note that feedback can also be an effective tool for exploring (through result ranking and query refinement) large semi-structured data collections. In particular, in large scale data sharing and curation environments, where the user may not know the structure of the data, queries may initially be overly vague. Given a path query and a set of results identified by the system to this query over the data, we consider two types of feedback: Soft feedback captures the user's preference for some features over the others. Hard feedback, on the other hand, expresses users' assertions regarding whether certain features should be further enforced or, in contrast, are to be avoided. Both soft and hard feedback can be "positive" or "negative". For soft feedback, we develop a probabilistic feature significance measure and describe how to use this for ranking results in the presence of dependencies between the path features. To deal with the hard feedback efficiently (i.e., fast enough for interactive exploration), we present finite automata based query refinement solutions. In particular, we present a novel LazyDFA+ algorithm for managing hard feedback. We also describe optimizations that leverage the inherently iterative nature of the feedback process. We bring together these techniques in AXP, a system for adaptive and exploratory path retrieval. The experimental results show the effectiveness of the proposed techniques.

Complex media fusion operations can be costly in terms of the time they need to process input objects. If data arrive faster to fusion nodes than the speed with which they can consume the inputs, this will result in some input objects not being processed. In this paper, we develop load shedding mechanisms which take into consideration both data quality and expensive nature of media fusion operators. In particular, we present quality assessment models for objects and multistream fusion operators and highlight that such quality assessments may impose partial orders on objects. We highlight that the most effective load control approach for fusion operators involves shedding of (not the individual input objects but) combinations of objects. Yet, identifying suitable combinations of objects in real time will not be possible if efficient combination selection algorithms do not exist. We develop efficient combination selection schemes for scenarios with different quality assessment and target characteristics. We first develop efficient combination-based load shedding when the fusion operator has unambiguously monotone semantics. We then extend this to the more general ambiguously monotone case and present experimental results that show the performance gains using quality-aware combination-based load shedding strategies under the various fusion scenarios.

Feedback driven data exploration schemes have been implemented for non-structured data (such as text) and document-centric XML collections where formulating precise queries is often impossible. In this paper, we study the problem of enabling exploratory access, through ranking, to data-centric XML. Given a path query and a set of results identified by the system to this query over the data, we consider feedback which captures the user's preference for some features over the others. The feedback can be "positive" or "negative". To deal with feedback, we develop a probabilistic feature significance measure and describe how to use this for ranking results in the presence of dependencies between the path features. We bring together these techniques in AXP, a system for adaptive and exploratory path retrieval. The experimental results show the effectiveness of the proposed techniques.

Consider a scientist who wants to explore multiple data sets to select the relevant ones for further analysis. Since the visualization real estate may put a stringent constraint on how much detail can be presented to this user in a single page, effective table summarization techniques are needed to create summaries that are both sufficiently small and effective in communicating the available content. In this paper, we first argue that table summarization can benefit from knowledge about acceptable value clustering alternatives for clustering the values in the database. We formulate the problem of table summarization with the help of value lattices. We then provide a framework to express alternative clustering strategies and to account for various utility measures (such as information loss) in assessing different summarization alternatives. Based on this interpretation, we introduce three preference criteria, max-min-util (cautious), max-sum-util (cumulative), and pareto-util, for the problem of table summarization. To tackle with the inherent complexity, we rely on the properties of the fuzzy interpretation to further develop a novel ranked set cover based evaluation mechanism (RSC). These are brought together in an AlphaSum, table summarization system. Experimental evaluations showed that RSC improves both execution times and the summary qualities in AlphaSum, by pruning the search space more effectively than the existing solutions.

In this paper, we introduce AURA, a novel framework for enriching the physical environment with information about objects and activities in order to support searches in the physical world. The goal is to enable individuals to use the environment in which they function as a living (short-term) memory of their activities and of the objects with which they interact in this environment. In order to act as a memory, the physical environment must be transparently embedded with relevant information and made accessible by in-situ search mechanisms. We achieve this embedding through innovative algorithms that leverage a collection of parasitic RFID tags distributed in the environment to act as a distributed storage cloud. Information about the activities of the users and objects with which they interact are encoded and stored, in a decentralized way, on these RFID tags to support attribute-based search. A novel auraProp algorithm disseminates information in the environment and a complementary auraSearch algorithm implements spatial searches for physical objects in the environment. Parasitic RFID tags are not self-powered and thus cannot communicate among each other. AURA leverages human movement in the environment to propagate information: as they move in the environment, users not only leave traces (or auras) of their own activities, but also help further disseminate auras of prior activities in the same space. AURA relies on a novel signature based information dissemination mechanism and a randomized information erasure scheme to ensure that the extremely limited storage spaces available on the RFID tags are used effectively. The erasure scheme also helps create an information gradient in the physical environment, which the auraSearch algorithm uses to direct the user towards the object of interest.

The high cost of creating and maintaining software and hardware infrastructures for delivering services to businesses has led to a notable trend toward the use of third-party service providers, which rent out network presence, computation power, and data storage space to clients with infrastructural needs. These third party service providers can act as data stores as well as entire software suites for improved availability and system scalability, reducing small and medium businesses' burden of managing complex infrastructures. This is called information/application outsourcing or software as a service (SaaS). Emergence of enabling technologies, such as service oriented architectures (SOA), virtual machines, and cloud computing, contribute to this trend. Scientific Grid computing, on-line software services, and business service networks are typical examples leveraging database and software as service paradigm. In this paper, we survey the technologies used to enable SaaS paradigm as well as the current offerings on the market. We also outline research directions in the field.

The tasks in the physical environments are mainly information centric processes, such as search and exploration of physical objects. We have developed an informational environment, AURA that supports object searches in the physical world. The goal of AURA is to enable individuals to use the environment in which they function as a living (short-term) memory of their activities and of the objects with which they interact in this environment. To support physical searches, the environment that the user is occupying must be transparently embedded with relevant information and made accessible by in-situ search mechanisms. We achieve this through innovative algorithms that re-imagine a collection of environmentally distributed RFID tags to act as a distributed storage cloud that encodes the required information for attribute-based object search. Since RFID tags lack radio transmitters and, thus, cannot communicate among each other, auraProp and auraSearch leverage the movements of the humans in the environment to propagate information: as they move in the environment, users not only leave traces (or auras) of their own activities, but also help further disseminate auras of prior activities in the same space. This scheme creates an information-gradient in the physical environment which AURA then leverages to direct the user toward the object of interest. auraSearch significantly reduces the number of steps that the user has to walk while searching for a given object.

Counting is a common task in many data mining applications, including market basket data analysis, scientific inquiry, and other high dimensional data management applications. Given a single table, obtaining the instance counts of the entries in the table is relatively cheap. In situations where the attributes of interest are distributed across different tables, however, the problem of computing instance counts can be very expensive. The naive solution, joining all the relevant relations to obtain a single table suitable for counting, is rarely practical. In this paper, we propose PICC (Propagation-based Instance Counts on Concise Graphs), a novel counting technique for discovering instance counts in databases. We first propose a propagation-based instance counting scheme which avoids joins to obtain a single table. We then present a method for summarizing a database into a concise synopsis and describe how to use this along with the propagation scheme to estimate the required counts efficiently. The experiment results show that the proposed technique, PICC, provides significant execution time and accuracy gains over the existing solutions to this problem.

Keyword search and ranked retrieval together emerged as popular data access paradigms for various kinds of data, from web pages to XML and relational databases. A user can submit keywords without knowing much (sometimes nothing) about the complex structure underlying a data collection, yet the system can identify, rank, and return a set of relevant matches by exploiting statistics about the distribution and structure of the data. Keyword-based data models are also suitable for capturing user's search context in terms of weights associated to the keywords in the query. Given a search context, the data in the database can also be re-interpreted for semantically correct retrieval. This option, however, is often ignored as the cost of re-assessing the content in the database naively tends to be prohibitive. In this paper, we first argue that top-k query processing can help tackle this challenge by re-assessing only the relevant parts of the database, efficiently. A road-block in this process, however, is that most efficient implementations of top-k query processing assume that the scoring function is monotonic, whereas the cosine-based scoring function needed for re-interpretation of content based on user context is not. In this paper, we develop an efficient top-k query processing algorithm, skip-and-prune (SnP), which is able to process top-k queries under cosine-based non-monotonic scoring functions. We compare the use of proposed algorithm against the alternative implementations of the context-aware retrieval, including naive top-k, accumulator-based inverted files, and full-scan. The experiment results show that while being fast, naive top-k is not an effective solution due to the non-monotonicity of underlying scoring function. The proposed technique, SnP, however, matches the precision of accumulator-based inverted files and full-scan, yet it is orders of magnitude faster than these.

The use of blogs to track and comment on real world (political, news, entertainment) events is growing. Similarly, as more individuals start relying on the Web as their primary information source and as more traditional media outlets try reaching consumers through alternative venues, the number of news sites on the Web is also continuously increasing. Content-reuse, whether in the form of extensive quotations or content borrowing across media outlets, is very common in blogs and news entries outlets tracking the same real-world event. Knowledge about which web entries re-use content from which others can be an effective asset when organizing these entries for presentation. On the other hand, this knowledge is not cheap to acquire: considering the size of the related space web entries, it is essential that the techniques developed for identifying re-use are fast and scalable. Furthermore, the dynamic nature of blog and news entries necessitates incremental processing for reuse detection. In this paper, we develop a novel qSign algorithm that efficiently and effectively analyze the blogosphere for quotation and reuse identification. Experiment results show that with qSign processing time gains from 10X to 100X are possible while maintaining reuse detection rates of upto 90%. Furthermore, processing time gains can be pushed multiple orders of magnitude (from 100X to 1000X) for 70% recall.

While navigation within complex information spaces is a problem for all users, the problem is most evident with individuals who are blind who cannot simply locate, point, and click on a link in hypertext documents with a mouse. Users who are blind have to listen searching for the link in the document using only the keyboard and a screen reader program, which may be particularly inefficient in large documents with many links or deep hierarchies that are hard to navigate. Consequently, they are especially penalized when the information being searched is hidden under multiple layers of indirections. In this article, we introduce a segment-enrich-annotate (SEA) paradigm for adapting digital content with deep structures for improved accessibility. In particular, we instantiate and evaluate this paradigm through the iCare-Assistant, an assistive system for helping students who are blind in accessing Web and electronic course materials. Our evaluations, involving the participation of students who are blind, showed that the iCare-Assistant system, built based on the SEA paradigm, reduces the navigational overhead significantly and enables user who are blind access complex online course servers effectively.

Table summarization is necessary in various scenarios where it is hard to display a large table. It can benefit from knowledge about acceptable value clustering alternatives. In this paper, we formulate the problem of table summarization with the help of domain knowledge lattices. We provide the outline of a fuzzy mechanism to express alternative clustering strategies. We further sketch a novel ranked set cover based evaluation mechanism (RSC) to tackle with the inherent complexity.

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.

We present the tagFlake system, which supports semantically informed navigation within a tag cloud. tagFlake relies on TMine for organizing tags extracted from textual content in hierarchical organizations, suitable for navigation, visualization, classification, and tracking. TMine extracts the most significant tag/terms from text documents and maps them onto a hierarchy in such a way that descendant terms are contextually dependent on their ancestors within the given corpus of documents. This provides tagFlake with a mechanism for enabling navigation within the tag space and for classification of the text documents based on the contextual structure captured by the created hierarchy. tagFlake is language neutral, since it does not rely on any natural language processing technique and is unsupervised.

OLAP is an important tool in decision support. With the help of domain knowledge, such as hierarchies of attribute values, OLAP helps the user observe the effects of various decisions. One assumption of most OLAP operations is that the available domain knowledge is precise. In particular, they assume that the hierarchy of values over which the user can navigate forms a taxonomy. In this paper, we first note that when multiple heterogeneous data sources are involved in the gathering of the data and the associated domain knowledge, the integrated knowledge-base, constructed by combining locally available taxonomies based on the concept matchings, may not be a taxonomy itself. Specifically, existence of intersections among concepts from different sources compromises the tree-structure of the integrated taxonomy and prevents effective use of hierarchical navigation techniques, such as drill-down and roll-up. To cope with this, we introduce concept un-classification, where a select few of the concepts are eliminated to ensure that the remaining structure is a navigable taxonomy, without concept intersections. Since un-classifying an originally classified data is not desirable, we consider ways to minimize un-classification in the process. We introduce a cost model which captures the imprecision caused by the un-classification process and we formulate the problem of finding an un-classification strategy which eliminates intersections and which adds minimal imprecision to the resulting structure. We show that, when performed naively, this task can be very costly and thus we propose a bottom-up preprocessing strategy which supports basic navigational analytics operations, such as drill-down and roll-up. Experiments over synthetic and real-life data verified the effectiveness and efficiency of our approach.

The UQBE is a mashup tool for non-programmers that supports query-by-example (QBE) over a schema made up by the user without knowing the schema of the original sources. Based on automated schema matching with uncertainty, the UQBE system returns the best confident results. The system lets the user refine them interactively. A tuple in the query result is associated with lineage that is a boolean formula over schema matching decisions representing underlying conditions on which the corresponding tuple is included in the result. Given binary feedbacks on tuples by the user, which are possibly imprecise, the system solves it as an optimization problem to refine confidence values of matching decisions. The demo features graphical user interaction on the UQBE system, including querying and refinement.

An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex Generalized-Tree-Pattern (GTP) queries. Our filtering mechanism is based on a novel Tree-of-Path (TOP) encoding scheme, which compactly represents the path matches for the entire document. First, we show that the TOP encodings can be efficiently produced via a shared bottom-up path matching. Second, with the aid of this TOP encoding, we can 1) achieve polynomial time and space complexity for post processing, 2) avoid redundant predicate evaluations, 3) allow an efficient duplicate-free and merge join-based algorithm for merging multiple encoded path matches and 4) simplify the processing of GTP queries. Overall our approach maximizes the sharing opportunity across queries by exploiting the suffix as well as prefix sharing. At the same time, our TOP encodings allow efficient post processing for GTP queries. Extensive performance studies show that our GFilter solution not only achieves significantly better filtering performance than state-of-the-art algorithms, but also is capable of efficiently filtering the more complex GTP queries.

Basic message processing tasks, such as well-formedness checking and grammar validation, can be off-loaded from the service providers' own infrastructures. To enable effective off-loading of processing tasks, we introduce the Prefix Automata SyStem - PASS, a middleware architecture which distributively processes XML payloads of Web service SOAP messages during their routing towards Web servers. PASS is based on a network of automata, where PASS-nodes independently but cooperatively process parts of the SOAP message XML payload.

In situ wireless sensor networks, not only have to route sensed data from sources to destinations, but also have to filter and fuse observations to eliminate potentially irrelevant data. If data arrive faster to such fusion nodes than the speed with which they can consume the inputs, this will result in an overflow of input buffers. In this paper, we develop load shedding mechanisms which take into consideration both data quality and expensive nature of fusion operators. In particular, we present quality assessment models for objects and fusion operators and we highlight that such quality assessments may impose partial orders on objects.

A critical reality in data integration is that knowledge from different sources may often be conflicting with each other. Conflict resolutioncan be costly and, if done without proper context, can be ineffective. In this paper, we propose a novel query-driven and feedback-based approach (FICSR1) to conflict resolution when integrating data sources. In particular, instead of relying on traditional model based definition of consistency, we introduce a ranked interpretation. This not only enables FICSR to deal with the complexity of the conflict resolution process, but also helps achieve a more direct match between the users' (subjective) interpretation of the data and the system's (objective) treatment of the available alternatives. Consequently, the ranked interpretation leads to new opportunities for bi-directional (data informsover ↔ user) feedback cycle for conflict resolution: given a query, (a) a preliminary ranking of candidate results on data can inform the user regarding constraints critical to the query, while (b) user feedback regarding the ranks can be exploited to inform the system about user's relevant domain knowledge. To enable this feedback process, we develop data structures and algorithms for efficient off-line conflict/agreement analysis of the integrated data as well as for on-line query processing, candidate result enumeration, and validity analysis. The results are brought together and evaluated in the FICSR system.

We present the QUery-driven Exploration of Semistructured dataand meta-data with conflicTs and partial knowledge (QUEST) system for supporting the integration of scientific data and taxonomies in the presence of misalignments and conflicts. QUEST relies on a novel constraint-based data model that captures both value and structural conflicts and enables researchers to observe and resolve such misalignments in the integrated data by considering the context provided by the data requirements of given research questions.

Mashup Feeds is a system that supports integrated web service feeds as continuous queries. We introduce collection-based stream processing semantics to enable information extraction by monitoring source evolution over time.

Extracting a query-oriented snippet (or passage) and highlighting the relevant information in long document can help reduce the result navigation cost of end users. While the traditional approach of highlighting matching keywords helps when the search is keyword oriented, finding appropriate snippets to represent matches to more complex queries requires novel techniques that can help characterize the relevance of various parts of a document to the given query, succinctly. In this paper, we present a languagemodel based method for accurately detecting the most relevant passages of a given document. Unlike previous works in passage retrieval which focus on searching relevance nodes for filtering of preoccupied passages, we focus on query-informed segmentation for snippet extraction. The algorithms presented in this paper are currently being deployed in OASIS, a system to help reduce the navigational load of blind users in accessing Web-based digital libraries.

Domain specific ontologies are heavily used in many applications. For instance, these form the bases on which similarity/dissimilarity between keywords are extracted for various knowledge discovery and retrieval tasks. Existing similarity computation schemes can be categorized as (a) structure- or (b) information-based approaches. Structure based approaches compute dissimilarity between keywords using a (weighted) count of edges between two keywords. Information-base approaches, on the other hand, leverage available corpora to extract additional information, such as keyword frequency, to achieve better performance in similarity computation than structure-based approaches. Unfortunately, in many application domains (such as applications that rely on unique-keys in a relational database), frequency information required by information-based approaches does not exist. In this paper, we note that there is a third way of computing similarity: if each node in a given hierarchy can be represented as a vector of related concepts, these vectors could be compared to compute similarities. This requires mapping concept-nodes in a given hierarchy onto a concept space. In this paper, we propose a concept propagation (CP) scheme, which relies on the semantical relationships between concepts implied by the structure of the hierarchy to annotate each concept-node with a concept-vector (CV). We refer to this approach as CP/CV. Comparison of keyword similarity results shows that CP/CV provides significantly better (upto 33%) results than existing structure-based schemes. Also, even if CP/CV does not assume the availability of an appropriate corpus to extract keyword frequency information, our approach matches (and slightly improves on) the performance of information-based approaches.

Current federated systems deploy cost-based query optimization mechanisms; i.e., the optimizer selects a global query plan with the lowest cost to execute. Thus, cost functions influence what remote sources (i.e. equivalent data sources) to access and how federated queries are processed. In most federated systems, the underlying cost model is based on database statistics and query statements; however, the system load of remote sources and the dynamic nature of the network latency in wide area networks are not considered. As a result, federated query processing solutions can not adapt to runtime environment changes, such as network congestion or heavy workloads at remote sources. We present a novel system architecture that deploys a query cost calibrator to calibrate the cost function based on system load and network latency at the remote sources and consequently indirectly "influences" query routing and load distribution in federated information systems.

Caching data by maintaining materialized views typically requires updating the cache appropriately to reflect dynamic source updates. Extensive research has addressed the problem of incremental view maintenance for relational data but only few works have addressed it for semi-structured data. In this paper we address the problem of incremental maintenance of views defined over XML documents using path-expressions. The approach described in this paper has the following main features that distinguish it from the previous works: (1) The view specification language is powerful and standardized enough to be used in realistic applications. (2) The size of the auxiliary data maintained with the views depends on the expression size and the answer size regardless of the source data size.(3) No source schema is assumed to exist; the source data can be any general well-formed XML document. Experimental evaluation is conducted to assess the performance benefits of the proposed approach.

Message hierarchies in web discussion boards grow with new postings. Threads of messages evolve as new postings focus within or diverge from the original themes of the threads. Thus, just by investigating the subject headings or contents of earlier postings in a message thread, one may not be able to guess the contents of the later postings. The resulting navigation problem is further compounded for blind users who need the help of a screen reader program that can provide only a linear representation of the content. We see that, in order to overcome the navigation obstacle for blind as well as sighted users, it is essential to develop techniques that help identify how the content of a discussion board grows through generalizations and specializations of topics. This knowledge can be used in segmenting the content in coherent units and guiding the users through segments relevant to their navigational goals. Our experimental results showed that the segmentation algorithm described in this paper provides up to 80-85% success rate in labeling messages. The algorithm is being deployed in a software system to reduce the navigational load of blind students in accessing web-based electronic course materials; however, we note that the techniques are equally applicable for developing web indexing and summarization tools for users with sight.

For most Web-based applications, contents are created dynamically based on the current state of a business, such as product prices and inventory, stored in database systems. These applications demand personalized content and track user behavior while maintaining application integrity. Many of such practices are not compatible with Web acceleration solutions. Consequently, although many web acceleration solutions have shown promising performance improvement and scalability, architecting and engineering distributed enterprise Web applications to utilize available content delivery networks remains a challenge. In this paper, we examine the challenge to accelerate J2EE-based enterprise web applications. We list obstacles and recommend some practices to transform typical database-driven J2EE applications to cache friendly Web applications where Web acceleration solutions can be applied. Furthermore, such transformation should be done without modification to the underlying application business logic and without sacrificing functions that are essential to e-commerce. We take the J2EE reference software, the Java PetStore, as a case study. By using the proposed guideline, we are able to cache more than 90% of the content in the PetStore and scale up the Web site more than 20 times.

With the wide availability of content delivery networks, many e-commerce Web applications utilize edge cache servers to cache and deliver dynamic contents at locations much closer to users, avoiding network latency. By caching a large number of dynamic content pages in the edge cache servers, response time can be reduced, benefiting from higher cache hit rates. However this is achieved at the expense of higher invalidation cost. On the other hand, a higher invalidation cost leads to a longer invalidation cycle (time to perform the invalidation check on the pages in caches) at the expense of freshness of cached dynamic content. In this paper we propose a freshness-driven adaptive dynamic content caching technique, which monitors response time and invalidation cycle length and dynamically adjusts caching policies. We have implemented the proposed technique within NECs CachePortal Web acceleration solution. The experimental results show that the proposed technique consistently maintains the best content freshness to users. The experimental results also show that even a Web site with dynamic content caching enabled can further benefit from deployment of our solution with improvement of its content freshness up to 10 times especially during heavy traffic.

Wide-area database replication technologies and the availability of content delivery networks allow Web applications to be hosted and served from powerful data centers. This form of application support requires a complete Web application suite to be distributed along with the database replicas. A major advantage of this approach is that dynamic content is served from locations closer to users, leading into reduced network latency and fast response times. However, this is achieved at the expense of overheads due to (a) invalidation of cached dynamic content in the edge caches and (b) synchronization of database replicas in the data center. These have adverse effects on the freshness of delivered content. In this paper, we propose a freshness-driven adaptive dynamic content caching, which monitors the system status and adjusts caching policies to provide content freshness guarantees. The proposed technique has been intensively evaluated to validate its effectiveness. The experimental results show that the freshness-driven adaptive dynamic content caching technique consistently provides good content freshness. Furthermore, even a Web site that enables dynamic content caching can further benefit from our solution, which improves content freshness up to 7 times, especially under heavy user request traffic and long network latency conditions. Our approach also provides better scalability and significantly reduced response times up to 70% in the experiments.

Since the Web encourages hypertext and hypermedia document authoring (e.g., HTML or XML), Web authors tend to create documents that are composed of multiple pages connected with hyperlinks. A Web document may be authored in multiple ways, such as: (1) all information in one physical page, or (2) a main page and the related information in separate linked pages. Existing Web search engines, however, return only physical pages containing keywords. We introduce the concept of information unit, which can be viewed as a logical Web document consisting of multiple physical pages as one atomic retrieval unit. We present an algorithm to efficiently retrieve information units. Our algorithm can perform progressive query processing. These functionalities are essential for information retrieval on the Web and large XML databases. We also present experimental results on synthetic graphs and real Web data.

Web performance is a key differentiation among content providers. Snafus and slowdowns at major web sites demonstrate the difficulty that companies face trying to scale to a large amount of web traffic. One solution to this problem is to store web content at server-side and edge-caches for fast delivery to the end users. However, for many e-commerce sites, web pages are created dynamically based on the current state of business processes, represented in application servers and databases. Since application servers, databases, web servers, and caches are independent components, there is no efficient mechanism to make changes in the database content reflected to the cached web pages. As a result, most application servers have to mark dynamically generated web pages as non-cacheable. In this paper, we describe the architectural framework of the CachePortal system for enabling dynamic content caching for database-driven e-commerce sites. We describe techniques for intelligently invalidating dynamically generated web pages in the caches, thereby enabling caching of web pages generated based on database contents. We use some of the most popular components in the industry to illustrate the deployment and applicability of the proposed architecture.

Article Retrieving and organizing web pages by "information unit" Share on Authors: Wen-Syan Li C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CA C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CAView Profile , K. Selçuk Candan C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CA C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CAView Profile , Quoc Vu C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CA C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CAView Profile , Divyakant Agrawal C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CA C&C Research Laboratories, NE, Inc., 110 Rio Robles, M/S SJ100, San Jose, CAView Profile Authors Info & Claims WWW '01: Proceedings of the 10th international conference on World Wide WebMay 2001 Pages 230–244https://doi.org/10.1145/371920.372057Online:01 April 2001Publication History 66citation1,478DownloadsMetricsTotal Citations66Total Downloads1,478Last 12 Months11Last 6 weeks3 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

Image data is structurally more complex than traditional types of data. An image can be viewed as a compound object containing many sub-objects. Each sub-object corresponds to image regions that are visually and semantically meaningful (e.g. car, man, etc.). We introduce a hierarchical structure for image modeling that supports image retrieval, at both the whole-image and object levels, using combinations of semantic expressions and visual examples. We introduce an image database system called SEMCOG (SEMantics and COGnition-based image retrieval). SEMCOG aims at integrating semantics- and cognition-based approaches and allows queries based on object-level information. We present a formal definition of a multimedia query language, we give details of the database's implementation and query processing, and we discuss our methods for merging similarities from different types of query criteria.

Multimedia documents are composed of different data types such as video, audio, text, and images. Authoring a multimedia document is a creative exercise. Unlike traditional computer supported collaborative work where documents are composed of static objects, multimedia documents have temporal and spatial requirements that must be supported by any collaborative multimedia platform. In this paper, we show that most requirements (including temporal and spatial) for collaborative multimedia authoring systems can be expressed in terms of a highly structured class of linear constraints called prioritized difference constraints. Based on our prioritized difference constraint-based characterization, we develop efficient, incremental algorithms for creating and modifying multimedia documents so as to satisfy the required temporal and spatial constraints. We further develop methods to identify inconsistent requirements, and show how such inconsistencies may be removed through constraint relaxation techniques. We also report on the collaborative heterogeneous interactive multimedia platform (CHIMP) system developed using the framework described. © 1998 John Wiley & Sons, Inc.

When a group {/1,..., l/sub n/} of individuals wishes to collaboratively construct a complex multimedia document, the first requirement is that they be able to manipulate media-objects created by one another. For instance, if individual L/sub j/ wishes to access some media objects present at participant l/sub k/'s site, he must be able to: 1) retrieve this object from across the network, 2) ensure that the object is in a form that is compatible with the viewing/editing resources he has available at his node, and 3) ensure that the object has the desired quality (such as image size and resolution). Furthermore, he must be able to achieve these goals at the lowest possible cost. In this paper, we develop a theory of media objects, and present optimal algorithms for collaborative object sharing/synthesis of the sort envisaged above. We then extend the algorithms to incorporate quality constraints (such as image size) as well as distribution across multiple nodes. The theoretical model is validated by an experimental implementation that supports the theoretical results.

2 SEMCOG Approach We argue that image retrieval based on either approach alone is not sufficient in terms of modeling and query specification flexibility y. We also argue that a visual query interface which is capability of visualizing target images is essential. SEMCOG[l] (SEMantics and COGnitionbased image retrieval) aims at integrating semautics and cognition-based approaches to give users a greater flexibility to pose queries. SEMCOG’S image matching is based on objects in the images rather than the whole images. In SEMCOG, a query “Retrieve all images in which there is a man to the right of a car and the man looks like this image” can be posed using combinations of semantics and visual expressions. The queries are posed in the way of specifying image objects and their layouts using a visual query interface, IFQ (In Frame Query), rather than complicated multimedia database query languages. The user’s query can be simplified as a mental model shown at the top of Figure 1. She then specifies her mental model using IFQ using combinations of visual examples or semantics. IFQ window shows a query “Retrieve

With the evolution of the information superhighway, there is now an immense amount of information available in a wide variety of databases. Furthermore, users often have the ability to access legacy software packages developed by external sources. However, sometimes both the information provided by a data source, as well as one or more of the functions available through a software package may be sensitive-in such cases, organizations require that access by users be controlled. HERMES (HEterogeneous Reasoning and MEdiator System) is a platform that has been developed at the University of Maryland within which mediators may be designed and implemented. HERMES has already been used for a number of applications. In this paper, we provide a formal model of security in mediated systems. We then develop techniques that are sound and complete and respect security constraints of packages/databases participating in the mediated system. The security constraints described an this paper have been implemented, and we describe the existing implementation.

Query processing and optimization in mediator systems that access distributed non-proprietary sources pose many novel problems. Cost-based query optimization is hard because the mediator does not have access to source statistics information and furthermore it may not be easy to model the source's performance. At the same time, querying remote sources may be very expensive because of high connection overhead, long computation time, financial charges, and temporary unavailability. We propose a cost-based optimization technique that caches statistics of actual calls to the sources and consequently estimates the cost of the possible execution plans based on the statistics cache. We investigate issues pertaining to the design of the statistics cache and experimentally analyze various tradeoffs. We also present a query result caching mechanism that allows us to effectively use results of prior queries when the source is not readily available. We employ the novel invariants mechanism, which shows how semantic information about data sources may be used to discover cached query results of interest.