The corpus of knowledge that we have amassed is often fragmented in nature. That is, we only possess a mere fraction of understanding regarding various objects and lack a holistic view of the interconnections between them. Graph, a widely used model to represent data and relationships between data, encompasses significant amounts of fragmented knowledge. In this paper, we study fragmented graph pattern matching ($\mathsf {FPM}$for short) on large graphs, a typical problem of fragmented knowledge management. Given several query graphs,$\mathsf {FPM}$searches for matches whose subgraphs are isomorphic to the given query graphs and these subgraphs are connected in a specified way.$\mathsf {FPM}$plays a crucial role in detecting financial crime, identifying abnormal behavior and mining latent knowledge. We propose an algorithm$\mathsf {FraMatch}$, which adopts a traversal-based manner to adaptively identify matches for the given query graphs and enumerates the interconnections among these matches. To improve the efficiency of$\mathsf {FraMatch}$, an index, represented as a$k$-partite graph, is constructed to help organize the candidate matches. Additionally, several methods, including four filtering strategies, parallel optimization and a dynamic loading strategy, are proposed to further accelerate the algorithm and reduce memory usage. We conducted extensive experiments on 4 real graphs to validate$\mathsf {FraMatch}$. The results demonstrate that$\mathsf {FraMatch}$outperforms its comparisons 2000× in running time and reduces memory usage by 8% on average. A real application on anti-money laundering further verifies the effectiveness of$\mathsf {FPM}$. To the best of our knowledge, this is the first study on$\mathsf {FPM}$on large graphs.

How should we perform anomaly detection on multivariate time-series data with missing data, attribute misplacement and concept drift? The majority of existing anomaly detection methods overlook the fact that data are often of low quality. To address this challenge, we propose an adaptive unsupervised anomaly detection method for low-quality multivariate time series data. Our method introduces a self-attention mechanism that integrates masked information and missing length information to enhance the model's capability in handling incomplete data. Furthermore, we design a deep probabilistic adaptive memory network to improve the model's adaptability to attribute misplacement and concept drift. We also discuss the optimal window size for effectively dealing with concept drift. Comparative experiments on multiple real-world datasets demonstrate that our method can effectively detect anomalies in low-quality multivariate time series data. The experimental results further highlight the robustness of our model, proving its ability to maintain high performance in the presence of data quality issues.

Motif discovery is a critical operation for analyzing series data in many applications. Recent works demonstrate the importance of finding motifs with Dynamic Time Warping. However, existing algorithms spend most of their time in computing lower bounds of Dynamic Time Warping to filter out the unpromising candidates. Specifically, the time complexity for computing these lower bounds is$O(L)$for each pair of subsequences, where$L$is the length of the motif (subsequences). This paper proposes two new lower bounds, called$LB_{f}$and$LB_{M}$, both of them only cost amortized$O(1)$time for each pair of subsequences. On real datasets, the proposed lower bounds are at least one magnitude faster than the state-of-the-art lower bounds used in motif discovery while still keeping satisfying effectiveness. Based on these faster lower bounds, this paper designs an efficient motif discovery algorithm that significantly reduces the cost of lower bounds. The experiments conducted on real datasets show the proposed algorithm is 5.6 times faster than the state-of-the-art algorithms on average.

Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. This query returns an optimal site from a candidate set to maximize itsinfluence. Existing work commonly focuses on outdoor spaces. In practice, however, people spend up to 87% of their daily life inside indoor spaces. The outdoor techniques fall short in indoor spaces due to the complicated topology of indoor spaces. In this paper, we formulate two indoor Max-Inf queries:Top-$k$kProbabilistic Influence Query (T$k$kPI)andCollective-$k$kProbabilistic Influence Query (C$k$kPI)taking probability and mobility factors into consideration. We propose a novel spatial index, IT-tree, which utilizes the properties of indoor venues to facilitate the indoor distance computation, and then applies a trie to further organize the trajectories with similar check-in partitions together, based on their sketch information. This structure is simple but highly effective in pruning the trajectory search space. To process T$k$PI efficiently, we devise subtree pruning and progressive pruning techniques to delicately filter out unnecessary trajectories based on probability bounds and the monotonicity of influence probability. For C$k$PI queries, which is a submodular NP-hard problem, three approximation algorithms are provided with different strategies of computing marginal influence value during the search. Through extensive experiments on several real indoor venues, we demonstrate the efficiency and effectiveness of our proposed algorithms.

Existing literature on k-Maximum Inner-Product Search has made it a common belief that tree based methods are less effective in terms of index construction time and query performance compared to locality sensitive hashing based, similarity graph based and quantization based methods. However, in this paper we partially roll over the existing assessments about tree based k- Maximum Inner-Product Search methods by our newly proposed tree structure named LRUS-CoverTree. The experimental results show that the new k- Maximum Inner-Product Search algorithm based on LRUS-CoverTree outperforms the state-of-the-art locality sensitive hashing based methods, and achieves comparable performance with similarity graph based and quantization based methods in terms of query time and accuracy. What's more important, the desirable query performance is attained with significantly lower index construction time compared to all the other methods. Besides the experimental evaluations, substantial theoretical results about the LRUS-CoverTree and the new k-Maximum Inner-Product Search algorithm are provided, including construction time and search time complexity, size and height of the tree, and so on. Furthermore, several new effective upper bounds on the inner-product value are provided to support the efficient branch-and-bound algorithm on LRUS-CoverTree. In summary, our novel tree structure and new algorithm significantly improve upon existing tree based methods, and it is hoped that this contribution can lead to a reconsideration of tree based k-Maximum Inner-Product Search methods.

Functional dependencies (FDs) are the most common constraints in the design theory for relational databases, generalizing the concept of a key for a relation. Given an attribute subset$X$and an attribute$A$in relation schema, a functional dependency (FD)$X\rightarrow A$means that the value of$A$is uniquely determined by the values of$X$. An FD$X\rightarrow A$is minimal if$A$is not determined by any proper subset of$X$, and is nontrivial if$A$is not contained in$X$The FD discovery problem is to determine all minimal nontrivial functional dependencies over a given relation instance.

In a wide variety of applications, such as indoor position selection for advertising and setting rents of different shops in a shopping mall, it is better to get the passenger flow of each room. In the indoor space, the positions of users are commonly captured by the indoor positioning system consisting of static positioning devices. And the sequence of all tracking events with the same user ordered by the corresponding time is the indoor trajectory of this user. Thus, in this paper, we define and study two essential queries named Rooms with top- k passenger flows at a Timestamp query (R k T for short) and Rooms with top- k passenger flows within a time Interval query (R k I for short), i.e., how to search rooms with top- k passenger flows at a timestamp and within a time interval in the past using indoor trajectories, respectively. For the indoor positioning system, there are only limited static positioning devices deployed in the indoor space on account of the cost. And the detection ranges of these static positioning devices only cover a small part of the indoor space. When a user is in the undetected state, there is uncertainty in its position combined with the quite complex indoor topology. Such uncertainty brings great challenges to determining the passenger flow in each room. Considering the distribution of static positioning devices, we propose a new method about how to reasonably infer where a user is in the undetected state and the corresponding probability based on its indoor trajectory and the complex indoor topology. In order to quickly retrieve the set of indoor trajectories, we propose a full Binary tree indexing indoor trajectories divided by Time intervals (BiT for short), which is built on the given set of indoor trajectories. Based on the index BiT, we propose PAT Algorithm and PAI Algorithm to efficiently process R k T and R k I queries, respectively. Extensive experiment results demonstrate superior performance of PAT Algorithm and PAI Algorithm.

Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. Given a set of weighted objects, this query aims to find an optimal location from a candidate set to maximize itsinfluence, which is the total weight of its reverse nearest neighbors. Existing work commonly assumes that every object is in a fixed location. In real life, however, there are a wide variety of drive-in services (e.g., food joints, pharmacies, ATMs, etc.) that are widely accessed by mobile users (i.e., trajectories) instead of the fixed ones. In this paper, we first define the Maximizing Influence query over Trajectories, namely, MIT query, which aims to find an optimal location to maximize the total weight of influenced trajectories. We propose a novel index, QB-tree to hierarchically group trajectories with similar activity regions together for subsequent unified processing, and classify trajectories inside the same node into multiple buckets according to their motion patterns. For each bucket, we construct a rectilinear polygon using the trajectories in it to exclude some irrelevant areas in the minimum boundary rectangle. Moreover, we develop a branch-and-bound approach called BBM to efficiently solve the MIT query. The algorithm adaptively partitions the candidates into disjoint regions and prunes the regions without containing optimal results. Then, by exploiting the QB-tree, the upper and lower bounds are efficiently computed with three-level pruning technique. Practically, we also study a variant of the MIT query, called MDT query. We propose novel pruning bounds in cooperation with QB-tree to answer MDT queries efficiently. Finally, extensive experiments on real and synthetic datasets demonstrate that our index and algorithms have high performance in terms of efficiency, scalability, and genericity.

Range query is an important operation on big multi-dimensional data. This paper studies the problem of multi-dimensional range query filtering for speeding up the range query processing by avoiding reading the useless data. To solve the problem, a novel multi-dimensional range filter is proposed to filter the multi-dimensional range queries, while the existing one-dimensional range filters can not provide efficient filtering. Based on the multi-dimensional range filter, an efficient range query processing algorithm is presented. It can directly return the locations of the I/O units that contain the data in the query result without any access to the input dataset. The time complexity of the algorithm is$O(3^{m}h)$, where$h$is the number of I/O units partially overlapping with a range query, and$m$is the dimension number. Since$m$is usually$o(\sqrt{\log n})$, it is a sublinear time algorithm if$V=O(n)$, where$n$is the size of the input dataset,$V=\prod _{i=1}^{m}d_{i}$, and$d_{i}$is the number of distinct values on the$i$-th dimension of the dataset for$1\leq i\leq m$. Experimental results show that the multi-dimensional range filter has low false positive rate and good filtering efficiency. The proposed range query processing algorithm achieves at least 3$\sim$7 times improvement compared to the one-dimensional filter based algorithms on different datasets.

Functional dependencies are the most common constraints in the design theory for relational databases, which have very important practical applications in many areas. Different kinds of algorithms are proposed to discover the functional dependencies. However, it is found in this paper that the existing algorithms cannot deal well with massive data which cannot be held entirely in memory due to high memory consumption and high computation cost. In this paper, a novel algorithm FSC is presented to compute functional dependencies on massive data. The two-step execution of FSC relies on a pre-computed update-friendly assistant structure of comparable pairs which reflect the identifier pairs for tuples with at least one equal attribute. In step 1, FSC determines the violated functional dependencies and introduces the selective comparison by comparable pairs to reduce the required pairwise comparison significantly. The direct value-combination compression strategy is devised to process attributes of small cardinality. In step 2, FSC induces the required functional dependencies by the results in step 1. The extensive experimental results, conducted on synthetic and real-life data sets, show that FSC can discover functional dependencies on massive data efficiently.

