With the rapid proliferation of short-video platforms and content-driven social networks, sequential recommendation models capable of accurately capturing user interests have become increasingly crucial. Among these, Transformer-based sequential recommendation models have gained widespread adoption due to their superior ability. The positional encoding (PE) in Transformer architectures serves to incorporate positional information into sequences. However, relying solely on original absolute positional information may be insufficient for sequential recommendation models. In contrast, the dwell time after interactions (i.e., the time intervals between consecutive user interactions) provides a more accurate reflection of users' emotional responses and evolving interests. Despite its significance, this aspect has often been overlooked in existing works. To fully utilize this information, our work introduces an adaptive PE method, termed TSAPE (Temporal-Series-Aware Positional Encoding). This approach introduces an innovative modeling of the sequence of time intervals between user interactions, rather than the numerical values of the intervals themselves, thereby capturing real-time feedback on user interests and integrating it with conventional PE mechanisms. Furthermore, we employ multiple layers of one-dimensional convolutional networks and attention mechanisms to endow the features with adaptive capabilities across various time interval scenarios. This enables TSAPE to more accurately capture sequential positional information at any given moment. By enhancing the sequential order information of interactions, TSAPE significantly improves the accuracy of next-item recommendations. We seamlessly integrated our method into several Transformer-based sequential recommendation models and conducted comparisons with state-of-the-art sequential recommendation approaches and widely-used PE methods. The results demonstrate that the integration of TSAPE consistently outperforms the original backbone models and other SOTA methods. The SASRec model integrated with TSAPE achieves an average improvement of 15.61% across three evaluation metrics on four benchmark datasets. Our code has been made publicly available at https://github.com/rongbo-qi/TSAPE_Rec.

Recommendation systems play a central role in modern services, yet often treat item cover images as static attributes, overlooking their influence on user decisions. We introduce the task of cover recommendation and study few-shot, interaction-free selection using multimodal user interest profiles. To address cold-start and sparsity challenges in traditional methods, we propose Multimodal Cover Recommendation (MCRec), a framework that leverages Vision-Language Models (VLMs) for multimodal feature extraction. Our approach includes: (1) a Text-Guided Visual Interest Aggregation network (TGVIA) integrating visual and textual representations; (2) multimodal interest embeddings fused via templated prompts; and (3) a multimodal-driven textual inversion technique enabling training-free generalization to new scenarios. We further propose MCRec+, a fine-tuning variant using hybrid sampling. To support evaluation, we construct three benchmarks and propose two new metrics. Extensive experiments show our methods significantly outperform baselines across datasets, especially with average gains of 3.72% in Recall@1, 1.70% in APMS and 1.25% in MPMS on MCRec. Code and data are publicly available from https://github.com/WeixinZhengRec/MCRec.

The recommendation system, as a widely used and effective tool to alleviate information overload, has been receiving increasing attention regarding its issues of bias and fairness. Many studies have focused on addressing fairness on the item side, targeting item fairness by minimizing exposure discrepancies of items among similar individuals. However, in real-world recommendation scenarios, many relevant items requiring similar exposure to users may exhibit certain dissimilarities while existing methods could not solve the problem. To address this, we define a broader item fairness recommendation issue aimed at improving fairness within specified groups of related individual items, which we term as “intra-group item fairness”. To solve this issue, we propose a Group-oriented Individual Fairness recommendation model called GIFRec. First, we introduce a global exposure balance module to mitigate exposure imbalances at a global level, with the help of multimodal information contained in each item. Then, at the group level, we propose a group fusion embedding representation method, allowing individual items within the same group to adaptively share group information. Additionally, as unfair training opportunities may arise for different items during model training, we propose a general fair intra-group optimization method to reduce individual training biases within the same group. Extensive experiments conducted on four real-world datasets demonstrate the effectiveness of our approach with an average improvement of 11.27% in accuracy and 24.91% in fair ness compared to eight SOTA methods. Our implementation and some details can be found at https://github.com/xderui/GIFRec.

Dynamic graphs are common in many applications to conveniently model heterogeneous data integrated from multiple sources. We study the monitoring of predictive events in dynamic graphs. Treating the problem as a continuous multi-label classification, we use deep metric learning to manage the embedding space and to create spherical codes where each codeword is an embedding vector representing a cluster of data state embeddings with the same results of the predictive events. By continuously training data embeddings from a dynamic graph neural network (DGNN) model and a code generator together, our method, called SCode, achieves significantly better accuracy than DGNN baselines. Moreover, SCode is also about twice as fast as the DGNN baselines, owing to its efficient matching between data state embedding and codewords for multiple events together. Finally, our training sample complexity analysis also sheds light on the generalizability of the online learning.