Multi-criteria decision-making usually requires finding a small representative set from the database. A popular method, the regret minimization set (RMS) query, returns a size$r$subset$S$of the full dataset$D$that minimizes the regret-ratio (the difference between the scores of top-1 in$S$and top-1 in$D$, for any utility function). RMS is not shift invariant, causing inconsistency in results. Further, the regret-ratio is often a “made up” number and users may mistake its absolute value. Instead, users do understand the notion of rank. Therefore, in this paper, we consider finding a fixed-size set$S$to minimize the maximum rank-regret (the rank of top-1 of$S$in the sorted list of$D$) over all possible utility functions, called the rank-regret minimization (RRM) problem, which is shift invariant. In 2D space, we design an exact algorithm 2DRRM for RRM. In HD space, we propose an approximate algorithm HDRRM with theoretical guarantees on rank-regret. It combines the ideas of space discretization and clustering. Extensive experiments verify the efficiency and effectiveness of our algorithms. In particular, HDRRM always has the best output quality in experiments.

Maximizing Influence (Max-Inf) query is a fundamental operation in spatial data management. Given a set of weighted objects, this query aims to find an optimal location from a candidate set to maximize its influence, which is the total weight of its reverse nearest neighbors. Existing work commonly assumes that every object is in a fixed location. In real life, however, there are a wide variety of drive-in services (e.g., food joints, fuel stations, ATMs, etc.) that are widely accessed by mobile users (i.e., trajectories) instead of the fixed ones. It is urgent and challenging to solve the Max-Inf query in trajectory data (MIT). In this paper, we first define the MIT query which aims to find the optimal location to maximize the total weight of influenced trajectories. We propose a novel index structure, QB-tree to hierarchically group trajectories with similar activity regions together for subsequent unified processing, and classify trajectories inside the same node into multiple buckets according to their motion patterns. For each bucket, we construct a rectilinear polygon using the trajectories in it to exclude some irrelevant areas in the minimum boundary rectangle. Moreover, we develop a branch-and-bound approach called BBM to efficiently solve the MIT query. The algorithm adaptively partitions the candidates into disjoint regions and prunes the regions without containing optimal results. Then, by exploiting the QB-tree, the upper and lower bounds are efficiently computed with three-level pruning technique. Finally, we conduct extensive experiments on real and synthetic datasets to evaluate our index and algorithms, and the experimental results demonstrate that our algorithm has high performance in terms of efficiency, scalability, and genericity.

A top-k query retrieves the k tuples with highest scores according to a user preference, defined as a scoring function. It is difficult for a user to precisely specify the scoring function. Instead, obtaining the distribution on scoring functions, i.e., the preference distribution, has been extensively explored in many fields. Motivated by this, we introduce the uniform (r,k)-hit (UrkHit) problem. Given a preference distribution, UrkHit aims to select a representative set of r tuples to maximize the probability of containing a tuple attractive to the user. We say a tuple attracts a user, if it is a top-k tuple for the scoring function adopted by the user. Further, we generalize UrkHit and propose the (r,k)-hit (rkHit) problem with an additional penalty function to model the user satisfaction with the tuple ranked i-th. rkHit aims to maximize the expected user satisfaction with the representative set. In 2D space, we design an exact algorithm 2DH for rkHit, indicating rkHit is in P for d=2. We show that rkHit is NP-hard when d\ge3. In 3D space, assuming a uniform preference distribution, we propose a (1-1/e)-approximation algorithm 3DH based on space partitioning. In addition, we propose an approximate algorithm MDH suitable for any dimension and distribution, which creatively combines the ideas of sampling and clustering. It relaxes the approximation guarantee slightly. Comprehensive experiments demonstrate the efficiency and effectiveness of our algorithms.

This paper presents a new approach for semi-external topological sorting algorithm on big directed acyclic graph(DAG). Topological sorting aims to find an ordering of each node in DAG, which satisfies$u$precedes$v$in the ordering for each edge$(u,v)$in DAG. Topological sorting is an important subroutine for scheduling and other external graph algorithms. But, the internal topological sorting algorithm cannot handle big DAGs and the I/O complexity of total external topological sorting is too high for practical applications. Therefore, we pay attention to the semi-external topological sorting for big DAGs in this paper. We find that the existing semi-external topological sorting algorithm is mainly based on constructing a DFS-Tree in internal memory. However, this DFS-based algorithm is natively more difficult than topological sorting, because DFS-Tree determines a strict total order, while topological order is only a partial order. Therefore, a partial orderlevel orderis proposed in this paper. Based on thelevel order, we propose a new semi-external topological sorting algorithm. Next, two optimizations,NodeRemoveandEdgeRemove, are proposed to reduce the CPU and I/O cost. In addition, we also propose a batch algorithm. Finally, we perform experimental studies using real and synthetic datasets to confirm the efficiency of our approach. According to the experimental results, our algorithms are better than the previous DFS-based algorithms.

Durable subgraph matching on a temporal graph finds all subgraphs in the temporal graph that not only match the given query graph but also have duration longer than a user-specified duration threshold. The state-of-the-art algorithm (Semertzidis and Pitoura, 2016, 2019) for solving this problem requires lots of memory when the input temporal graph is large. In this paper, a new algorithm is proposed to solve this problem. Many effective techniques are developed to improve the performance of this algorithm, including the DFS-based query decomposition method, the TD-tree index structure, the sort-based vertex matching order, and the time instance set compaction method. The experimental results show that the proposed algorithm is an order of magnitude faster and requires significantly less memory than the state-of-the-art algorithm.

Analyzing dynamic information networks, which contain evolving objects and links, to meet users various needs has attracted much attention in recent years. For sales companies, recruiting staff who are socialites would help to increase sales volume since such staff often sell more. For universities, employing active collaborators who are productive and well connected to many different scholars over time could bring many benefits to their development. However, no previous work has focused on the discovery of socialites and active collaborators who are worthy of investment in reality. In this paper, we advocate a new concept of attractive individuals to model such special objects. We also introduce the concept of attractive groups to represent groups of well-connected attractive individuals. We analyze the complexity of the attractive individual and group search problems. A time and space efficient algorithm is presented to detect attractive individuals. Furthermore, three algorithms are respectively proposed to find top-k representative attractive groups. Experiments on 6 real-world datasets show high performance of our methods and the significance of attractive individuals and groups in reality.

Computing a maximum independent set (MaxIS) is a fundamental NP-hard problem in graph theory, which has important applications in a wide spectrum of fields. Since graphs in many applications are changing frequently over time, the problem of maintaining a MaxIS over dynamic graphs has attracted increasing attention over the past few years. Due to the intractability of maintaining an exact MaxIS, this paper aims to develop efficient algorithms that can maintain an approximate MaxIS with an accuracy guarantee theoretically. In particular, we propose a framework that maintains a$(\displaystyle \frac{\triangle}{2}+1)$-approximate MaxIS over dynamic graphs and prove that it achieves a constant approximation ratio in many real-world networks. To the best of our knowledge, this is the first non-trivial approximability result for the dynamic MaxIS problem. Following the framework, we implement an efficient linear-time dynamic algorithm and a more effective dynamic algorithm with near-linear expected time complexity. Our thorough experiments over real and synthetic graphs demonstrate the effectiveness and efficiency of the pro-posed algorithms, especially when the graph is highly dynamic.

Analyzing dynamic information networks, which contain evolving objects and links, has attracted much attention in recent years. For sales companies, recruiting staff who are socialites would help to increase sales volume since such staff often sell more. For universities, employing active collaborators who are productive and well connected to many different scholars over time could bring many benefits to their development. However, no previous work has focused on socialites and active collaborators who are worthy of investment in reality. In this paper, we advocate attractive individuals to model such special objects, and introduce attractive groups to represent groups of well-connected attractive individuals. Then we propose several algorithms to search attractive individuals and groups. Extensive experiments show high performance of our methods and the significance of attractive individuals and groups in reality.

Multi-criteria decision-making often requires finding a small representative set from the database. A recently proposed method is the regret minimization set (RMS) query. RMS returns a size$r$subset$S$of dataset$D$that minimizes the regret- ratio (the difference between the score of top-1 in$S$and the score of top-l in$D$, for any possible utility function). RMS is not shift invariant, causing inconsistency in results. Further, existing work showed that the regret-ratio is often a “made up” number and users may mistake its absolute value. Instead, users do understand the notion of rank. Thus it considered the problem of finding the minimal set$S$with a rank-regret (the rank of top-l tuple of$S$in the sorted list of$D$) at most$k$, called the rank-regret representative (RRR) problem. Corresponding to RMS, we focus on the min-error version of RRR, called the rank-regret minimization (RRM) problem, which finds a size$r$set to minimize the maximum rank-regret for all utility functions. Further, we generalize RRM and propose the restricted RRM (i.e., RRRM) problem to optimize the rank-regret for functions restricted in a given space. Previous studies on both RMS and RRR did not consider the restricted function space. The solution for RRRM usually has a lower regret level and can better serve the specific preferences of some users. Note that RRM and RRRM are shift invariant. In 2D space, we design a dynamic programming algorithm 2DRRM to return the optimal solution for RRM. In HD space, we propose an algorithm HDRRM that introduces a double approximation guarantee on rank-regret. Both 2DRRM and HDRRM are applicable for RRRM. Extensive experiments on the synthetic and real datasets verify the efficiency and effectiveness of our algorithms. In particular, HDRRM always has the best output uuality in experiments.

Maximizing Range Sum (MaxRS) query is a basic operation in computational geometry and database communities. Given a set of weighted objects in 2-dimensional space and a rectangle, MaxRS query aims to find an optimal position of the rectangle to maximize the total weight of covered objects (i.e., Range Sum). All the existing literature for MaxRS query commonly assumes that every object is associated with a unique point. In real applications, however, every object (e.g., GPS-enabled moving vehicle) is related to a trajectory including a sequence of points, which goes beyond this restrictive assumption. How to tackle the problem of MaxRS query in trajectory data (MaxRST) is important and challenging. In this paper, we propose the definition of MaxRST query where a trajectory is covered by a rectangle if at least one of points in the trajectory is enclosed by the rectangle. We propose a novel method to solve MaxRST query by converting it to rectilinear polygon intersection problem. Then, an interval-tree-based partitioning technique is developed to efficiently settle rectilinear polygon intersection problem. To further shorten the response time, we present ($\epsilon, \delta$) -approximate MaxRST query, which returns an approximate answer having the relative error$\epsilon$to the optimal covered weight with probability at least$\delta$. Furthermore, two complementary sampling-based ($\epsilon, \delta$) -approximate MaxRST algorithms are proposed. One performs random sampling with replacements on rectilinear polygons and the sample size is irrelevant to the number of trajectories. The other employs grid shifting technique to reduce sample size yet requires an extra cost for grid construction. The theoretical analysis and experimental results show that our proposed algorithms have high performance in terms of efficiency and accuracy.

Subsequence matching is an important and fundamental problem on time series data. This paper studies the inherent time complexity of the subsequence matching problem and designs a more efficient algorithm for solving the problem. Firstly, it is proved that the subsequence matching problem is incomputable in time O ( n 1-δ ) even allowing polynomial time preprocessing if the hypothesis SETH is true, where n is the size of the input time series and 0 ≤ δ < 1, i.e., the inherent complexity of the subsequence matching problem is ω ( n 1-δ ). Secondly, an efficient algorithm for subsequence matching problem is proposed. In order to improve the efficiency of the algorithm, we design a new summarization method as well as a novel index for series data. The proposed algorithm supports both Euclidean Distance and DTW distance with or without z -normalization. Experimental results show that the proposed algorithm is up to about 3 ~ 10 times faster than the state of art algorithm on the constrained z -normalized Euclidean Distance and DTW distance, and is up to 7 ~ 12 times faster on Euclidean Distance.

Latent Dirichlet Allocation (LDA) has been widely used for topic modeling, with applications spanning various areas such as natural language processing and information retrieval. While LDA on small and static datasets has been extensively studied, several real-world challenges are posed in practical scenarios where datasets are often huge and are gathered in a streaming fashion. As the state-of-the-art LDA algorithm on streams, Streaming Variational Bayes (SVB) introduced Bayesian updating to provide a streaming procedure. However, the utility of SVB is limited in applications since it ignored three challenges of processing real-world streams: topic evolution , data turbulence , and real-time inference . In this article, we propose a novel distributed LDA algorithm—referred to as StreamFed-LDA— to deal with challenges on streams. For topic modeling of streaming data, the ability to capture evolving topics is essential for practical online inference. To achieve this goal, StreamFed-LDA is based on a specialized framework that supports lifelong (continual) learning of evolving topics. On the other hand, data turbulence is commonly present in streams due to real-life events. In that case, the design of StreamFed-LDA allows the model to learn new characteristics from the most recent data while maintaining the historical information. On massive streaming data, it is difficult and crucial to provide real-time inference results. To increase the throughput and reduce the latency, StreamFed-LDA introduces additional techniques that substantially reduce both computation and communication costs in distributed systems. Experiments on four real-world datasets show that the proposed framework achieves significantly better performance of online inference compared with the baselines. At the same time, StreamFed-LDA also reduces the latency by orders of magnitudes in real-world datasets.

Data quality plays a key role in big data management today. With the explosive growth of data from a variety of sources, the quality of data is faced with multiple problems. Motivated by this, we study the multiple data cleaning on incompleteness and inconsistency with currency reasoning and determination in this paper. We introduce a 4-step framework, named${\sf Imp3C}$, for errors detection and quality improvement in incomplete and inconsistent data without timestamps. We achieve an integrated currency determining method to compute the currency orders among tuples, according to currency constraints. Thus, the inconsistent data and missing values are repaired effectively considering the temporal impact. For both effectiveness and efficiency consideration, we carry out inconsistency repair ahead of incompleteness repair. A currency-related consistency distance metric is defined to measure the similarity between dirty tuples and clean ones more accurately. In addition, currency orders are treated as an important feature in the missing imputation training process. The solution algorithms are introduced in detail with case studies. A thorough experiment on three real-life datasets verifies our method${\sf Imp3C}$improves the performance of data repairing with multiple quality problems.${\sf Imp3C}$outperforms the existing advanced methods, especially in the datasets with complex currency orders.

To aggregate useful information among diversified sources, a hotspot research topic called truth discovery has emerged in recent years. Existing truth discovery methods attempt to infer the true attribute values for the entities by identifying and trusting reliable data sources. That is, the values provided by reliable sources are more likely to be the true values. However, all these methods neglect the relations among different entities, which play important roles in truth discovery task. When reliable data sources cannot provide sufficient information of entities, the true attribute values of these entities can still be inferred by propagating trustworthy information from related entities. Motivated by this, in this paper, we introduce theconstrained truth discoveryproblem. We incorporate denial constraints, a universally quantified first-order logic formalism which can express a large number of effective and widely existing relations among entities, into the process of truth discovery. We formulate it as a constrained optimization problem and analyze its hardness. To address the problem, we propose algorithms to partition the entities into disjoint groups, and generate arithmetic constraints for each disjoint group separately. Then, the true attribute values of the entities in each disjoint group are derived by minimizing the objective function under the corresponding arithmetic constraints. Experimental results on both real-world and synthetic datasets demonstrate that the proposed approach achieves good performance even with very few constraints and reliable sources.

With the growth of data from various sources, data quality is faced with multiple problems. In this paper, we study the multiple data cleaning on incompleteness and inconsistency with currency reasoning and determination. We introduce a 4-step method, named Imp3C, for error detection and repair in incomplete and inconsistent data without timestamps. We propose an integrated currency determining approach to compute currency order among tuples, thus, the dirty data can be repaired effectively considering the temporal impact. Experiments on three real-life datasets verify that Imp3C improves data repairing performance with multiple quality problems, especially in datasets with complex currency orders.

Aggregating the information provided by multiple data sources, which is also known as information integration , plays an important role in data analytics. Since there often exists recording errors, intentional errors, conflicts and outdated data across different data sources, finding the true attribute values of each entity is a fundamental task of crucial importance [3] . The process to fulfill this task is called truth discovery , which has been extensively studied in the literature.

The efficiency of big data analysis has become a bottleneck. Aggregation is a fundamental analytical task. It usually consumes a lot of time so that sampling based aggregation is often used to improve response time at a loss of result accuracy. In all of the related works, sampling is conducted at the granularity of data item. Considering the bits at different bit positions of each data item have different contributions to an aggregation result, the performance of sampling based aggregation has a chance of being improved if sampling is conducted at the granularity of bit. Thus, this paper studies bit-oriented sampling for aggregation. Two methods of bit-oriented uniform sampling based aggregation, i.e., DVBM and DVFM, are proposed which are based on the central limit theorem or the Chebyshev's inequality. They are much more efficient than the methods of the traditional data-oriented uniform sampling based aggregation. DVBM can guarantee a given error bound of aggregation with the assumption that sample variance equals dataset variance. By contrast, DVFM achieves the same goal without that assumption, but it could result in a larger sampling size. Extensive experiments are carried out and the results show that DVBM and DVFM are both efficient and effective.

Entity resolution (ER) is the problem of identifying and merging records that refer to the same real-world entity. In many scenarios, raw records are stored under heterogeneous environment. To leverage such records better, most existing work assume that schema matching and data exchange have been done to convert records under different schemas to those under a predefined schema. However, we observe that schema matching would lose information in some cases, which could be useful or even crucial to ER. To leverage sufficient information from heterogeneous sources, in this paper, we address several challenges of ER on heterogeneous records and show that none of existing similarity metrics or their transformations could be applied to find similar records under heterogeneous settings. Motivated by this, we propose a novel framework to iteratively find records which refer to the same entity as well as an index to generate candidates and accelerate similarity computation. Evaluations on real-world datasets show the effectiveness and efficiency of our methods.

In many fields, a mass of algorithms with completely different hyperparameters have been developed to address the same type of problems. Choosing the algorithm and hyperparameter setting correctly can promote the overall performance greatly, but users often fail to do so due to the absence of knowledge. How to help users to effectively and quickly select the suitable algorithm and hyperparameter settings for the given task instance is an important research topic nowadays, which is known as the CASH problem. In this paper, we design the Auto-Model approach, which makes full use of known information in the related research paper and introduces hyperparameter optimization techniques, to solve the CASH problem effectively. Auto-Model tremendously reduces the cost of algorithm implementations and hyperparameter configuration space, and thus capable of dealing with the CASH problem efficiently and easily. To demonstrate the benefit of Auto-Model, we compare it with classical Auto-Weka approach. The experimental results show that our proposed approach can provide superior results and achieves better performance in a short time.

Entity resolution (ER) is the problem of identifying and merging records that refer to the same real-world entity. In many scenarios, raw records are stored under heterogeneous environment. Specifically, the schemas of records may differ from each other. To leverage such records better, most existing work assume that schema matching and data exchange have been done to convert records under different schemas to those under a predefined schema. However, we observe that schema matching would lose information in some cases, which could be useful or even crucial to ER. To leverage sufficient information from heterogeneous sources, in this paper, we address several challenges of ER on heterogeneous records and show that none of existing similarity metrics or their transformations could be applied to find similar records under heterogeneous settings. Motivated by this, we design the similarity function and propose a novel framework to iteratively find records which refer to the same entity. Regarding efficiency, we build an index to generate candidates and accelerate similarity computation. Evaluations on real-world datasets show the effectiveness and efficiency of our methods.

The skyline query is important in the database community. In recent years, the researches on incomplete data have been increasingly considered, especially for the skyline query. However, the existing skyline definition on incomplete data cannot provide users with valuable references. In this paper, we propose a novel skyline definition utilizing probabilistic model on incomplete data where each point has a probability to be in the skyline. In particular, it returns K points with the highest skyline probabilities. In addition, we propose incomplete models and estimate probability density functions of missing values on independent, correlated, and anti-correlated distributions, respectively. Meanwhile, it is a big challenge to compute probabilistic skyline on incomplete data. We propose three efficient algorithms SPISkyline, SPCSkyline, and SPASkyline for probabilistic skyline computation on incomplete data complying with independent, correlated, and anti-correlated distributions, respectively. They employ pruning strategy, optimization of the process of probability computation, and sorting technique to improve the efficiency of probabilistic skyline computation on incomplete data. Our experimental results demonstrate that our proposed concept of probabilistic skyline is an effective method to tackle skyline query on incomplete data and our algorithms are tens of times faster than the naive algorithm on both synthetic and real datasets.

The current data explosion poses great challenges to approximate aggregation with high efficiency and accuracy. To address this problem, we propose a novel approach to calculate the aggregation answers with a high accuracy using only a small portion of the data. We introduce leverages to reflect individual differences in the data from a statistical perspective. Two kinds of estimators, the leverage-based estimator, and the sketch estimator (a "rough picture" of the aggregation answer), are in constraint relations and iteratively improved according to the actual conditions until their difference is below a threshold. Due to the iteration mechanism and the leverages, our approach achieves a high accuracy. Moreover, some features, such as not requiring recording the sampled data and easy to extend to various execution modes, such as the online mode, make our approach well suited to deal with big data. Experiments show that our approach has an extraordinary performance, and when compared with the uniform sampling, our approach can achieve high-quality answers with only 1/3 sample size.

In this paper, we deal with the problem of rule-based entity resolution on imprecise temporal data. We use record matching dependencies and data currency constraints to derive temporal records' information and trend of their attributes' evolvement with elapsing of time. We firstly block records into smaller blocks, and then by exploring data currency constraints. We propose a temporal clustering approach with two steps, i.e., the skeleton clustering and the banding clustering. Experiments show that our method achieves both high accuracy and efficiency with hidden temporal information on datasets without imprecise timestamps.

A reasonable and effective community scoring function is of great significance since it can measure the community quality of groups we found more properly and help us discover more valuable communities. In this paper, we propose a new community scoring function, ECOQUG. Different from the existing community scoring functions, ECOQUG is designed based on the experimental study and theoretical analysis of groups with different community qualities. ECOQUG is more convincing. In addition, we design a series of experiments to examine the effectiveness and accuracy of ECOQUG and 13 other classic community scoring functions comprehensively. The extensive experimental results show that ECOQUG is effective and better than other community scoring functions.