Personalized recommendations are integrated into daily life, but providers may want certain items to become more appealing over time through user interactions, yet this issue is often overlooked. The existing works are often based on the assumption that users will passively accept all intermediate sequences or not explore intention modeling in the targeted nudging process. Both of these factors result in suboptimal performance in the proactive recommendation. In this paper, we propose a novel intention-based targeted multi-round proactive recommendation method, dubbed ITMPRec. We first select target items using a pre-match strategy. Then, we employ a multi-round nudging recommendation method, incorporating a module to quantify users' intention-level evolution, helping choose suitable intermediate items. Additionally, we model users' sensitivity to changes caused by these items. Lastly, we propose an LLM agent as a pluggable component to simulate user feedback, offering an alternative to traditional click models by leveraging the agent's external knowledge and reasoning capabilities. Through extensive experiments on four public datasets, we demonstrate the superiority of ITMPRec compared to eight baseline models.

Heterogeneous graph streams represent data interactions in real-world applications and are characterized by dynamic and heterogeneous properties including varying node labels, edge labels and edge weights. The mining of graph streams is critical in fields such as network security , social network analysis , and traffic control. However, the sheer volume and high dynamics of graph streams pose significant challenges for efficient storage and accurate query analysis. To address these challenges, we propose LSketch, a novel sketch technique designed for heterogeneous graph streams. Unlike traditional methods, LSketch effectively preserves the diverse label information inherent in these streams, enhancing the expressive ability of sketches. Furthermore, as graph streams evolve over time, some edges may become outdated and lose their relevance. LSketch incorporates a sliding window model that eliminates expired edges, ensuring that the analysis remains focused on the most current and relevant data automatically. LSketch operates with sub-linear storage space and supports both structure-based and time-sensitive queries with high accuracy. We perform extensive experiments over four real datasets, demonstrating that LSketch outperforms state-of-the-art methods in terms of query accuracy and time efficiency.

Today, mainstream recommendation systems have achieved remarkable success in recommending items that align with user interests. However, limited attention has been paid to the perspective of item providers. Content providers often desire that all their offerings, including unpopular or cold items, aredisplayed and appreciated by users. To tackle the challenges ofunfair exhibition and limited item acceptance coverage, we introduce a novel recommendation perspective that enables items to “select” their most relevant users. We further introduce ItemRec, a straightforward plug-and-play approach that leverages mutual scores calculated by any model. The goal is to maximize the recommendation and acceptance of items by users. Through extensive experiments on three real-world datasets, we demonstrate that ItemRec can enhance valid coverage by up to 38.5% while maintaining comparable or superior recommendation quality. This improvement comes with only a minor increase in model inference time, ranging from 1.5% to 5%. Furthermore, when compared to thirteen state-of-the-art recommendation methods across accuracy, fairness, and diversity, ItemRec exhibits significant advantages as well. Specifically, ItemRec achieves an optimal balance between precision and valid coverage, showcasing an efficiency gain ranging from 1.8 to 45 times compared to other fairness-oriented methodologies.

We observe the need for continuous, online training of dynamic graph neural network (DGNN) models while at the same time using them to answer continuous predictive queries as data streams in. This implies significant training-time and memory costs. Along with the DGNN model learning, we simultaneously learn a weight/priority distribution over the nodes via a randomized online algorithm. In turn, the DGNN is continuously trained/learned by sampling nodes from the learned distribution and performing the chosen nodes' partitions of training work. We also devise a novel graph Kernel Density Estimation technique to smooth the distribution and improve the learning quality. Our experiments show that continuous online learning is much needed for graph streams and our approach significantly improves the standard DGNN models-to achieve the same accuracy, the training time ranges from several times to two orders of magnitude shorter, and the maximum memory consumption is several times to 20 times smaller.

Abstract Community search (CS) is a vital research area in network science that focuses on discovering personalized communities for query vertices from graphs. However, existing CS methods mainly concentrate on homogeneous or simple attributed graphs, often disregarding complex semantic information and rich contents carried by entities in heterogeneous graphs (HGs). In this paper, we propose a novel problem, namely the “Semantic Network Oriented Community Search with Meta-Structures in Heterogeneous Graphs (SNCS),” which aims to find dense communities that contain the query vertex, with vertices of the same type sharing similar topics. In response to this new problem, we present a novel approach, also named SNCS, representing the first solution employing meta-structures and topic constraints to tackle community search, leveraging both topological and latent features. To overcome the high-time complexity challenge posed by searching through meta-structures, we introduce a unique graph reconstruction technique. Our proposed method’s superiority is validated through extensive evaluations on real-world datasets. The results demonstrate a significant improvement in the quality of the obtained communities, with increases of 3.5–4.4% in clustering coefficient and 5–11% in density while requiring only 4–46% of the running time when compared with the state-of-the-art methods.

We study a novel problem of continuously predicting a number of user-subscribed continuous analytics targets (CATs) in dynamic networks. Our architecture includes any dynamic graph neural network model as the back end applied over the network data, and per CAT front end models that return results with their confidence to users. We devise a data filtering algorithm that feeds a provably optimal subset of data in the embedding space from back end model to front end models. Secondly, to ensure fairness in terms of query result accuracy for different CATs and users, we propose a fairness metric and a fairness-aware training scheduling algorithm, along with accuracy guarantees on fairness estimation. Our experiments over five real-world datasets show that our proposed solution is effective, efficient, fair, extensible, and adaptive.