Abstract This paper revisits set containment join (SCJ) problem, which uses the subset relationship (i.e., $$\subseteq$$ ⊆ ) as condition to join set-valued attributes of two relations and has many fundamental applications in commercial and scientific fields. Existing in-memory algorithms for SCJ are either signature-based or prefix-tree-based. The former incurs high CPU cost because of the enumeration of signatures, while the latter incurs high space cost because of the storage of prefix trees. This paper proposes a new adaptive parameter-free in-memory algorithm, named as frequency-hashjoin or $${\mathsf {FreshJoin}}$$ FreshJoin in short, to evaluate SCJ efficiently. $${\mathsf {FreshJoin}}$$ FreshJoin builds a flat index on-the-fly to record three kinds of signatures (i.e., two least frequent elements and a hash signature whose length is determined adaptively by the frequencies of elements in the universe set). The index consists of two sparse inverted indices and two arrays which record hash signatures of all sets in each relation. The index is well organized such that $${\mathsf {FreshJoin}}$$ FreshJoin can avoid enumerating hash signatures. The rationality of this design is explained. And, the time and space cost of the proposed algorithm, which provide a rule to choose $${\mathsf {FreshJoin}}$$ FreshJoin from existing algorithms, are analyzed. Experiments on 16 real-life datasets show that $${\mathsf {FreshJoin}}$$ FreshJoin usually reduces more than 50% of space cost while remains as competitive as the state-of-the-art algorithms in running time.

The great amount of time series generated by machines has enormous value in intelligent industry. Knowledge can be discovered from high-quality time series, and used for production optimization and anomaly detection in industry. However, the original sensors data always contain many errors. This requires a sophisticated cleaning strategy and a well-designed system for industrial data cleaning. Motivated by this, we introduce Cleanits, a system for industrial time series cleaning. It implements an integrated cleaning strategy for detecting and repairing three kinds of errors in industrial time series. We develop reliable data cleaning algorithms, considering features of both industrial time series and domain knowledge. We demonstrate Cleanits with two real datasets from power plants. The system detects and repairs multiple dirty data precisely, and improves the quality of industrial time series effectively. Cleanits has a friendly interface for users, and result visualization along with logs are available during each cleaning process.

Top-k dominating query is an important operation to return a set of interesting points from a potentially huge data space. For any tuple, its domination score is defined as the number of tuples dominated by the tuple. Top-k dominating query returns the k tuples with the highest domination scores. This paper proposes a novel table-scan-based TDTS algorithm to compute the top-k dominating results on massive data efficiently. TDTS presorts table T to generate PT, whose tuples are arranged in the order of round-robin retrieval on the sorted lists. TDTS performs sequential scan on PT to obtain query results. It is proved that TDTS has the characteristic of early termination. This paper devises efficient pruning operation to reduce the number of candidate tuples and the number of assistant tuples significantly. The experimental results show that, TDTS has a markedly superior performance compared with the existing algorithms.

Mining dense subgraphs on multi-layer graphs is an interesting problem, which has witnessed lots of applications in practice. To overcome the limitations of the quasi-clique-based approach, we propose d-coherent core (d-CC), a new notion of dense subgraph on multi-layer graphs, which has several elegant properties. We formalize the diversified coherent core search (DCCS) problem, which finds k d-CCs that can cover the largest number of vertices. We propose a greedy algorithm with an approximation ratio of 1 - 1/e and two search algorithms with an approximation ratio of 1/4. The experiments verify that the search algorithms are faster than the greedy algorithm and produce comparably good results as the greedy algorithm in practice. As opposed to the quasi-clique-based approach, our DCCS algorithms can fast detect larger dense subgraphs that cover most of the quasi-clique-based results.

Rectangle has been recognized as an essential motif in a large number of real-world networks. Counting rectangles in a network plays an important role in network analysis. This paper comprehensively studies the rectangle counting problem on large networks. We propose a novel counting paradigm called the wedge-centric counting, where a wedge is a simple path consisting of three vertices. Unlike the traditional edge-centric counting, the wedge-centric counting uses wedges instead of edges as building blocks of rectangles. The main advantage of the wedge-centric counting is that it does not need to access two-hop neighbors. Based on this paradigm, we develop a collection of rectangle counting algorithms, including an in-memory algorithm with lower time complexity, an external-memory algorithm with the optimal I/O complexity, and two randomized algorithms with provable error bounds. The experimental results on a variety of real networks verify the effectiveness and the efficiency of the proposed wedge-centric rectangle counting algorithms.

The view propagation problem is a class of view update problem in relational databases [7], involving deletion and insertion propagations. Given source database D, conjunctive query Q, view V generated by query Q(D) and a deletion (insertion) on view ΔV, deletion (insertion) propagation is to find a side effect free update ΔD on D such that the deletion (insertion) of ΔD from (into) D will delete (insert) the intentional ones ΔV without resulting in the deletion (insertion) of additional tuples from (into) the view. Generally, such a deletion (insertion) is side effect free. The related data management applications include query result explanation, data debugging, and anonymizing datasets, which rely on understanding how interventions in a database affect the output of a query. View propagation is a natural and typical way to define such interventions, which seems to be well-studied. However, in general, the candidate update on a source database is picked up aimlessly in advance, making the updated database to be very distant from the original one no matter whether it is the maximum one. In this paper, we formally define the bounded view propagation problem, where candidate update ΔD is bounded as a subset of potential C which is a fixed small tuple set of D. We study the complexity of this problem for conjunctive queries, and make contributions to the previous results of the problems of side-effect free deletion propagation. Specifically, our bounded view propagation problem decreases computational complexity regardless of conjunctive query structure. We show the fixed potential is actually a dichotomy for both deletion and insertion propagations, and figure out the results on combined complexity which is neglected previously. Based on our results, for view propagation, we map out a complete picture of the computational complexity hierarchy for conjunctive queries on both data and combined complexities. Moreover, this bounded version is an update forbidden case of view propagation, and our results can be applied to it.

In this paper, we deal with the problem of rule-based entity resolution on imprecise temporal data. Entity resolution (ER) is widely explored in research community, but the problem on temporal data, especially without available timestamps, has not been studied well yet. Because of the elapsing of time, records referring to the same entity observed in different time periods may be different. Besides traditional similarity-based ER approaches, by carefully exploring several data quality rules, e.g., matching dependency and data currency, much information can be obtained to facilitate to cope with this problem. In this paper, we use such rules to derive temporal records' information of time order and trend of their attributes' evolvement with elapsing of time. Specifically, we first block records into smaller blocks, and then by exploring data currency constraints, we propose a temporal clustering approach with two steps, i.e., the skeleton clustering and the banding clustering. Experimental results on both real and synthetic data show that our entity resolution method can achieve both high accuracy and efficiency on datasets with hidden temporal information.

We describe CleanCloud, a system for cleaning big data based on Map-Reduce paradigm in cloud. Using Map-Reduce paradigm, the system detects and repairs various data quality problems in big data. We demonstrate the following features of CleanCloud: (a) the support for cleaning multiple data quality problems in big data; (b) a visual tool for watching the status of big data cleaning process and tuning the parameters for data cleaning; (c) the friendly interface for data input and setting as well as cleaned data collection for big data. CleanCloud is a promising system that provides scalable and effect data cleaning mechanism for big data in either files or databases.

The skyline query is important in database community. In recent years, the researches on incomplete data have been increasingly considered, especially for the skyline query. However, the existing skyline definition on incomplete data cannot provide users with valuable references. In this paper, we propose a novel skyline definition utilizing probabilistic model on incomplete data where each point has a probability to be in the skyline. In particular, it returnsK points with the highest skyline probabilities. Meanwhile, it is a big challenge to compute probabilistic skyline on incomplete data. We propose an efficient algorithm PISkyline, which utilizes two pruning strategies to reduce the number of points and adopts two optimizations to accelerate probability computation for each point. Nevertheless, PISkyline is susceptible to the order of input data and there is still a great deal of room for optimization. We develop a point-level sorting technique by adjusting the order of accessing points to further improve the efficiency of PISkyline. Our experimental results demonstrate that our algorithms are tens of times faster than the naive algorithm on both synthetic and real datasets.

This paper studies a novel approach to processing massive uncertain graph data. In this approach, we propose a new framework to simultaneously process a query on a set of randomly sampled possible worlds of an uncertain graph. Based on this framework, we develop a series of algorithms to analyze massive uncertain graphs, including breadth-first search, shortest distance queries, triangle counting, and core decomposition. We implement this approach based on GraphLab, one of the stateof-the-art graph processing frameworks. By sharing fine-grained internal processing steps on common substructures of sampled possible worlds, the new approach achieves tens to hundreds of times speedup in execution time on a cluster of 20 servers.

The amount of sensory data manifests an explosive growth due to the increasing popularity of Wireless Sensor Networks (WSNs). The scale of sensory data in many applications has already exceeded several petabytes annually, which is beyond the computation and transmission capabilities of conventional WSNs. On the other hand, the information carried by big sensory data has high redundancy because of strong correlation among sensory data. In this paper, we introduce the novel concept of ϵ-Kernel Dataset, which is only a small data subset and can represent the vast information carried by big sensory data with the information loss rate being less than ϵ, where ϵ can be arbitrarily small. We prove that drawing the minimum ϵ-Kernel Dataset is polynomial time solvable and provide a centralized algorithm with O(n3) time complexity. Furthermore, a distributed algorithm with constant complexity O(1) is designed. It is shown that the result returned by the distributed algorithm can satisfy the ϵ requirement with a near optimal size. Furthermore, two distributed algorithms of maintaining the correlation coefficients among sensor nodes are developed. Finally, the extensive real experiment results and simulation results are presented. The results indicate that all the proposed algorithms have high performance in terms of accuracy and energy efficiency.

In many applications, top-k dominating query is an important operation to return k tuples with the highest domination scores in a potentially huge data space. It is analyzed that the existing algorithms have their performance problems when performed on massive data. This paper proposes a novel table-scan-based TDTS algorithm to efficiently compute top-k dominating results. TDTS first presorts the table for early termination. The early termination checking is proposed in this paper, along with the theoretical analysis of scan depth. The pruning operation for tuples is devised in this paper. The theoretical pruning effect shows that the number of tuples maintained in TDTS can be reduced substantially. The extensive experimental results, conducted on synthetic and real-life data sets, show that TDTS outperforms the existing algorithms significantly.

SimRank is a similarity measure between vertices in a graph. Recently, many algorithms have been proposed to efficiently evaluate SimRank similarities. However, the existing algorithms either overlook uncertainty in graph structures or depends on an unreasonable assumption. In this paper, we study SimRank on uncertain graphs. Following the random-walk-based formulation of SimRank on deterministic graphs and the possible world model of uncertain graphs, we first define random walks on uncertain graphs and show that our definition of random walks satisfies Markov's property. We formulate our SimRank measure based on random walks on uncertain graphs. We discover a critical difference between random walks on uncertain graphs and random walks on deterministic graphs, which makes all existing SimRank computation algorithms on deterministic graphs inapplicable to uncertain graphs. For SimRank computation, we consider computing both single-pair SimRank and single-source top-K SimRank. We propose three algorithms, namely the sampling algorithm with high efficiency, the two-phase algorithm with comparable efficiency and higher accuracy, and a speeding-up algorithm with much higher efficiency. Meanwhile, we present an optimized algorithm for efficient computing the single-source top-K SimRank. The experimental results verify the effectiveness of our SimRank measure and the efficiency of the proposed SimRank computation algorithms.

Top-k query is an important operation to return a set of interesting points from a potentially huge data space. In top-k query, a ranking function is provided to determine the score of each tuple and k tuples with the largest scores are returned.

SimRank is a similarity measure between vertices in a graph, which has become a fundamental technique in graph analytics. Recently, many algorithms have been proposed for efficient evaluation of SimRank similarities. However, the existing SimRank computation algorithms either overlook uncertainty in graph structures or is based on an unreasonable assumption (Du et al). In this paper, we study SimRank similarities on uncertain graphs based on the possible world model of uncertain graphs. Following the random-walk-based formulation of SimRank on deterministic graphs and the possible worlds model of uncertain graphs, we define random walks on uncertain graphs for the first time and show that our definition of random walks satisfies Markov's property. We formulate the SimRank measure based on random walks on uncertain graphs. We discover a critical difference between random walks on uncertain graphs and random walks on deterministic graphs, which makes all existing SimRank computation algorithms on deterministic graphs inapplicable to uncertain graphs. To efficiently compute SimRank similarities, we propose three algorithms, namely the baseline algorithm with high accuracy, the sampling algorithm with high efficiency, and the two-phase algorithm with comparable efficiency as the sampling algorithm and about an order of magnitude smaller relative error than the sampling algorithm. The extensive experiments and case studies verify the effectiveness of our SimRank measure and the efficiency of our SimRank computation algorithms.

A fundamental problem of time series is k nearest neighbor (k-NN) query processing. However, existing methods are not fast enough for large dataset. In this paper, we propose a novel approach, STS3, to process k-NN queries by transforming time series to sets and measure the similarity under Jaccard metric. Our approach is more accurate than Dynamic Time Warping(DTW) in our suitable scenarios and it is faster than most of the existing methods, due to the efficient similarity search for sets. Besides, we also developed an index, a pruning and an approximation technique to improve the k-NN query procedure. As shown in the experimental results, all of them could accelerate the query processing effectively.

With the rapid development of information technologies and data acquisition technologies, the era of big data has arrived.In the recent years, big data have been accumulated by many countries, and the size of data has exceeded PB (10 15 bytes) in many areas such as energy, manufacturing, transportation, service industry, education and public health.The enormous values of big data can be summarized as follows.(1) Accelerating economic development In 2012, Gartner, a world-famous international consulting organization, released a report forecasting that the global big data-related industrial scale will reach $232 billion in 2016.A Mckinsey Global Institute report forecasts that big data will bring an economic value of $300 billion annually only in the medical industry.In China, many companies such as Alibaba and Baidu have gained a great amount of economic benefit by querying, mining and analyzing big data.(2) Promoting social progress Big data play an important role in social progress, which can be witnessed by the following facts.Financial big data can help the government on the aspects of decision-making.Big data from the areas of energy, transportation, environment and geography can help with city management, conserving energy, intelligent traffic control and environment monitoring.Big health data can be utilized to monitor the running status of medical systems and the trends of people's health, to lower healthcare costs and to improve health care standard and health conditions of the whole society.Big data from education can help with promoting the effectiveness and efficiency of education.

Since regular expressions are often used to detect errors in sequences such as strings or date, it is natural to use them for data repair. Motivated by this, we propose a data repair method based on regular expression to make the input sequence data obey the given regular expression with minimal revision cost. The proposed method contains two steps, sequence repair and token value repair. For sequence repair, we propose the Regular-expression-based Structural Repair (RSR in short) algorithm. RSR algorithm is a dynamic programming algorithm that utilizes Nondeterministic Finite Automata (NFA) to calculate the edit distance between a prefix of the input string and a partial pattern regular expression with time complexity of O ( nm 2 ) and space complexity of O ( mn ) where m is the edge number of NFA and n is the input string length. We also develop an optimization strategy to achieve higher performance for long strings. For token value repair, we combine the edit-distance-based method and associate rules by a unified argument for the selection of the proper method. Experimental results on both real and synthetic data show that the proposed method could repair the data effectively and efficiently.

Uncertain graphs have been widely used to represent graph data with inherent uncertainty in structures. Reliability search is a fundamental problem in uncertain graph analytics. This paper studies a new problem, the top-k reliability search problem on uncertain graphs, that is, finding k vertices v with the highest reliabilities of connections from a source vertex s to v. Note that the existing algorithm for the threshold-based reliability search problem is inefficient for the top-k reliability search problem. We propose a new algorithm to efficiently solve the top-k reliability search problem. The algorithm adopts two important techniques, namely the BFS sharing technique and the offline sampling technique. The BFS sharing technique exploits overlaps among different sampled possible worlds of the input uncertain graph and performs a single BFS on all possible worlds simultaneously. The offline sampling technique samples possible worlds offline and stored them using a compact structure. The algorithm also takes advantages of bit vectors and bitwise operations to improve efficiency. Moreover, we generalize the top-k reliability search problem to the multi-source case and show that the multi-source case of the problem can be equivalently converted to the single-source case of the problem. Extensive experiments carried out on both real and synthetic datasets verify that the optimized algorithm outperforms the baselines by 1 - 2 orders of magnitude in execution time while achieving comparable accuracy. Meanwhile, the optimized algorithm exhibits linear scalability with respect to the size of the input uncertain graph.

In many applications, top-k query is an important operation to return a set of interesting points in a potentially huge data space. It is analyzed in this paper that the existing algorithms cannot process top-k query on massive data efficiently. This paper proposes a novel table-scan-based T2S algorithm to efficiently compute top-k results on massive data. T2S first constructs the presorted table, whose tuples are arranged in the order of the round-robin retrieval on the sorted lists. T2S maintains only fixed number of tuples to compute results. The early termination checking for T2S is presented in this paper, along with the analysis of scan depth. The selective retrieval is devised to skip the tuples in the presorted table which are not top-k results. The theoretical analysis proves that selective retrieval can reduce the number of the retrieved tuples significantly. The construction and incremental-update/batchprocessing methods for the used structures are proposed in this paper. The extensive experimental results, conducted on synthetic and real-life data sets, show that T2S has a significant advantage over the existing algorithms.

The objective of entity resolution (ER) is to identify records referring to the same real-world entity. Traditional ER approaches identify records based on pairwise similarity comparisons, which assumes that records referring to the same entity are more similar to each other than otherwise. However, this assumption does not always hold in practice and similarity comparisons do not work well when such assumption breaks. We propose a new class of rules which could describe the complex matching conditions between records and entities. Based on this class of rules, we present the rule-based entity resolution problem and develop an on-line approach for ER. In this framework, by applying rules to each record, we identify which entity the record refers to. Additionally, we propose an effective and efficient rule discovery algorithm. We experimentally evaluated our rule-based ER algorithm on real data sets. The experimental results show that both our rule discovery algorithm and rule-based ER algorithm can achieve high performance.

In this demo, we present Cleanix, a prototype system for cleaning relational Big Data. Cleanix takes data integrated from multiple data sources and cleans them on a shared-nothing machine cluster. The backend system is built on-top-of an extensible and flexible data-parallel substrate - the Hyracks framework. Cleanix supports various data cleaning tasks such as abnormal value detection and correction, incomplete data filling, de-duplication, and conflict resolution. We demonstrate that Cleanix is a practical tool that supports effective and efficient data cleaning at the large scale.

Shortest path query is an important problem and has been well studied in static graphs. However, in practice, the costs of edges in graphs always change over time. We call such graphs as time-dependent graphs. In this paper, we study how to find a cost-optimal path with time constraint in time-dependent graphs. Most existing works regarding the Time-Dependent Shortest Path (TDSP) problem focus on finding a shortest path with the minimum travel time. All these works are based on the following fact: the earliest arrival time at a vertex v can be derived from the earliest arrival time at v 's neighbors. Unfortunately, this fact does not hold for our problem. In this paper, we propose a novel algorithm to compute a cost-optimal path with time constraint in time-dependent graphs. We show that the time and space complexities of our algorithm are O ( kn log n + mk ) and O (( n + m ) k ) respectively. We confirm the effectiveness and efficiency of our algorithm through conducting experiments on real datasets with synthetic cost.

This paper investigates incremental detection of errors in distributed data. Given a distributed database D, a set Σ of conditional functional dependencies (CFDs), the set V of violations of the CFDs in D, and updates ΔD to D, it is to find, with minimum data shipment, changes ΔV to V in response to ΔD. The need for the study is evident since real-life data is often dirty, distributed and frequently updated. It is often prohibitively expensive to recompute the entire set of violations when D is updated. We show that the incremental detection problem is NP-complete for database D that is partitioned either vertically or horizontally, even when Σ and D are fixed. Nevertheless, we show that it is bounded: there exist algorithms to detect errors such that their computational cost and data shipment are both linear in the size of ΔD and ΔV, independent of the size of the database D. We provide such incremental algorithms for vertically partitioned data and horizontally partitioned data, and show that the algorithms are optimal. We further propose optimization techniques for the incremental algorithm over vertical partitions to reduce data shipment. We verify experimentally, using real-life data on Amazon Elastic Compute Cloud (EC2), that our algorithms substantially outperform their batch counterparts.

Structural-context similarities between vertices in graphs, such as the Jaccard similarity, the Dice similarity, and the cosine similarity, play important roles in a number of graph data analysis techniques. However, uncertainty is inherent in massive graph data, and therefore the classical definitions of structural-context similarities on exact graphs don't make sense on uncertain graphs. In this paper, we propose a generic definition of structural-context similarity for uncertain graphs. Since it is computationally prohibitive to compute the similarity between two vertices of an uncertain graph directly by its definition, we investigate two efficient approaches to computing similarities, namely the polynomial-time exact algorithms and the linear-time approximation algorithms. The experimental results on real uncertain graphs verify the effectiveness of the proposed structural-context similarities as well as the accuracy and efficiency of the proposed evaluation algorithms.

The retrieval results of online products information in e-commerce web sites are often difficult for users to use because of different descriptions for the same product. This paper proposes ProductSeeker, a product retrieval system organizing results according to their referring real-world entities for the conveniences of users. In the demonstration, we will present our system providing friendly interface to retrieve fresh product information and refining results according to feedback.

Entity resolution (ER) is to find the data objects referring to the same real-world entity. When ER is performed on relations, the crucial operator is record matching, which is to judge whether two tuples refer to the same real-world entity. Record matching is a longstanding issue. However, with massive and complex data in applications, current methods cannot satisfy the requirements. A Sequence-rule-based record matching (SeReMatching) is presented with the consideration of both which attributes should be used and their importance in record matching. We have changed the Bloom filter and therefore the checking speed is greatly increased. The best performance of the algorithm makes the complexity of entity resolution O (n). And extensive experiments were performed to evaluate our methods.