Heterogeneous graph streams are very common in the applications today. Although representation learning has advantages in prediction accuracy, it is inherently deficient in the abilities to interpret or to reason well. It has long been realized as far back as in 1990 by Marvin Minsky that connectionist networks and symbolic rules should co-exist in a system and overcome the deficiencies of each other. The goal of this paper is to show that it is feasible to simultaneously and efficiently perform representation learning (for connectionist networks) and rule learning spontaneously out of the same online training process for graph streams. We devise such a system called RL$^2$, and show, both analytically and empirically, that it is highly efficient and responsive for graph streams, and produces good results for both representation learning and rule learning in terms of prediction accuracy and returning top-quality rules for interpretation and building dynamic Bayesian networks.

Complex networks have been used widely to model a large number of relationships. The outbreak of COVID-19 has had a huge impact on various complex networks in the real world, for example global trade networks, air transport networks, and even social networks, known as racial equality issues caused by the spread of the epidemic. Link prediction plays an important role in complex network analysis in that it can find missing links or predict the links which will arise in the future in the network by analyzing the existing network structures. Therefore, it is extremely important to study the link prediction problem on complex networks. There are a variety of techniques for link prediction based on the topology of the network and the properties of entities. In this work, a new taxonomy is proposed to divide the link prediction methods into five categories and a comprehensive overview of these methods is provided. The network embedding-based methods, especially graph neural network-based methods, which have attracted increasing attention in recent years, have been creatively investigated as well. Moreover, we analyze thirty-six datasets and divide them into seven types of networks according to their topological features shown in real networks and perform comprehensive experiments on these networks. We further analyze the results of experiments in detail, aiming to discover the most suitable approach for each kind of network.

One important problem that is insufficiently studied is finding densest lasting subgraphs in large dynamic graphs, which considers the time duration of the subgraph pattern. We propose a framework called Expectation-Maximization with Utility functions (EMU), a novel stochastic approach that nontrivially extends the conventional EM approach. EMU has the flexibility of optimizing any user-defined utility functions. We validate our EMU approach by showing that it converges to the optimum---by proving that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. We devise EMU algorithms for the densest lasting subgraph problem, as well as several variants by varying the utility function. Using real-world data, we evaluate the effectiveness and efficiency of our techniques, and compare them with two prior approaches on dense subgraph detection.

With the rapid development of the information age, many complex systems can be modeled as graphs. However, the unprecedented growth of data makes it extremely difficult for everyday users to process and mine very large graphs, given their limited computing resources such as personal computers and laptops. To address this challenge, we propose selective edge shedding. By estimating the original graph information from the reduced graph, it can accelerate graph algorithms and queries.In this paper, we propose two vertex-degree preserving edge shedding methods, the core of which are to maintain the expected vertex degree, so as to capture the basic characteristics of the network. Both methods allow users to control the size of the reduced graph based on the computing resource constraint. The experimental results show that the methods proposed in this paper can achieve up to 65% higher accuracy on graph analysis tasks compared to the competitive method, while consuming only 26%-57% running time, which fully demonstrates the advantages of the methods proposed in this work.

Complex event monitoring is an important problem in data streams that has drawn much attention. Most previous work assumes that the user knows and provides a complex event pattern for the system to continuously monitor. However, we observe that in many real applications, such as healthcare, security, and businesses, there are heterogeneous substreams and a diverse set of attributes. Often there is no simple uniform pattern prior to a critical event; nor is there clean simple language to describe the pattern leading to the critical event. People often only know it after the fact -- e.g., when something undesirable happens. We propose a novel approach based on relational machine learning and representation learning. We propose and learn probabilistic state machine patterns, which are used to monitor and predict the imminence of critical events. Our experiments demonstrate the efficiency and effectiveness of our approach, as well as its clear superiority over the closest previous approaches such as IL-Miner and LSTM based early prediction.

Querying and extracting potentially a large number of entities that are the user's intention is a challenging problem for knowledge graphs. The conventional query mechanism of subgraph pattern matching would not work well as the user in general does not know the graph pattern to search for. Moreover, there may not be a single subgraph pattern that fits all the intended entities. Using keywords also may not be a viable approach, as it is very difficult to come up with the right set of keywords, and the results are often very diverse and overwhelming. We propose a novel approach that does not require users to know much about the knowledge graph but only simple keywords about the desired entities. We retrieve a sample of matches and learn the entity context patterns as what we call the subgraph sketch signatures. We provide clustered patterns for the user to prune. Moreover, we devise a novel index to finally perform efficient entity retrieval over the whole knowledge graph.