Skyline is an important operation in many applications to return a set of interesting points from a potentially huge data space. Given a table, the operation finds all tuples that are not dominated by any other tuples. It is found that the existing algorithms cannot process skyline on big data efficiently. This paper presents a novel skyline algorithm SSPL on big data. SSPL utilizes sorted positional index lists which require low space overhead to reduce I/O cost significantly. The sorted positional index list Ljis constructed for each attribute Ajand is arranged in ascending order of Aj. SSPL consists of two phases. In phase 1, SSPL computes scan depth of the involved sorted positional index lists. During retrieving the lists in a round-robin fashion, SSPL performs pruning on any candidate positional index to discard the candidate whose corresponding tuple is not skyline result. Phase 1 ends when there is a candidate positional index seen in all of the involved lists. In phase 2, SSPL exploits the obtained candidate positional indexes to get skyline results by a selective and sequential scan on the table. The experimental results on synthetic and real data sets show that SSPL has a significant advantage over the existing skyline algorithms.

Shortest path query is an important problem in graphs and has been well-studied. However, most approaches for shortest path query are based on single-cost (weight) graphs. In this paper, we introduce the definition of multi-cost graph and study a novel query: the optimal path query over multi-cost graphs. We propose a best-first branch and bound search algorithm with two optimizing strategies. Furthermore, we propose a novel index named k-cluster index to make our method more space and time efficient for large graphs. We discuss how to construct and utilize k-cluster index. We confirm the effectiveness and efficiency of our algorithms using real-life datasets in experiments.

Abstract — One of the central problems for data quality is inconsistency detection. Given a database D and a set Σ of dependencies as data quality rules, we want to identify tuples in D that violate some rules in Σ. When D is a centralized database, there have been effective SQL-based techniques for finding violations. It is, however, far more challenging when data in D is distributed, in which inconsistency detection often necessarily requires shipping data from one site to another. This paper develops techniques for detecting violations of conditional functional dependencies (CFDs) in relations that are fragmented and distributed across different sites. (1) We formulate the detection problem in various distributed settings as optimization problems, measured by either network traffic or response time. (2) We show that it is beyond reach in practice to find optimal detection methods: the detection problem is NP-complete when the data is partitioned either horizontally or vertically, and when we aim to minimize either data shipment or response time. (3) For data that is horizontally partitioned, we provide several algorithms to find violations of a set of CFDs, leveraging the structure of CFDs to reduce data shipment or increase parallelism. (4) We verify experimentally that our algorithms are scalable on large relations and complex CFDs. (5) For data that is vertically partitioned, we provide a characterization for CFDs to be checked locally without requiring data shipment, in terms of dependency preservation. We show that it is intractable to minimally refine a partition and make it dependency preserving. I.

With the rapid development of advanced data acquisition techniques such as high-throughput biological experiments and wireless sensor networks, large amount of graph-structured data, graph data for short, have been collected in a wide range of applications. Discovering knowledge from graph data has witnessed a number of applications and received a lot of research attentions. Recently, it is observed that uncertainties are inherent in the structures of some graph data. For example, protein-protein interaction (PPI) data can be represented as a graph, where vertices represent proteins, and edges represent PPI's. Due to the limits of PPI detection methods, it is uncertain that a detected PPI exist in practice. Other examples of uncertain graph data include topologies of wireless sensor networks, social networks and so on. Managing and mining such large-scale uncertain graph data is of both theoretical and practical significance. Many solid works have been conducted on uncertain graph mining from the aspects of models, semantics, methodology and algorithms in last few years. A number of research papers on managing and mining uncertain graph data have been published in the database and data mining conferences such as VLDB, ICDE, KDD, CIKM and EDBT. This talk focuses on the data model, semantics, computational complexity and algorithms of uncertain graph mining. In the talk, some typical research work in the field of uncertain graph mining will also be introduced, including frequent subgraph pattern mining, dense subgraph detection, reliable subgraph discovery, and clustering on uncertain graph data.

It is common to find graphs with millions of nodes and billions of edges in, e.g., social networks. Queries on such graphs are often prohibitively expensive. These motivate us to propose query preserving graph compression, to compress graphs relative to a class Λ of queries of users' choice. We compute a small Gr from a graph G such that (a) for any query Q Ε Λ Q, Q(G) = Q'(Gr), where Q' Ε Λ can be efficiently computed from Q; and (b) any algorithm for computing Q(G) can be directly applied to evaluating Q' on Gr as is. That is, while we cannot lower the complexity of evaluating graph queries, we reduce data graphs while preserving the answers to all the queries in Λ. To verify the effectiveness of this approach, (1) we develop compression strategies for two classes of queries: reachability and graph pattern queries via (bounded) simulation. We show that graphs can be efficiently compressed via a reachability equivalence relation and graph bisimulation, respectively, while reserving query answers. (2) We provide techniques for aintaining compressed graph Gr in response to changes ΔG to the original graph G. We show that the incremental maintenance problems are unbounded for the two lasses of queries, i.e., their costs are not a function of the size of ΔG and changes in Gr. Nevertheless, we develop incremental algorithms that depend only on ΔG and Gr, independent of G, i.e., we do not have to decompress Gr to propagate the changes. (3) Using real-life data, we experimentally verify that our compression techniques could reduce graphs in average by 95% for reachability and 57% for graph pattern matching, and that our incremental maintenance algorithms are efficient.

The ability to handle large scale graph data is crucial to an increasing number of applications. Much work has been dedicated to supporting basic graph operations such as subgraph matching, reachability, regular expression matching, etc. In many cases, graph indices are employed to speed up query processing. Typically, most indices require either super-linear indexing time or super-linear indexing space. Unfortunately, for very large graphs, super-linear approaches are almost always infeasible. In this paper, we study the problem of subgraph matching on billion-node graphs. We present a novel algorithm that supports efficient subgraph matching for graphs deployed on a distributed memory store. Instead of relying on super-linear indices, we use efficient graph exploration and massive parallel computing for query processing. Our experimental results demonstrate the feasibility of performing subgraph matching on web-scale graph data.

This paper investigates three problems identified in [1] for annotation propagation, namely, the view side-effect, source side-effect, and annotation placement problems. Given annotations entered for a tuple or an attribute in a view, these problems ask what tuples or attributes in the source have to be annotated to produce the view annotations. As observed in [1], these problems are fundamental not only for data provenance but also for the management of view updates. For an annotation attached to a single existing tuple in a view, it has been shown that these problems are often intractable even for views defined in terms of simple SPJU queries [1]. We revisit these problems by considering several dichotomies: (1) views defined in various subclasses of SPJU, versus SPJU views under a practical key preserving condition; (2) annotations attached to existing tuples in a view versus annotations on tuples to be inserted into the view; and (3) a single-tuple annotation versus a group of annotations. We provide a complete picture of intractability and tractability for the three problems in all these settings. We show that key preserving views often simplify the propagation analysis. Indeed, some problems become tractable for certain key preserving views, as opposed to the intractability of their counterparts that are not key preserving. However, group annotations often make the analysis harder. In addition, the problems have quite diverse complexity when annotations are attached to existing tuples in a view and when they are entered for tuples to be inserted into the view.

This article proposes algorithms for evaluating XPath queries over an XML tree that is partitioned horizontally and vertically, and is distributed across a number of sites. The key idea is based on partial evaluation: it is to send the whole query to each site that partially evaluates the query, in parallel, and sends the results as compact (Boolean) functions to a coordinator that combines these to obtain the result. This approach possesses the following performance guarantees. First, each site is visited at most twice for data-selecting XPath queries, and only once for Boolean XPath queries. Second, the network traffic is determined by the answer to the query, rather than the size of the tree. Third, the total computation is comparable to that of centralized algorithms on the tree stored in a single site, regardless of how the tree is fragmented and distributed. We also present a MapReduce algorithm for evaluating Boolean XPath queries, based on partial evaluation. In addition, we provide algorithms to evaluate XPath queries on very large XML trees, in a centralized setting. We show both analytically and empirically that our techniques are scalable with large trees and complex XPath queries. These results, we believe, illustrate the usefulness and potential of partial evaluation in distributed systems as well as centralized XML stores for evaluating XPath queries and beyond.

In this paper, we consider the entity resolution(ER) problem, which is to identify objects referring to the same real-world entity. Prior work of ER involves expensive similarity comparison and clustering approaches. Additionally, the quality of entity resolution may be low due to insufficient information. To address these problems, by adopting context information of data objects, we present a novel framework of entity resolution, context-based entity description (CED), to make context information help entity resolution. In our framework, each entity is described by a set of CEDs. During entity resolution, objects are only compared with CEDs to determine its corresponding entity. Additionally, we propose efficient algorithms for CED discovery and CED-based entity resolution. We experimentally evaluated our CED-based ER algorithm on the real DBLP datasets, and the experimental results show that our algorithm can achieve both high precision and recall as well as outperform existing methods.

It is increasingly common to find graphs in which edges bear different types, indicating a variety of relationships. For such graphs we propose a class of reachability queries and a class of graph patterns, in which an edge is specified with a regular expression of a certain form, expressing the connectivity in a data graph via edges of various types. In addition, we define graph pattern matching based on a revised notion of graph simulation. On graphs in emerging applications such as social networks, we show that these queries are capable of finding more sensible information than their traditional counterparts. Better still, their increased expressive power does not come with extra complexity. Indeed, (1) we investigate their containment and minimization problems, and show that these fundamental problems are in quadratic time for reachability queries and are in cubic time for pattern queries. (2) We develop an algorithm for answering reachability queries, in quadratic time as for their traditional counterpart. (3) We provide two cubic-time algorithms for evaluating graph pattern queries based on extended graph simulation, as opposed to the NP-completeness of graph pattern matching via subgraph isomorphism. (4) The effectiveness, efficiency and scalability of these algorithms are experimentally verified using real-life data and synthetic data.

Graph pattern matching has become a routine process in emerging applications such as social networks. In practice a data graph is typically large, and is frequently updated with small changes. It is often prohibitively expensive to recompute matches from scratch via batch algorithms when the graph is updated. With this comes the need for incremental algorithms that compute changes to the matches in response to updates, to minimize unnecessary recomputation. This paper investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. (1) For simulation, we provide incremental algorithms for unit updates and certain graph patterns. These algorithms are optimal: in linear time in the size of the changes in the input and output, which characterizes the cost that is inherent to the problem itself. For general patterns we show that the incremental matching problem is unbounded, i.e., its cost is not determined by the size of the changes alone. (2) For bounded simulation, we show that the problem is unbounded even for unit updates and path patterns. (3) For subgraph isomorphism, we show that the problem is intractable and unbounded for unit updates and path patterns. (4) For multiple updates, we develop an incremental algorithm for each of simulation, bounded simulation and subgraph isomorphism. We experimentally verify that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.