Getting high quality XML schemas to avoid or reduce application risks is an important problem in practice, for which some important aspects have yet to be addressed satisfactorily in existing work. In this paper, we propose a tool FlashSchema for high quality XML schema design, which supports both one-pass and interactive schema design and schema recommendation. To the best of our knowledge, no other existing tools support interactive schema design and schema recommendation. One salient feature of our work is the design of algorithms to infer k-occurrence interleaving regular expressions, which are not only more powerful in model capacity, but also more efficient. Additionally, such algorithms form the basis of our interactive schema design. The other feature is that, starting from large-scale schema data that we have harvested from the Web, we devise a new solution for type inference, as well as propose schema recommendation for schema design. Finally, we conduct a series of experiments on two XML datasets, comparing with 9 state-of-the-art algorithms and open-source tools in terms of running time, preciseness, and conciseness. Experimental results show that our work achieves the highest level of preciseness and conciseness within only a few seconds. Experimental results and examples also demonstrate the effectiveness of our type inference and schema recommendation methods.

Knowledge graphs have seen increasingly broad applications. However, they are known to be incomplete. We define the notion of a virtual knowledge graph which extends a knowledge graph with predicted edges and their probabilities. We focus on two important types of queries: top-k entity queries and aggregate queries. To improve query processing efficiency, we propose an incremental index on top of low dimensional entity vectors transformed from network embedding vectors. We also devise query processing algorithms with the index. Moreover, we provide theoretical guarantees of accuracy, and conduct a systematic experimental evaluation. The experiments show that our approach is very efficient and effective. In particular, with the same or better accuracy guarantees, it is one to two orders of magnitude faster in query processing than the closest previous work which can only handle one relationship type.

We study a practical problem of predicting the upcoming events in data streams using a novel approach. Treating event time orders as relationship types between event entities, we build a dynamic knowledge graph and use it to predict future event timing. A unique aspect of this knowledge graph embedding approach for prediction is that we enhance conventional knowledge graphs with the notion of "states"---in what we call the ephemeral state nodes---to characterize the state of a data stream over time. We devise a complete set of methods for learning relevant events, for building the event-order graph stream from the original data stream, for embedding and prediction, and for theoretically bounding the complexity. We evaluate our approach with four real world stream datasets and find that our method results in high precision and recall values for event timing prediction, ranging between 0.7 and nearly 1, significantly outperforming baseline approaches. Moreover, due to our choice of efficient translation-based embedding, the overall throughput that the stream system can handle, including continuous graph building, training, and event predictions, is over one thousand to sixty thousand tuples per second even on a personal computer---which is especially important in resource constrained environments, including edge computing.

One important problem that is insufficiently studied is finding densest lasting-subgraphs in large dynamic graphs, which considers the time duration of the subgraph pattern. We propose a framework called Expectation-Maximization with Utility functions (EMU), a novel stochastic approach that nontrivially extends the conventional EM approach. EMU has the flexibility of optimizing any user-defined utility functions. We validate our EMU approach by showing that it converges to the optimum-by proving that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. We then devise EMU algorithms for the densest lasting subgraph problem. Using real-world graph data, we experimentally verify the effectiveness and efficiency of our techniques, and compare with two prior approaches on dense subgraph detection.

Dynamic networks are very common in urban systems today. As data are acquired, unfortunately, they are rarely complete observations of the whole system. It is important to reliably infer the unobserved attribute values anywhere in the graphs, at certain times---either in the past or in the future. Previous work does not sufficiently capture the correlations inherent with graph topology and with time. We propose a machine learning approach using a novel probabilistic graphical model. We devise a series of algorithms to efficiently group the vertices, to learn the model parameters, and to infer the unobserved values for query processing. Furthermore, we propose a method to incrementally and automatically update the model. Finally, we perform an extensive experimental study using two real-world dynamic graph datasets to evaluate our approach.

In large and medium-sized cities, detecting unusual changes of crowds of people on the streets is needed for public security, transportation management, emergency control, and terrorism prevention. As public transportation has the capability to bring a large number of people to an area in a short amount of time, real-time discovery of anomalies in passenger numbers is an effective way to detect crowd anomalies. In this paper, we devise an approach called Kochab. Kochab adopts a generative model and combines the prior knowledge about passenger flows. Hence, it can detect anomalies in the numbers of incoming and outgoing passengers within a certain time and spatial area, including anomalous events along with their durations and severities. Through well-designed inference algorithms, Kochab requires only a moderate amount of historical data to be sample data. As such, Kochab shows good performance in real time and makes prompt responses to user' s interactive analysis requests. In particular, based on the recognized anomalous events, we capture event patterns which give us hints to link to activities or status in cities. In addition, for the convenience of method evaluation and comparison, we create an open Stream Anomaly Benchmark on the basis of large-scale real-world data. This benchmark will prove useful for other researchers too. Using this benchmark, we compare Kochab with four other methods. The experimental results show that Kochab is sensitive to population flow anomalies and has superior accuracy in detecting anomalies in terms of precision, recall and the F1 score.

Recent studies show that table scans are increasingly more common than using secondary indices. Given that the optimizer may choose table scans when the selectivity is as low as 0.5% with large data, it is important to make initial query results faster for interactive data explorations. We formulate it as a query result timeliness problem, and propose two complementary approaches. The first approach builds lightweight statistics and judiciously determines an access order to data blocks for a given query. The second approach performs adaptive microscopic tuple reordering online without relying on pre-built statistics. Our systematic experimental evaluation further verifies the efficiency and efficacy of our approaches.

Nowadays, a graph serves as a fundamental data structure for many applications. As graph edges stream in, users are often only interested in the recent data. In data exploration, how to store and process such massive amounts of graph stream data becomes a significant problem. As vertex and edge attributes are often referred to as labels, we propose a labeled graph sketch that stores real-time graph structural information in sublinear space and supports queries of diverse types. This sketch also supports sliding window queries. We conduct experiments on three real-world datasets, comparing with a state-of-the-art method to show the superiority of our sketch.

Detecting regularities between complex events in temporal graphs is critical for emerging applications. This paper proposes graph temporal association rules (GTAR). A GTAR extends traditional association rules to discover temporal associations for complex events captured by a class of temporal pattern queries. We introduce notions of support and confidence for GTARS and formalize the discovery problem for GTARS. We show that despite the enhanced expressive power, GTARS discovery is feasible over large temporal graphs. We develop an effective rule discovery algorithm, which integrates event mining and rule discovery as a single process, and reduces the redundant computation by leveraging their interaction. Using real-life and synthetic data, we experimentally verify the effectiveness and scalability of the algorithms. Our case study also verifies that GTARS demonstrate highly interpretable associations in real-world networks.

This demo presents BEAMS, a system that automatically discovers and monitors top-k complex events over graph streams. Unlike conventional event detection over streams of items, BEAMS is able to (1) characterize and detect complex events in dynamic networks as graph patterns, and (2) perform online event discovery with a class of bounded algorithms that compute changes to top-k events in response to the transactions in graph streams, and incurs a minimized time cost determined by the changes, independent of the size of graph streams. We demonstrate: a) how BEAMS identifies top-k complex events as graph patterns in graph streams, and supports ad-hoc event queries online, b) how it copes with the sheer size of real-world graph streams with bounded event detection algorithm, and c) how the GUI of BEAMS interacts with users to support adhoc event queries that detect, browse and inspect trending events. Video: https://youtu.be/lVUGM0Fa17Q.

Many big data applications today require querying highly dynamic and large-scale data streams for top-k frequent items in the most recent window of any specified size at any time. This is a challenging problem. We show that our novel solution is not only accurate, but it also one to two orders of magnitude faster than previous approaches. Moreover, its memory footprint grows only logarithmically with the window size, rather than linearly as in previous work. Our comprehensive experiments over real-world datasets show that our solution is very effective and scalable. In addition, we devise a concise and efficient solution to a related problem of tracking the frequency of selected items, improving upon previous work by twenty to thirty times in model conciseness while providing the same accuracy and efficiency.

The newly emerging location-based social networks (LBSN) such as Tinder and Momo extends social interaction from friends to strangers, providing novel experiences of making new friends. Familiar strangers refer to the strangers who meet frequently in daily life and may share common interests; thus they may be good candidates for friend recommendation. In this paper, we study the problem of discovering familiar strangers, specifically, public transportation trip companions, and their common interests. We collect 5.7 million transaction records of smart cards from about 3.02 million people in the city of Beijing, China. We first analyze this dataset and reveal the temporal and spatial characteristics of passenger encounter behaviors. Then we propose a stability metric to measure hidden friend relations. This metric facilitates us to employ community detection techniques to capture the communities of trip companions. Further, we infer common interests of each community using a topic model, i.e., LDA4HFC (Latent Dirichlet Allocation for Hidden Friend Communities) model. Such topics for communities help to understand how hidden friend clusters are formed. We evaluate our method using large-scale and real-world datasets, consisting of two-week smart card records and 901,855 Point of Interests (POIs) in Beijing. The results show that our method outperforms three baseline methods with higher recommendation accuracy. Moreover, our case study demonstrates that the discovered topics interpret the communities very well.

In this paper, we study the problem of learning a regular model from a number of sequences, each of which contains events in a time unit. Assuming some regularity in such sequences, we determine what events should be deemed irregular in their contexts. We perform an in-depth analysis of the model we build, and propose two optimization techniques, one of which is also of independent interest in solving a new problem named the Group Counting problem. Our comprehensive experiments on real and hybrid datasets show that the model we build is very effective in characterizing regularities and identifying irregular events. One of our optimizations improves model building speed by more than an order of magnitude, and the other significantly saves space consumption.