Central to a data cleaning system are record matching and data repairing. Matching aims to identify tuples that refer to the same real-world object, and repairing is to make a database consistent by fixing errors in the data by using constraints. These are treated as separate processes in current data cleaning systems, based on heuristic solutions. This paper studies a new problem, namely, the interaction between record matching and data repairing. We show that repairing can effectively help us identify matches, and vice versa. To capture the interaction, we propose a uniform framework that seamlessly unifies repairing and matching operations, to clean a database based on integrity constraints, matching rules and master data. We give a full treatment of fundamental problems associated with data cleaning via matching and repairing, including the static analyses of constraints and rules taken together, and the complexity, termination and determinism analyses of data cleaning. We show that these problems are hard, ranging from NP- or coNP-complete, to PSPACE-complete. Nevertheless, we propose efficient algorithms to clean data via both matching and repairing. The algorithms find deterministic fixes and reliable fixes based on confidence and entropy analysis, respectively, which are more accurate than possible fixes generated by heuristics. We experimentally verify that our techniques significantly improve the accuracy of record matching and data repairing taken as separate processes, using real-life data.

This paper investigates the discovery of conditional functional dependencies (CFDs). CFDs are a recent extension of functional dependencies (FDs) by supporting patterns of semantically related constants, and can be used as rules for cleaning relational data. However, finding quality CFDs is an expensive process that involves intensive manual effort. To effectively identify data cleaning rules, we develop techniques for discovering CFDs from relations. Already hard for traditional FDs, the discovery problem is more difficult for CFDs. Indeed, mining patterns in CFDs introduces new challenges. We provide three methods for CFD discovery. The first, referred to as CFDMiner, is based on techniques for mining closed item sets, and is used to discover constant CFDs, namely, CFDs with constant patterns only. Constant CFDs are particularly important for object identification, which is essential to data cleaning and data integration. The other two algorithms are developed for discovering general CFDs. One algorithm, referred to as CTANE, is a levelwise algorithm that extends TANE, a well-known algorithm for mining FDs. The other, referred to as FastCFD, is based on the depth-first approach used in FastFD, a method for discovering FDs. It leverages closed-item-set mining to reduce the search space. As verified by our experimental study, CFDMiner can be multiple orders of magnitude faster than CTANE and FastCFD for constant CFD discovery. CTANE works well when a given relation is large, but it does not scale well with the arity of the relation. FastCFD is far more efficient than CTANE when the arity of the relation is large; better still, leveraging optimization based on closed-item-set mining, FastCFD also scales well with the size of the relation. These algorithms provide a set of cleaning-rule discovery tools for users to choose for different applications.

We investigate the problem of summarizing frequent subgraphs by a smaller set of representative patterns. We show that some special graph patterns, called δ-jump patterns in this paper, must be representative patterns. Based on the fact, we devise two algorithms, RP-FP and RP-GD, to mine a representative set that summarizes frequent subgraphs. RP-FP derives a representative set from frequent closed subgraphs, whereas RP-GD mines a representative set from graph databases directly. Three novel heuristic strategies, Last-Succeed-First-Check, Reverse-Path-Trace, and Nephew-Representative-Based-Cover, are proposed to further improve the efficiency of RP-GD. RP-FP can provide a tight ratio bound but has heavy computation cost. RP-GD cannot provide a ratio bound guarantee but is more efficient than RP-FP. We also make use of the similarity between sibling branches in the graph pattern space to devise another much more efficient algorithm, RP-Leap, for mining a representative set that can approximately summarize frequent subgraphs. Our extensive experiments on both real and synthetic data sets verify the summarization quality and efficiency of our algorithms. To further demonstrate the interestingness of representative patterns, we study an application of representative patterns to classification. We demonstrate that the classification accuracy achieved by representative pattern-based model is no less than that achieved by closed graph pattern-based model.

In corporate networks, daily business data are generated in gigabytes or even terabytes. It is costly to process aggregate queries in those systems. In this paper, we propose PACA, a probably approximately correct aggregate query processing scheme, for answering aggregate queries in structured Peer-to-Peer (P2P) network. PACA retrieves random samples from peers' databases and applies the samples to process queries. Instead of scanning the entire database of each peer, PACA only accesses a small random number of data. Moreover, based on the query distribution,PACA publishes a precomputed synopsis and uses the synopsis to answer future queries. Most queries are expected to be answered by the precomputed synopsis partially or fully. And the synopsis is adaptively tuned to follow the query distribution. Experiments on the PlanetLab show the effectiveness of the approach.

Existing studies on graph mining focus on exact graphs that are precise and complete. However, graph data tends to be uncertain in practice due to noise, incompleteness and inaccuracy. This paper investigates the problem of finding top-k maximal cliques in an uncertain graph. A new model of uncertain graphs is presented, and an intuitive measure is introduced to evaluate the significance of vertex sets. An optimized branch-and-bound algorithm is developed to find top-k maximal cliques, which adopts efficient pruning rules, a new searching strategy and effective preprocessing methods. The extensive experimental results show that the proposed algorithm is very efficient on real uncertain graphs, and the top-k maximal cliques are very useful for real applications, e.g. protein complex prediction.

Frequent subgraph mining has been extensively studied on certain graph data. However, uncertainties are inherently accompanied with graph data in practice, and there is very few work on mining uncertain graph data. This paper investigates frequent subgraph mining on uncertain graphs under probabilistic semantics. Specifically, a measure called φ-frequent probability is introduced to evaluate the degree of recurrence of subgraphs. Given a set of uncertain graphs and two numbers 0 < φ,τ < 1, the goal is to quickly find all subgraphs with φ-frequent probability at least τ. Due to the NP-hardness of the problem, an approximate mining algorithm is proposed for this problem. Let 0 < δ < 1 be a parameter. The algorithm guarantees to find any frequent subgraph S with probability at least (1 - δ/2)s, where s is the number of edges of S. In addition, it is thoroughly discussed how to set δ to guarantee the overall approximation quality of the algorithm. The extensive experiments on real uncertain graph data verify that the algorithm is efficient and that the mining results have very high quality.

Providing scalable database services is an essential requirement for extending many existing applications of the Cloud platform. Due to the diversity of applications, database services on the Cloud must support large-scale data analytical jobs and high concurrent OLTP queries. Most existing work focuses on some specific type of applications. To provide an integrated framework, we are designing a new system, epiC, as our solution to next-generation database systems. In epiC, indexes play an important role in improving overall performance. Different types of indexes are built to provide efficient query processing for different applications.

Graph pattern matching is typically defined in terms of subgraph isomorphism, which makes it an np-complete problem. Moreover, it requires bijective functions, which are often too restrictive to characterize patterns in emerging applications. We propose a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, we define matching based on a notion of bounded simulation, an extension of graph simulation. We show that with this revision, graph pattern matching can be performed in cubic-time, by providing such an algorithm. We also develop algorithms for incrementally finding matches when data graphs are updated, with performance guarantees for dag patterns. We experimentally verify that these algorithms scale well, and that the revised notion of graph pattern matching allows us to identify communities commonly found in real-world networks.

A variety of integrity constraints have been studied for data cleaning. While these constraints can detect the presence of errors, they fall short of guiding us to correct the errors. Indeed, data repairing based on these constraints may not find certain fixes that are absolutely correct, and worse, may introduce new errors when repairing the data. We propose a method for finding certain fixes, based on master data, a notion of certain regions , and a class of editing rules . A certain region is a set of attributes that are assured correct by the users. Given a certain region and master data, editing rules tell us what attributes to fix and how to update them. We show how the method can be used in data monitoring and enrichment. We develop techniques for reasoning about editing rules, to decide whether they lead to a unique fix and whether they are able to fix all the attributes in a tuple, relative to master data and a certain region. We also provide an algorithm to identify minimal certain regions, such that a certain fix is warranted by editing rules and master data as long as one of the regions is correct. We experimentally verify the effectiveness and scalability of the algorithm.

In a variety of emerging applications one needs to decide whether a graph G matches another G p , i.e. , whether G has a topological structure similar to that of G p . The traditional notions of graph homomorphism and isomorphism often fall short of capturing the structural similarity in these applications. This paper studies revisions of these notions, providing a full treatment from complexity to algorithms. (1) We propose p-homomorphism (p -hom) and 1-1 p -hom, which extend graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the similarity of nodes . (2) We introduce metrics to measure graph similarity, and several optimization problems for p -hom and 1-1 p -hom. (3) We show that the decision problems for p -hom and 1-1 p -hom are NP-complete even for DAGs, and that the optimization problems are approximation-hard. (4) Nevertheless, we provide approximation algorithms with provable guarantees on match quality. We experimentally verify the effectiveness of the revised notions and the efficiency of our algorithms in Web site matching, using real-life and synthetic data.

In many real applications, graph data is subject to uncertainties due to incompleteness and imprecision of data. Mining such uncertain graph data is semantically different from and computationally more challenging than mining conventional exact graph data. This paper investigates the problem of mining uncertain graph data and especially focuses on mining frequent subgraph patterns on an uncertain graph database. A novel model of uncertain graphs is presented, and the frequent subgraph pattern mining problem is formalized by introducing a new measure, called expected support. This problem is proved to be NP-hard. An approximate mining algorithm is proposed to find a set of approximately frequent subgraph patterns by allowing an error tolerance on expected supports of discovered subgraph patterns. The algorithm uses efficient methods to determine whether a subgraph pattern can be output or not and a new pruning method to reduce the complexity of examining subgraph patterns. Analytical and experimental results show that the algorithm is very efficient, accurate, and scalable for large uncertain graph databases. To the best of our knowledge, this paper is the first one to investigate the problem of mining frequent subgraph patterns from uncertain graph data.

Graph data are subject to uncertainties in many applications due to incompleteness and imprecision of data. Mining uncertain graph data is semantically different from and computationally more challenging than mining exact graph data. This paper investigates the problem of mining frequent subgraph patterns from uncertain graph data. The frequent subgraph pattern mining problem is formalized by designing a new measure called expected support. An approximate mining algorithm is proposed to find an approximate set of frequent subgraph patterns by allowing an error tolerance on the expected supports of the discovered subgraph patterns. The algorithm uses an efficient approximation algorithm to determine whether a subgraph pattern can be output or not. The analytical and experimental results show that the algorithm is very efficient, accurate and scalable for large uncertain graph databases.

In recent years, large amount of data modeled by graphs, namely graph data, have been collected in various domains. Efficiently processing queries on graph databases has attracted a lot of research attentions. Supergraph query is a kind of new and important queries in practice. A supergraph query, q, on a graph database D is to retrieve all graphs in D such that q is a supergraph of them. Because the number of graphs in databases is large and subgraph isomorphism testing is NP-complete, efficiently processing such queries is a big challenge. This paper first proposes an optimal compact method for organizing graph databases. Common subgraphs of the graphs in a database are stored only once in the compact organization of the database, in order to reduce the overall cost of subgraph isomorphism testings from stored graphs to queries during query processing. Then, an exact algorithm and an approximate algorithm for generating significant feature set with optimal order are proposed to construct indices on graph databases. The optimal order on the feature set is to reduce the number of subgraph isomorphism testings during query processing. Based on the compact organization of graph databases, a novel algorithm of testing subgraph isomorphisms from multiple graphs to one graph is presented. Finally, based on all these techniques, a query processing method is proposed. Analytical and experimental results show that the proposed algorithms outperform the existing similar algorithms by one to two orders of magnitude. 1.

In community web management systems (CWMS), storage structures inspired by universal tables are being used increasingly to manage sparse datasets. Such a sparse wide table (SWT) typically embodies thousands of attributes, with many of them being undefined in each tuple, and low-dimensional structured similarity search on a combination of numerical and text attributes is a common operation. However, many properties of such wide tables and their associated Web 2.0 services render most multi-dimensional indexing structures irrelevant. Recent studies in this area have mainly focused on improving the storage efficiency and efficient deployment of inverted indices; so far no new index has been proposed for indexing SWTs. The inverted index is fast for scanning but not efficient in reducing random accesses to the data file as it captures little information about the content of attribute values. In this paper, we propose the iVA-file that works on the basis of approximate contents and keeps scanning efficiency within a bounded range. We introduce the nG-signature to approximately represent data strings and improve the existing approximate vectors for numerical values. We also propose an efficient query processing strategy for the iVA-file, which is different from strategies used for existing scan-based indices. To enable the use of different metrics of distance between a query and a tuple that may vary from application to application, the iVA-file has been designed to be metric-oblivious and to provide efficient filter-and-refine search based on any rational metric. Extensive experiments on real datasets show that the iVA-file outperforms existing proposals in query efficiency significantly, at the same time, keeps a good update speed.

Traditionally, distributed databases assume that the (small) set of nodes participating in a query is known apriori, the data is well placed, and the statistics are readily available. However, these assumptions are no longer valid in a peer-based database management system (PDBMS). As such, it is a challenge to process and optimize queries in a PDBMS. In this paper, we present our distributed solution to this problem for multi-way join queries. Our approach first processes a multi-way join query based on an initial query evaluation plan (generated using statistical data that may be obsolete or inaccurate); as the query is being processed, statistics obtained on-the-fly are used to (continuously) refine the current plan dynamically into a more effective one. We have conducted an extensive performance study which shows that our adaptive query processing strategy can reduce the network traffic significantly.

To accurately match records it is often necessary to utilize the semantics of the data. Functional dependencies (FDs) have proven useful in identifying tuples in a clean relation, based on the semantics of the data. For all the reasons that FDs and their inference are needed, it is also important to develop dependencies and their reasoning techniques for matching tuples from unreliable data sources. This paper investigates dependencies and their reasoning for record matching. (a) We introduce a class of matching dependencies (MDs) for specifying the semantics of data in unreliable relations, defined in terms of similarity metrics and a dynamic semantics . (b) We identify a special case of MDs, referred to as relative candidate keys (RCKs), to determine what attributes to compare and how to compare them when matching records across possibly different relations. (c) We propose a mechanism for inferring MDs, a departure from traditional implication analysis, such that when we cannot match records by comparing attributes that contain errors, we may still find matches by using other, more reliable attributes. (d) We provide an O ( n 2 ) time algorithm for inferring MDs, and an effective algorithm for deducing a set of RCKs from MDs. (e) We experimentally verify that the algorithms help matching tools efficiently identify keys at compile time for matching, blocking or windowing, and that the techniques effectively improve both the quality and efficiency of various record matching methods.

Data approximation is a popular means to support energy-efficient query processing in sensor networks. Conventional data approximation methods require users to specify fixed error bounds a prior to address the trade-off between result accuracy and energy efficiency of queries. We argue that this can be infeasible and inefficient when, as in many real-world scenarios, users are unable to determine in advance what error bounds can lead to affordable cost in query processing. We envision ε- approximate querying (EAQ) to bridge the gap. EAQ is a uniform data access scheme underlying various queries in sensor networks. It allows users or query executors to incrementally 'refine' previously obtained approximate data to reach arbitrary accuracy. EAQ not only grants more flexibility to in-network query processing, but also minimizes energy consumption through communicating data upto a just-sufficient level. To enable the EAQ scheme, we propose a novel data shuffling algorithm. The algorithm converts sensed datasets into special representations called multi-version array (MVA) . From prefixes of MVA , we can recover approximate versions of the entire dataset, where all individual data items have guaranteed error bounds. The EAQ scheme supports efficient and flexible processing of various queries including spatial window query, value range query, and queries with QoS constraints. The effectiveness and efficiency of the EAQ scheme are evaluated in a real sensor network testbed.

In many applications, transaction data arrive in the form of high speed data streams. These data contain a lot of information about customers, not just transactions, and thus have to be carefully managed to protect customers' privacy. This paper presents a novel method called SKY (Stream K-anonYmity) to continuously facilitate k-anonymity on data streams. Experimental results show that SKY is efficient and effective.

Several efficient frequent subgraph mining algorithms have been recently proposed. However, the number of frequent graph patterns generated by these graph mining algorithms may be too large to be effectively explored by users, especially when the support threshold is low. In this paper, we propose to summarize frequent graph patterns by a much smaller number of representative graph patterns. Several novel concepts such as delta-covergraph,jumpvalueanddelta-jumppatternare proposed for efficiently summarizing frequent graph patterns. Based on the fact that all delta-jumppatternsmust be representative graph patterns, we propose two efficient algorithms for summarizing frequent graph patterns, RP-FP and RP-GD. The RP-FP algorithm computes representative graph patterns from a set of closed frequent graph patterns, whereas the RP-GD algorithm directly mines representative graph patterns from graph databases. Experimental results show that RP-FP and RP-GD are able to obtain compact summarization in both real and synthetic graph databases. When the number of closed graph patterns is very large, RP-GD is much more efficient than RP-FP, while achieving comparable summarization quality.

Structured peer-to-peer (P2P) overlays have been successfully employed in many applications to locate content. However, they have been less effective in handling massive amounts of data because of the high overhead of maintaining indexes. In this paper, we propose PISCES, a Peer-based system that Indexes Selected Content for Efficient Search. Unlike traditional approaches that index all data, PISCES identifies a subset of tuples to index based on some criteria (such as query frequency, update frequency, index cost, etc.). In addition, a coarse-grained range index is built to facilitate the processing of queries that cannot be fully answered by the tuple-level index. More importantly, PISCES can adaptively self-tune to optimize the subset of tuples to be indexed. That is, the (partial) index in PISCES is built in a Just-In-Time (JIT) manner. Beneficial tuples for current users are pulled for indexing while indexed tuples with infrequent access and high maintenance cost are discarded. We also introduce a light-weight monitoring scheme for structured networks to collect the necessary statistics. We have conducted an extensive experimental study on PlanetLab to illustrate the feasibility, practicality and efficiency of PISCES. The results show that PISCES incurs lower maintenance cost and offers better search and query efficiency compared to existing methods.

When XML documents are modeled as graphs, many research issues arise. In particular, there are many new challenges in query processing on graph-structured XML documents because traditional query processing techniques for tree-structured XML documents cannot be directly applied. This paper studies the problem of structural queries on graph-structured XML documents. A hash-based structural join algorithm, HGJoin, is first proposed to handle reachability queries on graph-structured XML documents. Then, it is extended to the algorithms to process structural queries in form of bipartite graphs. Finally, based on these algorithms, a strategy to process subgraph queries in form of general DAGs is proposed. Analysis and experiments show that all the algorithms have high performance. It is notable that all the algorithms above can be slightly modified to process structural queries in form of general graphs.

This paper introduces a fast data dissemination method for structured peer-to-peer networks. The work is motivated on one side by the increase in non-volatile memory available on mobile devices and, on the other side, by observed behavioral patterns of the users. We envision a scenario where users come together for short periods of time (e.g. public transport, conference sessions) and wish to be able to share large collections of data. With hundreds and even thousands of data, items stored on small devices, content publication is simply too energy and time consuming. By indexing summary information obtained by a combination of multi-resolution analysis and k-means, our method (Hyper-Ad) is able to cut down the overall construction time of an overlay network such as CAN by an order of magnitude, as well as provide fast approximate similarity search on such a network. The results of our extensive experimental studies confirm that Hyper-M is both energy and time efficient, and provides good precision and recall.

This paper describes a PC-cluster based parallel DBMS, InfiniteDB, developed by the authors. InfiniteDB aims at efficiently storing and processing of massive databases in response to the rapidly growing in database size and the need of high performance analyzing of massive databases. It supports the parallelisms of intra-query, inter-query, intra-operation, inter-operation and pipelining. It provides effective strategies for processing massive databases including the multiple data declustering methods, the declustering-aware algorithms for the execution of relational operations and other database operations, and the adaptive query optimization method. It also provides the functions of parallel data warehousing and data mining, the coordinator-wrapper mechanism to support the integration of heterogeneous information resources on the Internet, and the fault tolerant and resilient infrastructures. It has been used in many applications and has proved quite effective for storing and processing massive databases in practice.

This paper focuses on multi-way sliding window join (SWJoin) processing over distributed data streams. A novel Join algorithm is proposed based on two distributed data stream transfer models. To reduce the communication cost and lighten the workload on the central processor node, the algorithm filters out tuples that can’t contribute to multiway SWJoin results by transforming the join conditions of SWJoin into filtering conditions during data stream transfer. Furthermore, the algorithm guarantees that all necessary data for generating exact multi-way SWJoin results can be transmitted to the central processor node.

Data compression is an effective technique to improve the performance of data warehouses. Since cube operation represents the core of online analytical processing in data warehouses, it is a major challenge to develop efficient algorithms for computing cube on compressed data warehouses. To our knowledge, very few cube computation techniques have been proposed for compressed data warehouses to date in the literature. This paper presents a novel algorithm to compute cubes on compressed data warehouses. The algorithm operates directly on compressed data sets without the need of first decompressing them. The algorithm is applicable to a large class of mapping complete data compression methods. The complexity of the algorithm is analyzed in detail. The analytical and experimental results show that the algorithm is more efficient than all other existing cube algorithms. In addition, a heuristic algorithm to generate an optimal plan for computing cube is also proposed.

Aggregation and cube are important operations for online analytical processing (OLAP). Many efficient algorithms to compute aggregation and cube for relational OLAP have been developed. Some work has been done on efficiently computing cube for multidimensional data warehouses that store data sets in multidimensional arrays rather than in tables. However, to our knowledge, there is nothing to date in the literature describing aggregation algorithms on compressed data warehouses for multidimensional OLAP. This paper presents a set of aggregation algorithms on compressed data warehouses for multidimensional OLAP. These algorithms operate directly on compressed data sets, which are compressed by the mapping-complete compression methods, without the need to first decompress them. The algorithms have different performance behaviors as a function of the data set parameters, sizes of outputs and main memory availability. The algorithms are described and the I/O and CPU cost functions are presented in this paper. A decision procedure to select the most efficient algorithm for a given aggregation request is also proposed. The analysis and experimental results show that the algorithms have better performance on sparse data than the previous aggregation algorithms.

The paper describes three fast loading algorithms for grid files on a parallel shared nothing architecture. The algorithms use dynamic programming and sampling to effectively partition the data file among the processors to achieve maximum parallelism in answering range queries. Each processor then constructs in parallel its own portion of the grid file. Analytical results and simulations are given for the three algorithms.