Data and actions are tightly coupled. On one hand, data analysis results trigger decision making and actions. On the other hand, the action of acquiring data is the very first step in the whole data processing pipeline. Data acquisition almost always has some costs, which could be either monetary costs or computing resource costs such as sensor battery power, network transfers, or I/O costs. Using out-dated data to answer queries can avoid the data acquisition costs, but there is a penalty of potentially inaccurate results. Given a sequence of incoming queries over time, we study the problem of sequential decision making on when to acquire data and when to use existing versions to answer each query. We propose two approaches to solve this problem using reinforcement learning and tailored locality-sensitive hashing. A systematic empirical study using two real-world datasets shows that our approaches are effective and efficient.

Complex event processing (CEP) has proven to be a highly relevant topic in practice. As it is sensitive to both errors in the stream and uncertainty in the pattern, approximate complex event processing (ACEP) is an important direction but has not been adequately studied before. ACEP is costly, and is often performed under insufficient computing resources. We propose an algorithm that learns from the past behavior of ACEP runs, and makes decisions on what to process first in an online manner, so as to maximize the number of full matches found. In addition, we devise effective optimization techniques. Finally, we propose a mechanism that uses reinforcement learning to dynamically update the history structure without incurring much overhead. Put together, these techniques drastically improve the fraction of full matches found in resource constrained environments.

Most of the recent complex event semantics is based on regular expressions, extended with additional filters such as window constraints. We observe that many applications today require parallel (interleaving) event patterns. Moreover, we observe that this matching needs to be approximate in terms of event orders and missing events. We first propose the query semantics. Then we devise a foundation algorithm, on top of which two optimization techniques are proposed. Finally, we perform a comprehensive experimental evaluation using three real-world datasets in different domains and synthetic datasets.

Sequence data is prevalent, and event processing over sequences is increasingly important in this Big Data era, drawing much attention from both research and industry. In this paper, we address a novel problem, which is to find common event subsequences from two long sequences. This problem is well motivated, with applications in diverse domains. We propose the window-chained longest common subsequence (WCLCS) semantics, and argue that the traditional longest common subsequence (LCS) cannot serve this need. We then devise efficient algorithms to solve this problem by reducing it to a graph problem. We also propose two more methods to improve the performance: one is based on informed search and exploration, and the other is an approximation algorithm with accuracy guarantees. We finally carry out a systematic experimental evaluation using two real-world datasets and some synthetic datasets.

We propose a new local data perturbation method called Aroma. We first show that Aroma is sound in its privacy protection. For that, we devise a realistic privacy game, called the exposure test. We prove that the αβ algorithm, a previously proposed method that is most closely related to Aroma, performs poorly under the exposure test and fails to provide sufficient privacy in practice. Moreover, any data protection method that satisfies ε-differential privacy will succeed in the test. By proving that Aroma satisfies ε-differential privacy, we show that Aroma offers strong privacy protection. We then demonstrate the utility of Aroma by proving that its estimator has significantly smaller errors than the previous state-of-the-art algorithms such as αβ, AM, and FRAPP. We carry out a systematic empirical study using real-world data to evaluate Aroma, which shows its clear advantages over previous methods.

A graph is a fundamental and general data structure underlying all data applications. Many applications today call for the management and query capabilities directly on graphs. Real time graph streams, as seen in road networks, social and communication networks, and web requests, are such applications. Event pattern matching requires the awareness of graph structures, which is different from traditional complex event processing. It also requires a focus on the dynamicity of the graph, time order constraints in patterns, and online query processing, which deviates significantly from previous work on subgraph matching as well. We study the semantics and efficient online algorithms for this important and intriguing problem, and evaluate our approaches with extensive experiments over real world datasets in four different domains.

Although association rule mining has been studied in the literature for quite a while and numerical attributes are prevalent, perhaps surprisingly, the state-of-the-art quantitative association rule mining is rather inefficient and ineffective in discovering all useful rules. In this paper, we propose a novel divide and conquer two-phase algorithm, which is guaranteed to find all good rules efficiently. We further devise an optimization technique for performance. Moreover, we discuss a few issues with managing and using the discovered quantitative association rules. We perform a comprehensive experimental study which shows that our algorithm is one to two orders of magnitude faster than the state-of-the-art one. In addition, we discover significantly more rules that are useful for prediction.

Answering real-time queries, especially over probabilistic data, is becoming increasingly important for service providers. We study anytime query processing algorithms, and extend the traditional query execution plan with a timing component. Our focus is how to determine this timing component, given the queries' deadline constraints. We consider the common multicore processors. Specifically, we propose two query optimization modes: offline periodic optimization and online optimization. We devise efficient algorithms for both offline and online cases followed by a competitive analysis to show the power of our online optimization. Finally, we perform a systematic experimental evaluation using real-world datasets to verify our approaches.

Managing noisy and uncertain data is needed in a great number of modern applications. A major difficulty in managing such data is the sheer number of query result tuples with diverse probabilities. In many cases, users have a preference over the tuples in a deterministic world, determined by a scoring function. Yet it has been a challenging problem to return top-k for uncertain data. Various semantics have been proposed, and they have been shown to give wildly different tuple rankings. In this paper, we propose a completely different approach. Instead of returning users fc tuples, which are merely one point in the complex distribution of top-k tuple vectors, we provide a so-called top-k oracle and users can arbitrarily query it. Intuitively, an oracle is a black box that, whenever given an SQL query, returns its result. Any information we give is based on faithful, best-effort estimates of the ground-truth top-k tuples. This is especially critical in emergency response applications and in monitoring top-k applications. Furthermore, we are the first to provide the nested query capability with the uncertain top-k result being a subquery. We devise various query processing algorithms for top-k oracles, and verify their efficiency and accuracy through a systematic evaluation over real-world and synthetic datasets.

Regular expression matching over sequences in real time is a crucial task in complex event processing on data streams. Given that such data sequences are often noisy and errors have temporal and spatial correlations, performing regular expression matching effectively and efficiently is a challenging task. Instead of the traditional approach of learning a distribution of the stream first and then processing queries, we propose a new approach that efficiently does the matching based on an error model. In particular, our algorithms are based on the realistic Markov chain error model, and report all matching paths to trace relevant basic events that trigger the matching. This is much more informative than a single matching path. We also devise algorithms to efficiently return only top-k matching paths, and to handle negations in an extended regular expression. Finally, we conduct a comprehensive experimental study to evaluate our algorithms using real datasets.

Previous work has introduced probability distributions as first-class components in uncertain stream database systems. A lacking element is the fact of how accurate these probability distributions are. This indeed has a profound impact on the accuracy of query results presented to end users. While there is some previous work that studies unreliable intermediate query results in the tuple uncertainty model, to the best of our knowledge, we are the first to consider an uncertain stream database in which accuracy is taken into consideration all the way from the learned distributions based on raw data samples to the query results. We perform an initial study of various components in an accuracy-aware uncertain stream database system, including the representation of accuracy information and how to obtain query results' accuracy. In addition, we propose novel predicates based on hypothesis testing for decision-making using data with limited accuracy. We augment our study with a comprehensive set of experimental evaluations.

Windowed subsequence matching over deterministic strings has been studied in previous work in the contexts of knowledge discovery, data mining, and molecular biology. However, we observe that in these applications, as well as in data stream monitoring, complex event processing, and time series data processing in which streams can be mapped to strings, the strings are often noisy and probabilistic. We study this problem in the online setting where efficiency is paramount. We first formulate the query semantics, and propose an exact algorithm. Then we propose a randomized approximation algorithm that is faster and, in the mean time, provably accurate. Moreover, we devise a filtering algorithm to further enhance the efficiency with an optimization technique that is adaptive to sequence stream contents. Finally, we propose algorithms for patterns with negations. In order to verify the algorithms, we conduct a systematic empirical study using three real datasets and some synthetic datasets.

Uncertain data is quite common nowadays in a variety of modern database applications. At the same time, the join operation is one of the most important but expensive operations in SQL. However, join queries on uncertain data have not been adequately addressed thus far. In this paper, we study the SQL join operation on uncertain attributes. We observe and formalize two kinds of join operations on such data, namely v-join and d-join. They are each useful for different applications. Using probability theory, we then devise efficient query processing algorithms for these join operations. Specifically, we use probability bounds that are based on the moments of random variables to either early accept or early reject a candidate v-join result tuple. We also devise an indexing mechanism and an algorithm called Two-End Zigzag Join to further save I/O costs. For d-join, we first observe that it can be reduced to a special form of similarity join in a multidimensional space. We then design an efficient algorithm called condensed d-join and an optimal condensation scheme based on dynamic programming. Finally, we perform a comprehensive empirical study using both real datasets and synthetic datasets.

Array database systems are architected for scientific and engineering applications. In these applications, the value of a cell is often imprecise and uncertain. There are at least two reasons that a Monte Carlo query processing algorithm is usually required for such uncertain data. Firstly, a probabilistic graphical model must often be used to model correlation, which requires a Monte Carlo inference algorithm for the operations in our database. Secondly, mathematical operators required by science and engineering domains are much more complex than those of SQL. State-of-the-art query processing uses Monte Carlo approximation. We give an example of using Markov Random Fields combined with an array's chunking or tiling mechanism to model correlated data. We then propose solutions for two of the most challenging problems in this framework, namely the expensive array join operation, and the determination and optimization of stopping conditions of Monte Carlo query processing. Finally, we perform an extensive empirical study on a real world application.

Multidimensional array database systems are suited for scientific and engineering applications. Data in these applications is often uncertain and imprecise due to errors in the instruments and observations, etc. There are often correlations exhibited in the distribution of values among the cells of an array. Typically, the correlation is stronger for cells that are close to each other and weaker for cells that are far away. We devise a novel data structure, called the A*-tree (multi dimensional Array tree ), demonstrating that by taking advantage of the predictable and structured correlations of multidimensional data, we can have a more efficient way of modeling and answering queries on large-scale array data. An A*-tree is a unified model for storage and inference. The graphical model that is assumed in an A*-tree is essentially a Bayesian Network. We analyze and experimentally verify the accuracy of an A*-tree encoding of the underlying joint distribution. We also study the efficiency of query processing over A*-trees, comparing it to an alternative graphical model.

Modern database systems increasingly make use of networked storage. This storage can be in the form of SAN's or in the form of shared-nothing nodes in a cluster. One type of attack on databases is arbitrary modification of data in a database through the file system, bypassing database access control. Additionally, for many applications, ensuring strict and definite authenticity of query source and results is required or highly desirable. In this paper, we propose a lightweight approach for verifying the minimum information that a database server needs from the storage system to execute a query. The verification is definite and produces high confidence results because of its online manner (i.e., the information is verified right before it is used). It is lightweight in three ways: (1) We use the Merkle hash tree data structure and fast cryptographic hash functions to ensure the verification itself is fast and secure; (2) We verify the minimum number of bytes needed to ensure the authenticity of the source related to the query result; and (3) We achieve high concurrency of multiple reader and writer transactions and avoid delays due to locking by using the compare-and-swap primitive. We then prove the correctness and progress guarantees of the algorithms using concepts from the theory of distributed computing. We also analyze the performance of the algorithm. Finally, we perform a comprehensive empirical study on various parameter choices and on the system performance and concurrency with our approaches.

Uncertain data arises in a number of domains, including data integration and sensor networks. Top-k queries that rank results according to some user-defined score are an important tool for exploring large uncertain data sets. As several recent papers have observed, the semantics of top-k queries on uncertain data can be ambiguous due to tradeoffs between reporting high-scoring tuples and tuples with a high probability of being in the resulting data set. In this paper, we demonstrate the need to present the score distribution of top-k vectors to allow the user to choose between results along this score-probability dimensions. One option would be to display the complete distribution of all potential top-k tuple vectors, but this set is too large to compute. Instead, we propose to provide a number of typical vectors that effectively sample this distribution. We propose efficient algorithms to compute these vectors. We also extend the semantics and algorithms to the scenario of score ties, which is not dealt with in the previous work in the area. Our work includes a systematic empirical study on both real dataset and synthetic datasets.

Scientific and intelligence applications have special data handling needs. In these settings, data does not fit the standard model of short coded records that had dominated the data management area for three decades. Array database systems have a specialized architecture to address this problem. Since the data is typically an approximation of reality, it is important to be able to handle imprecision and uncertainty in an efficient and provably accurate way. We propose a discrete approach for value distributions and adopt a standard metric (i.e., variation distance) in probability theory to measure the quality of a result distribution. We then propose a novel algorithm that has a provable upper bound on the variation distance between its result distribution and the "ideal" one. Complementary to that, we advocate the usage of a "statistical mode" suitable for the results of many queries and applications, which is also much more efficient for execution. We show how the statistical mode also presents interesting predicate evaluation strategies. In addition, extensive experiments are performed on real world datasets to evaluate our algorithms.

Time series data is common in many settings including scientific and financial applications. In these applications, the amount of data is often very large. We seek to support prediction queries over time series data. Prediction relies on model building which can be too expensive to be practical if it is based on a large number of data points. We propose to use statistical tests of hypotheses to choose a proper subset of data points to use for a given prediction query interval. This involves two steps: choosing a proper history length and choosing the number of data points to use within this history. Further, we use an I/O conscious skip list data structure to provide samples of the original data set. Based on the statistics collected for a query workload, which we model as a probability mass function (PMF) over query intervals, we devise a randomized algorithm that selects a set of pre-built models (PM's) to construct, subject to some maintenance cost constraint when there are updates. Given this set of PM's, we discuss interesting query processing strategies for not only point queries, but also range, aggregation, and JOIN queries. We conduct a comprehensive empirical study on real world datasets to verify the effectiveness of our approaches and algorithms.

Networked information systems require strong security guarantees because of the new threats that they face. Various forms of encryption have been proposed to deal with this problem. In a database system, there are often two contradictory goals: security of the encryption and fast performance of queries. There have been a number of proposals of database encryption schemes to facilitate queries on encrypted columns. Order-preserving encryption techniques are well-suited for databases since they support a simple, and efficient way to build indices. However, as we will show, they are insecure under straightforward attack scenarios. We propose a new light-weight database encryption scheme (called FCE) for column stores in data warehouses with trusted servers. The low decryption overhead of FCE makes comparisons of ciphertexts and hence indexing operations very fast. Since it is hard to use classical security definitions in cryptography to prove the security of any existing symmetric encryption scheme, we propose a relaxed measure of security, called INFO-CPA-DB. INFO-CPA-DB is based on a well-established security definition in cryptography and relaxes it using information theoretic concepts. Using INFO-CPA-DB, we give strong evidence that FCE is as secure as any underlying block cipher (yet more efficient than using the block cipher itself). Using the same security measure we also show the inherent insecurity of any order preserving encryption scheme under straightforward attack scenarios. We discuss indexing techniques based on FCE as well.