Graph Edit Distance (GED) is a widely used measure of graph similarity, valued for its flexibility in encoding domain knowledge through operation costs. However, existing learning-based approximation methods follow a modeling paradigm that decouples local candidate match selection from both operation costs and global dependencies between matches. This decoupling undermines their ability to capture the intrinsic flexibility of GED and often forces them to rely on costly iterative refinement to obtain accurate alignments. In this work, we revisit the formulation of GED and revise the prevailing paradigm, and propose Graph Edit Network (GEN), an implementation of the revised formulation that tightly integrates cost-aware expense estimation with globally guided one-step alignment. Specifically, GEN incorporates operation costs into node matching expenses estimation, ensuring match decisions respect the specified cost setting. Furthermore, GEN models match dependencies within and across graphs, capturing each match's impact on the overall alignment. These designs enable accurate GED approximation without iterative refinement. Extensive experiments on real-world and synthetic benchmarks demonstrate that GEN achieves up to a 37.8% reduction in GED predictive errors, while increasing inference throughput by up to 414x. These results highlight GEN's practical efficiency and the effectiveness of the revision. Beyond this implementation, our revision provides a principled framework for advancing learning-based GED approximation.

Influence maximization (IM) aims to select a small set of seed nodes whose activation triggers a maximal cascade. Existing methods typically assume access to the network topology or a reliable surrogate, which is often unavailable in practice due to noisy, privacy-protected, or partially observed links. These settings pose two challenges: (1) the lack of explicit topology removes a key inductive constraint for diffusion modeling, undermining influence estimation, and (2) nonlinear, temporally dependent node interactions yield complex multivariate time series that hinder topology inference. We propose DynaFLUX, an end-to-end generative framework for IM under hidden topology. DynaFLUX learns a compact surrogate of latent dynamics directly from observed time series, and jointly optimizes a seed-selection policy via reinforcement learning. A self-attention pointer network captures long-range dependencies for seed generation, while an influence-prediction module infers a surrogate topology and uses Monte Carlo diffusion to provide policy-gradient rewards. Experiments show that DynaFLUX accurately identifies influential spreaders and consistently outperforms state-of-the-art baselines in unseen topology scenarios.

Event reasoning is to reason with events and certain inter-event relations. These cutting-edge techniques possess crucial and fundamental capabilities that underlie various applications. Large language models (LLMs) have made advances in event reasoning owing to their wealth of training. However, the LLMs commonly used today still do not consistently demonstrate proficiency in managing event reasoning as humans. This discrepancy arises from not explicitly modeling events and their relations and insufficient knowledge of event relations. In addition, the different reasoning paradigms of the LLMs are trained in an imbalanced way. In this paper, we propose WIZARDEVENT, to synthesize data from the unlabeled corpus with the proposed hybrid event-aware instruction tuning. Specifically, we first represent the events and their relation in a novel structure and then extract the knowledge from the raw text. Second, we introduce hybrid event reasoning paradigms with four reasoning formats. Lastly, we wrap our constructed WIZARDEVENT with the paradigms to create the instruction tuning dataset. We fine-tune the model with this enriched dataset, significantly improving the event reasoning. The performance of WIZARDEVENT is rigorously evaluated through extensive experiments. The results demonstrate that WIZARDEVENT substantially outperforms baselines, indicating the effectiveness of our approach.

Pre-trained language models have made significant advancements in text generation tasks. Nevertheless, evaluating the generated text with automatic metrics is still challenging. Compared with supervised metrics, unsupervised metrics which are known for generality and robustness, are frequently employed to assess the quality of generated text efficiently. The representative unsupervised metric BERTScore uses pretrained embedding to calculate the word-to-word similarity across all tokens as evaluation scores, which can introduce potential noise due to the inclusion of tokens that do not contribute significantly to the semantics of the text. Furthermore, its heavy reliance on dense embeddings may lead to lower accuracy when evaluating text outside the common contexts represented in the training data, making it less effective in handling uncommon linguistic patterns Additionally, BERTScore treats all tokens with equal importance and lacks the ability to perform meaningful contextual expansion, which can result in less accurate similarity measurements, particularly when dealing with paraphrased or semantically rich text. To address this problem, we propose an unsupervised automatic evaluation metric inspired by the concept of lexical match in information retrieval. Our method leverages contextualized lexical matching to measure exact matches between identical tokens and dynamically matches different tokens based on their contextualized representations. Experiments on SummEval and Topical-Chat demonstrate our proposed RetriEVAL can correlate better with human judgments than previous unsupervised metrics.

Semi-supervised anomaly detection (AD) has garnered growing attention due to its ability to effectively leverage limited labeled data to identify anomalies. However, current methods often impose artificial constraints on the proportion of unlabeled anomalies in the training set, thereby impeding the effective training of models for anomaly detection in real-world scenarios where several anomalies may be present in the unlabeled dataset. Additionally, existing methods often struggle to effectively exploit and model the complex relationships between data instances, which is critical for learning more discriminative features and accurate distance measures. Distance-based methods, in particular, typically rely on Euclidean distance metric, which lacks the flexibility to capture complex correlations across different data dimensions. To address the above challenges, we propose CAD, a denoising-aware Contrastive distance learning framework for semi-supervised AD. It introduces a contrastive training objective to facilitate the learning of distinctive representations by contrasting the average distance between anomalies and unlabeled samples. To fully exploit the information from the unlabeled data meanwhile mitigate the effects of noise, we incorporate a two-stage anomaly denoising and expansion strategy to refine the dataset by identifying high-confidence samples from the unlabeled set. Furthermore, we employ a parameterized bilinear tensor distance layer to learn a customized distance metric, enabling the model to capture intricate relationships among data points. Extensive experiments on 10 real-world datasets demonstrate that CAD significantly outperforms existing semi-supervised AD models. Code available at https://github.com/CADrepo/CAD.

This paper studies the discovery of relaxed functional dependencies (RFDs). We consider RFDs that relax restrictions in both value equality and constraint satisfaction: treating values as equal if their distance is less than a given similarity threshold, and considering RFDs with violations below a given error threshold as valid. As a highly non-trivial extension of the row-based approach to functional dependency (FD) discovery, we present the first algorithm capable of discovering all valid and minimal RFDs. We extend the structure called "difference-set" for predicates that are combinations of attributes and similarity thresholds. We present an efficient method for difference-set construction, incorporating optimizations for both time and space complexity. When inferring RFDs from difference-sets, we enumerate RFDs based on the subsumption relationship of their right-hand-side predicates to share computations. An extensive experimental evaluation verifies that the proposed discovery algorithm is faster than baseline methods up to orders of magnitude and effective in finding hidden FDs from dirty data.

Network motifs provide a deep insight into the network functional abilities, and have proven useful in various practical applications. Existing studies reveal that different definitions of motifs may be needed for different temporal networks. In this study, we focus on a class of temporal networks such that the nodes and edges keep fixed, but the edge labels vary regularly with timestamps. First, we propose a proper definition of temporal motifs, which appear continuously within sufficiently large time intervals, to properly reinterpret the recurrent and statistically significant nature of motifs in temporal networks. Second, we develop a low polynomial time solution to find temporal motifs for all possible time intervals with the top to bottom and right to left scheme, based on the analyses of the properties for temporal motifs. Third, we develop a theoretically faster incremental solution to efficiently find temporal motifs to support continuously updates of temporal networks, by identifying unaffected time intervals and unnecessary edges. Finally, we have conducted extensive experiments to verify the efficiency and usefulness of our static and incremental solutions.

3D spatial data management is increasingly vital across various application scenarios, such as GIS, digital twins, human atlases, and tissue imaging. However, the inherent complexity of 3D spatial data, primarily represented by 3D geometries in real-world applications, hinders the efficient evaluation of spatial relationships through resource-intensive geometric computations. Geometric simplification algorithms have been developed to reduce the complexity of 3D representations, albeit at the cost of querying accuracy. Previous work has aimed to address precision loss by leveraging the spatial relationship between the simplified and original 3D object representations. However, this approach relied on specialized geometric simplification algorithms tailored to regions with specific criteria. In this paper, we introduce a novel approach to achieve highly efficient and accurate 3D spatial queries, incorporating geometric computation and simplification. We present a generalized progressive refinement methodology applicable to general geometric simplification algorithms, involving accurate querying of 3D geometry data using low-resolution representations and simplification extents quantified using Hausdorff distances at the facet level. Additionally, we propose techniques for calculating and storing Hausdorff distances efficiently. Extensive experimental evaluations validate the effectiveness of the proposed method which outperforms state-of-the-art systems by a factor of 4 while minimizing computational and storage overhead.

Order dependencies (ODs) state ordering specifications between attributes, and have been proven effective in query optimization for sorting operations. In this paper we investigate the problem of set-based OD discovery, for automatically finding hidden ODs from data. We tackle the problem with a novel level-wise hybrid strategy. With a given relational instance r, we discover ODs from a sample (subset) of r, validate the discovered ODs on r and refine the sample by leveraging the validation, in a level-by-level manner according to the lattice of set-based ODs. This process continues until the discovery result on the sample converges to that on r. We prove that a dynamic sample whose size keeps growing can be used in the process without affecting the correctness and completeness of the discovery result, and present techniques to incrementally refine the sample on demand. We also enhance our method with multi-threaded parallelism. On a host of datasets, our method is faster than the state-of-the-art method up to orders of magnitude even when the parallelism of our approach is disabled, and achieves up to a 4.5x self-relative parallel speedup with 6 threads.

Differential dependencies (DDs) are proposed to specify constraints on the differences between values, where the semantics of difference can be "similar", "dissimilar" and beyond. DDs subsume functional dependencies (FDs), and find valuable applications in tasks such as violation detection, duplicate identification, and quantitative data cleaning, among others. In this paper we present an efficient DD discovery method for finding hidden DDs from data. We encode differences between values in a novel structure called the "diff-set", and present a set of techniques for constructing the diff-set, discovering valid DDs with set cover enumeration of the diff-set, and eliminating non-minimal DDs. Our extensive experimental evaluation verifies that our method outperforms the existing DD discovery method up to orders of magnitude. Furthermore, our method is adapted to discover an important subclass of DDs, known as relaxed FDs (RFDs), and is also up to orders of magnitude faster than the state-of-the-art RFD discovery method.

Inclusion dependencies (INDs) are widely used in data management tasks. The discovery techniques of INDs have thus received a lot of attention, for discovering INDs valid in data. However, real-world data quality issues may lead to partial violations of INDs. This paper makes the first effort to provide a comprehensive study on the discovery of approximate INDs (AINDs), aiming to identify INDs with error rates below a given threshold. This paper introduces a new definition of AIND based on deletion semantics, in addition to the existing definition based on insertion semantics. A discovery method is developed that can be configured to identify AINDs based on either of these semantics. The method combines partitioning techniques to handle tables that cannot all fit into memory simultaneously, with novel approaches to quantify AIND violations based on partitioned tables. To improve efficiency, the method employs a novel three-layer filtering structure and techniques that can potentially prune invalid candidate AINDs and identify valid AINDs without necessarily processing all tuples. We conduct an extensive experimental evaluation and verify the following: the proposed method significantly outperforms existing methods for AIND discovery based on insertion semantics, the AIND discoveries with insertion and deletion semantics can provide complementary results, and our discovery method can effectively deal with dirty dataset containing various types of errors.

Graph Edit Distance (GED) is a general and domain-agnostic metric to measure graph similarity, widely used in graph search or retrieving tasks. However, the exact GED computation is known to be NP-complete. For instance, the widely used A* algorithms explore the entire search space to find the optimal solution which inevitably suffers scalability issues. Learning-based methods apply graph representation techniques to learn the GED by formulating a regression task, which can not recover the edit path and lead to inaccurate GED approximation (i.e., the predicted GED is smaller than the exact). To this end, in this work, we present a data-driven hybrid approach MATA* for approximate GED computation based on Graph Neural Networks (GNNs) and A* algorithms, which models from the perspective of learning to match nodes instead of directly regressing GED. Specifically, aware of the structure-dominant operations (i.e., node and edge insertion/deletion) property in GED computation, a structure-enhanced GNN is firstly designed to jointly learn local and high-order structural information for node embeddings for node matchings. Second, top-k candidate nodes are produced via a differentiable top-k operation to enable the training for node matchings, which is adhering to another property of GED, i.e., multiple optimal node matchings. Third, benefiting from the candidate nodes, MATA* only performs on the promising search directions, reaching the solution efficiently. Finally, extensive experiments show the superiority of MATA* as it significantly outperforms the combinatorial search-based, learning-based and hybrid methods and scales well to large-size graphs.

In a permissioned blockchain, performance dictates its development, which is substantially influenced by its parameters. However, research on auto-tuning for better performance has somewhat stagnated because of the difficulty posed by distributed parameters; thus, it is possible only with difficulty to propose an effective auto-tuning optimization scheme. To alleviate this issue, we lay a solid basis for our research by first exploring the relationship between parameters and performance in Hyperledger Fabric, a permissioned blockchain, and we propose Athena, a Fabric-based auto-tuning system that can automatically provide parameter configurations for optimal performance. The key of Athena is designing a new Permissioned Blockchain Multi-Agent Deep Deterministic Policy Gradient (PB-MADDPG) to realize heterogeneous parameter-tuning optimization of different types of nodes in Fabric. Moreover, we select parameters with the most significant impact on accelerating recommendation. In its application to Fabric, a typical permissioned blockchain system, with 12 peers and 7 orderers, Athena achieves a throughput improvement of 470.45% and a latency reduction of 75.66% over the default configuration. Compared with the most advanced tuning schemes (CDBTune, Qtune, and ResTune), our method is competitive in terms of throughput and latency.

Analyzing the urban trajectory in cities has become an important topic in data mining. How can we model the human mobility consisting of stay and travel states from the raw trajectory data? How can we infer these mobility states from a single user’s trajectory information? How can we further generalize the mobility inference to the real-world trajectory data that span multiple users and are sparsely sampled over time? In this article, based on formal and rigid definitions of the stay/travel mobility, we propose a single trajectory inference algorithm that utilizes a generic long-tailed sparsity pattern in the large-scale trajectory data. The algorithm guarantees a 100% precision in the stay/travel inference with a provable lower bound in the recall metric. Furthermore, we design a transformer-like deep learning architecture on the problem of mobility inference from multiple sparse trajectories. Several adaptations from the standard transformer network structure are introduced, including the singleton design to avoid the negative effect of sparse labels in the decoder side, the customized space-time embedding on features of location records, and the mask apparatus at the output side for loss function correction. Evaluations on three trajectory datasets of 40 million urban users validate the performance guarantees of the proposed inference algorithm and demonstrate the superiority of our deep learning model, in comparison to sequence learning methods in the literature. On extremely sparse trajectories, the deep learning model improves from the single trajectory inference algorithm with more than two times of overall and F1 accuracy. The model also generalizes to large-scale trajectory data from different sources with good scalability.

Lexicographical order dependencies state relationships of order between lists of attributes. They naturally model the order-by clauses in SQL queries, and are proven useful in query optimizations concerning sorting. Despite their importance, order dependencies on a dataset are typically unknown and are too costly, if not impossible, to design or discover manually. Techniques for automatic order dependency discovery are recently studied. It is challenging for order dependency discovery to scale well, since it is by nature factorial in the number$m$of attributes and quadratic in the number$n$of tuples. In this article, we adopt a strategy that decouples the impact of$m$from that of$n$, and that still finds all minimal and valid lexicographical order dependencies. We present carefully designed data structures, a host of algorithms and optimizations, and an enhanced strategy combined with multithreaded parallelism, for an efficient implementation. Using a host of real-life and synthetic datasets, we experimentally verify our approach is up to orders of magnitude faster than the state-of-the-art methods, and can deliver better results with an improved definition of minimal attribute lists.

Lexicographical order dependencies (LODs) specify orders between list of attributes, and are proven useful in optimizing SQL queries with order by clauses. To discover hidden dependencies from dirty data in practice, approximate dependency discoveries are actively studied, aiming at automatically discovering dependencies that hold on data with some exceptions. In this paper we study the discovery of approximate LODs. (1) We adapt two error measures, namely$g_1$and$g_3$, to LODs. We prove their desirable properties, present efficient algorithms for computing the measures and related lower and upper bounds, and study the relationship between the two measures. (2) We present an efficient approximate LOD discovery algorithm that is well suited to the two error measures, with a set of pruning rules, optimization techniques and ranking functions. (3) We study techniques for estimating$g_1$by sampling, with high accuracy and far less time. (4) We conduct extensive experiments to verify the effectiveness and scalability of our methods, using both real-life and synthetic data.

This paper concerns the problem of network embedding (NE), whose aim is to learn a low-dimensional representation for each node in networks. We provide a new train to solve the sparsity problem where most of nodes including the new arrival nodes have little knowledge with respect to the network. A novel paradigm is proposed to integrate the multiple information from the subgraph covering the target node instead of only the target node. Particularly, to epxress the distinctive feature over the vertex domain, a probabiltiy distribution over subgraph space is constructed for each node. The distribution is more effective to express the distinctive characteristic and feature in a higher dimension compared to the latent representation vectors. One of the primary goals of this paradigm is to define the convolution operation over the distributions, which are efficient to evaluate and learn. Experiments on four real-world network datasets demonstrate that our approach significantly outperforms state-of-the-art methods, especially on the representation learning for the nodes newly joining in the network.

Functional dependencies (FDs) are widely applied in data management tasks. Since FDs on data are usually unknown, FD discovery techniques are studied for automatically finding hidden FDs from data. In this paper, we develop techniques to dynamically discover FDs in response to changes on data. Formally, given the complete set$\Sigma$of minimal and valid FDs on a relational instance$r$, we aim to find the complete set$\Sigma^{\prime}$of minimal and valid FDs on$r\oplus\Delta r$, where$\Delta r$is a set of tuple insertions and deletions. Different from the batch approaches that compute$\Sigma^{\prime}$on$r\oplus\Delta r$from scratch, our dynamic method computes$\Sigma^{\prime}$in response to$\triangle\uparrow$. by leveraging the known$\Sigma$on$r$, and avoids processing the whole of$r$for each update from$\Delta r$. We tackle dynamic FD discovery on$r\oplus\Delta r$by dynamic hitting set enumeration on the difference-set of$r\oplus\Delta r$. Specifically, (1) leveraging auxiliary structures built on$r$, we first present an efficient algorithm to update the difference-set of$r$to that of$r\oplus\Delta r$. (2) We then compute$\Sigma^{\prime}$, by recasting dynamic FD discovery as dynamic hitting set enumeration on the difference-set of$r\oplus\Delta r$and developing novel techniques for dynamic hitting set enumeration. (3) We finally experimentally verify the effectiveness and efficiency of our approaches, using real-life and synthetic data. The results show that our dynamic FD discovery method outperforms the batch counterparts on most tested data, even when$\Delta r$is up to 30 % of$r$.

Given a time interval and a graph where vertices exhibit a property of interest (PoI) dynamically, an interesting question is: where (i.e., which part of the graph) and when (i.e., which time sub-interval) does the PoI occur frequently? To our knowledge, no work has been done to answer this question to date. We address this issue in this paper. Specifically, given (i) a time interval composed of multiple time slots and (ii) a graph where each vertex either exhibits or does not exhibit the PoI in each time slot, our objective is to find a pair of a connected sub-graph and a time sub-interval (which we refer to as a temporal bump), such that the discrepancy between the numbers of times that vertices in this sub-graph exhibit and do not exhibit the PoI during this time sub-interval is maximized. Due to the NP-hardness of this problem, initially, we propose two approximation algorithms. The first one achieves a tight approximation guarantee, at the cost of a weak scalability to the number of time slots. The second one achieves a strong scalability to the number of time slots, at the price of a loose approximation guarantee. Then, we propose two heuristic algorithms that have no non-trivial approximation guarantee, but produce similar solutions with, and are considerably faster than, the two approximation algorithms. Experiments on real datasets show that, in comparison with baselines built using related existing techniques, our algorithms hunt bumps with significantly higher discrepancies, while scaling well to large graphs, and thus are more suitable for answering the aforementioned question.

We investigate the problem of discovering approximate denial constraints (DCs), for finding DCs that hold with some exceptions to avoid overfitting real-life dirty data and facilitate data cleaning tasks. Different methods have been proposed to address the problem, by following the same framework consisting of two phases. In the first phase a structure called evidence set is built on the given instance, and in the second phase approximate DCs are found by leveraging the evidence set. In this paper, we present novel and more efficient techniques under the same framework. (1) We optimize the evidence set construction by first building a condensed structure called clue set and then transforming the clue set to the evidence set. The clue set is more memory-efficient than the evidence set and facilitates more efficient bit operations and better cache utilization, and the transformation cost is usually trivial. We further study parallel clue set construction with multiple threads. (2) Our solution to approximate DC discovery from the evidence set is a highly non-trivial extension of the evidence inversion method for exact DC discovery. (3) Using a host of datasets, we experimentally verify our approximate DC discovery approach is on average 8.2 and 7.5 times faster than the two state-of-the-art ones that also leverage parallelism, respectively, and our methods for the two phases are up to an order of magnitude and two orders of magnitude faster than the state-of-the-art methods, respectively.

Scholar name disambiguation remains a hard and unsolved problem, which brings various troubles for bibliography data analytics. Most existing methods handle name disambiguation separately that tackles one name at a time, and neglect the fact that disambiguation of one name affects the others. Further, it is typically common that only limited information is available for bibliography data, e.g., only basic paper and citation information is available in DBLP. In this study, we propose a collective approach to name disambiguation, which takes the connection of different ambiguous names into consideration. We reformulate bibliography data as a heterogeneous multipartite network, which initially treats each author reference as a unique author entity, and disambiguation results of one name propagate to the others of the network. To further deal with the sparsity problem caused by limited available information, we also introduce word-word and venue-venue similarities, and we finally measure author similarities by assembling similarities from four perspectives. Using real-life data, we experimentally demonstrate that our approach is both effective and efficient.

Lexicographical order dependencies (ODs) specify orders between list of attributes, and are proven useful in optimizing SQL queries with order by clauses. To find hidden ODs from dirty data in practice, in this paper we make a first effort to study the approximate OD discovery problem, aiming at automatically discovering ODs that hold on the data with some exceptions. (1) We adapt two error measures to ODs, prove their desirable properties, and present efficient algorithms for computing the measures and related lower and upper bounds. (2) We present an efficient approximate OD discovery algorithm that is well suited to the two error measures, with a set of pruning rules and optimization techniques. (3) We conduct extensive experiments to verify the effectiveness and scalability of our methods, using real-life and synthetic data.

This study investigates name disambiguation for scholarly data. We propose a collective approach, which considers the connections of different ambiguous names, such that it initially treats each author reference as a unique author entity and reformulates the bibliography data as a heterogeneous multipartite network. Disambiguation results of one author name propagate to the others in the network. To further deal with the sparsity problem caused by limited available information, we also introduce word-word and venue-venue similarities and measure author similarities by assembling similarities from multiple perspectives. Using three real-life datasets, we experimentally show that our approach is both effective and efficient.

Aggregate nearest neighbor (Ann) query in both the euclidean space and road networks has been extensively studied, and the flexible aggregate nearest neighbor (Fann) problem further generalizesAnnby introducing an extra flexibility parameter$\phi$that ranges in$(0, 1]$. In this article, we focus onFannon road networks, denoted asFann$_\mathcal {R}$, and its keyword-aware variant, denoted asKFann$_\mathcal {R}$. To solve these problems, we propose a series of universal (i.e., suitable for bothmaxandsum) algorithms, including a Dijkstra-based algorithm that enumerates$P$instead of$\phi |Q|$-combinations of$Q$, a queue-based approach that processes data points from-near-to-far, and a framework that combinesincremental euclidean restriction(IER) and$k$NN. We also propose a specific exact solution tomax-Fann$_\mathcal {R}$and a constant-factor ratio approximate solution tosum-Fann$_\mathcal {R}$. These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend this problem to top-$k$and multipleFann$_\mathcal {R}$(resp.,KFann$_\mathcal {R}$) queries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real datasets to demonstrate their superior efficiency and high quality.

Nowadays, various sensors are collecting, storing, and transmitting tremendous trajectory data, and it is well known that the storage, network bandwidth, and computing resources could be heavily wasted if raw trajectory data is directly adopted. Line simplification algorithms are effective approaches to attacking this issue by compressing a trajectory to a set of continuous line segments, and are commonly used in practice. In this article, we first classify the error bounded line simplification algorithms into different categories and review each category of algorithms. We then study the data aging problem of line simplification algorithms and distance metrics from the views of aging friendliness and aging errors. Finally, we present a systematic experimental evaluation of representative error bounded line simplification algorithms, including both compression optimal and sub-optimal methods, in terms of commonly adopted perpendicular Euclidean, synchronous Euclidean, and direction-aware distances. Using real-life trajectory datasets, we systematically evaluate and analyze the performance (compression ratio, average error, running time, aging friendliness, and query friendliness) of error bounded line simplification algorithms with respect to distance metrics, trajectory sizes, and error bounds. Our study provides a full picture of error bounded line simplification algorithms, which leads to guidelines on how to choose appropriate algorithms and distance metrics for practical applications.

Finding a team that is both competent in performing the task and compatible in working together has been extensively studied. However, most methods for team formation tend to rely on a set of skills only. In order to solve this problem, we present an efficient team formation method based on Constrained Pattern Graph (called CPG). Unlike traditional methods, our method takes into account both structure constraints and communication constraints on team members, which can better meet the requirements of users. First, a CPG preprocessing method is proposed to normalize a CPG and represent it as a CoreCPG in order to establish the basis for efficient matching. Second, a Communication Cost Index (called CCI) is constructed to speed up the matching between a CPG and its corresponding social network. Third, a CCI-based node matching algorithm is proposed to minimize the total number of intermediate results. Moreover, a set of incremental maintenance strategies for the changes of social networks are proposed. We conduct experimental studies based on two real-world social networks. The experiments demonstrate the effectiveness and the efficiency of our proposed method in comparison with traditional methods.

Scholarly search systems greatly aid the deep understanding of scholarly data and facilitate the research activities of scholars for scientific studies. Though a number of such systems have been developed, most of them either support rankings of limited search of entities or provide only basic ranking metrics. These existing systems also mainly adopt RDBMSs as their storage such that the linked feature of scholarly data is not fully exploited. In this study, we design and develop a novel scholarly search system Athena. (1) It supports four types of scholarly entity searches: articles, authors, venues and affiliations, and is equipped with five ranking metrics, including three traditional metrics and two comprehensive importance ranking metrics. (2) It also provides profiling of scholarly entities. (3) It further utilizes a graph storage to directly leverage the linked feature for speeding up the processing of complex queries. We demonstrate the advantages of Athena at scholarly search, profiling, graph storage and ranking quality.

Pointwise order dependencies (PODs) are dependencies that specify ordering semantics on attributes of tuples. POD discovery refers to the process of identifying the set Σ of valid and minimal PODs on a given data set D. In practice D is typically large and keeps changing, and it is prohibitively expensive to compute Σ from scratch every time. In this paper, we make a first effort to study the incremental POD discovery problem, aiming at computing changes ΔΣ to Σ such that Σ ⊕ ΔΣ is the set of valid and minimal PODs on D with a set Δ D of tuple insertion updates. (1) We first propose a novel indexing technique for inputs Σ and D. We give algorithms to build and choose indexes for Σ and D , and to update indexes in response to Δ D. We show that POD violations w.r.t. Σ incurred by Δ D can be efficiently identified by leveraging the proposed indexes, with a cost dependent on log (| D |). (2) We then present an effective algorithm for computing ΔΣ, based on Σ and identified violations caused by Δ D. The PODs in Σ that become invalid on D + Δ D are efficiently detected with the proposed indexes, and further new valid PODs on D + Δ D are identified by refining those invalid PODs in Σ on D + Δ D. (3) Finally, using both real-life and synthetic datasets, we experimentally show that our approach outperforms the batch approach that computes from scratch, up to orders of magnitude.

Human mobility annotation aims to assign mobility records the corresponding visiting Point-of-Interests (POIs). It is one of the most fundamental problems for understanding human mobile behaviors. In literature, many efforts have been devoted to annotating mobility records in a pointwise or trajectory-wise manner. However, the user preference factor is not fully explored and, worse still, the mobile peer influence factor has never been integrated. To this end, in this article, we propose a novel framework, named JEPPI, to jointly exploit user preference and mobile peer influence to tackle the problem. In our JEPPI, we first unify the two distinct factors in a behavior-driven user-POI graph. This graph enables us to model user preference with user-POI visiting relationships, and model two types of mobile peer influence with co-location and co-visiting peer relationships, respectively. Moreover, we devise an equivalence-emphasizing metric to reduce redundancy in the second-order co-visiting peer influence. In addition, a mutual augmentation learning approach is proposed to preserve the latent structures of various factors exploited. Notably, our learning approach preserves all factors in a shared representation space such that user preference is learned with mobile peer influence being considered at the same time, and vice versa. In this way, the different factors are mutually augmented and semantically integrated to enhance human mobility annotation. Finally, using two large-scale real-world datasets, we conduct extensive experiments to demonstrate the superiority of our approach compared with the state-of-the-art annotation methods.

With the proliferation of mobile devices and location-based services, continuous generation of massive volume of streaming spatial objects (i.e., geo-tagged data) opens up new opportunities to address real-world problems by analyzing them. In this paper, we present a novel continuous bursty region detection (SURGE) problem that aims to continuously detect a burstyregion of a given size in a specified geographical area from a stream of spatial objects. Specifically, a bursty region shows maximum spike in the number of spatial objects in a given time window. The SURGE problem is useful in addressing several real-world challenges such as surge pricing problem in online transportation and disease outbreak detection. To solve the problem, we propose an exact solution and two approximate solutions, and the approximation ratio is 1-α/4 in terms of the burst score, where α is a parameter to control the burst score. We further extend these solutions to support detection of top-k bursty regions. Extensive experiments with real-world data are conducted to demonstrate the efficiency and effectiveness of our solutions.

Dense subgraph discovery has proven useful in various applications of temporal networks. We focus on a special class of temporal networks whose nodes and edges are kept fixed, but edge weights regularly vary with timestamps. However, finding dense subgraphs in temporal networks is non-trivial, and its state of the art solution uses a filter-and-verification framework that is not scalable on large temporal networks. In this study, we propose a highly efficient approach to finding dense subgraphs in large temporal networks with T timestamps. (1) We first develop a statistics-driven approach that employs hidden statistics to identifying k time intervals, instead of T(T + 1)/2 ones (k is typically much smallerthan T), which strikes a balance between quality and efficiency. (2) After proving that the problem has no constant factor approximation algorithms, we design better heuristic algorithms to attack the problem, by connecting finding dense subgraphs with a variant of the Prize Collecting Steiner Tree problem. (3) Finally, we have conducted an extensive experimental study to verify that our approach is both effective and efficient.

Spectral clustering is one of the most popular modern clustering algorithms. It is easy to implement, can be solved efficiently, and very often outperforms other traditional clustering algorithms such as k-means. However, pectral clustering would be insufficient when dealing with most datasets which have complex statistical properties and quires the user to specify the number of clusters (called k). To address these two problems, in this paper, we propose an approach to extending spectral clustering with deep embedding and estimation of the number of clusters. Specifically, we first generate the deep embedding via learning a deep autoencoder, which transforms the raw data into the lower dimensional representations that suitable for clustering. We then provide an effective method to estimate the number of clusters by learning a softmax autoencoder from the deep embedding. We finally extend spectral clustering with the learned embedding and the estimated number. An extensive experimental study on several image and text datasets illustrates the effectiveness and efficiency of our approach.

News recommendation is an effective information dissemination solution in modern society. In general, news articles can be modeled from multiple granularities: sentence-, element-and news-level. However, the first two levels have been largely ignored in existing methods and it is also unclear how such multi-granularity modeling can enhance news recommendation. In this paper, we propose a novel dynamic model for news recommendation. A unique perspective of our model is to discriminate the contributions of previously interacted contents for triggering the next news-reading, in sentence-, element-and news-level simultaneously. To this end, we design a hierarchical attention network of which the lower layer learns the impacts of sentences and elements, while the upper layer captures disparity of news. Moreover, we incorporate a time-decaying factor to reflect the dynamism, as well as convolution neural networks for learning sequential influence. Using three real-world datasets, we conduct extensive experiments to verify the superiority of our model, compared with several state-of-the-art approaches.

Aggregate nearest neighbor (ANN) query has been studied in both the Euclidean space and road networks. The flexible aggregate nearest neighbor (FANN) problem further generalizes ANN by introducing an extra flexibility. Given a set of data points P, a set of query points Q, and a user-defined flexibility parameter φ that ranges in (0, 1], an FANN query returns the best candidate from P, which minimizes the aggregate (usually max or sum) distance to any φ |Q| objects in Q. In this paper, we focus on the problem in road networks (denoted as FANNR), and present a series of universal (i.e., suitable for both max and sum) algorithms to answer FANNRqueries in road networks, including a Dijkstra-based algorithm enumerating P, a queue-based approach that processes data points from-near-to-far, and a framework that combines Incremental Euclidean Restriction (IER) and kNN. We also propose a specific exact solution to max-FANNRand a specific approximate solution to sum-FANNRwhich can return a near-optimal result with a guaranteed constant-factor approximation. These specific algorithms are easy to implement and can achieve excellent performance in some scenarios. Besides, we further extend the FANNRto k-FANNR, and successfully adapt most of the proposed algorithms to answer k-FANNRqueries. We conduct a comprehensive experimental evaluation for the proposed algorithms on real road networks to demonstrate their superior efficiency and high quality.

With the proliferation of location-based services, the generation of massive geo-tagged data opens up new opportunities to address real-world problems. In this paper, we present a novel continuous bursty region detection (SURGE) problem that aims to continuously detect a bursty region of a given size in a specified geographical area from a stream of spatial objects. The SURGE problem is useful in addressing several real-world challenges such as disease outbreak detection. We propose an exact solution to address the problem, and show the efficiency and effectiveness by conducting experiments on real-world datasets.

Ranking query independent scholarly articles is a practical and difficult task, due to the heterogeneous, evolving and dynamic nature of entities involved in scholarly articles. To do this, we first propose a scholarly article ranking model by assembling the importance of involved entities (i.e., articles, venues and authors) such that the importance is a combination of prestige and popularity to capture the evolving nature of entities. To compute the prestige of articles and venues, we propose a novel Time-Weighted PageRank that extends traditional PageRank with a time decaying factor. We then develop a batch algorithm for scholarly article ranking, in which we propose a block-wise method for Time-Weighted PageRank in terms of an analysis of the citation characteristics of scholarly articles. We further develop an incremental algorithm for dynamic scholarly article ranking, which partitions graphs into affected and unaffected areas, and employs different updating strategies for nodes in different areas. Using real-life data, we finally conduct an extensive experimental study, and show that our approach is both effective and efficient for ranking scholarly articles.

We demonstrate a graph caching system GC for expediting subgraph/supergraph queries, which are computationally expensive due to the entailed NP-Complete subgraph isomorphism problem. Unlike existing caching systems for fast data access where each cache hit saves one disk I/O, GC reduces the computational costs due to subgraph isomorphism testing. Moreover, GC harnesses both subgraph and supergraph cache hits, extending the traditional exact-match-only hit, thus resulting in significant speedups. Furthermore, GC features dashboards for both skilled developers and general end-users; the former could investigate and experiment with alternative components/mechanisms while the latter could look into the principle of GC through a number of demonstration scenarios.

Traditional graph pattern matching is based on subgraph isomorphism, which is often too restrictive to identify meaningful matches. To handle this, taxonomy subgraph isomorphism has been proposed to relax the label constraints in the matching. Nonetheless, there are many cases that cannot be covered. In this study, we first formalize taxonomy simulation, a natural matching semantics combing graph simulation with taxonomy, and propose its pattern relaxation to enrich graph pattern matching results with taxonomy information. We also design topological ranking and diversified topological ranking for top-k relaxations. We then study the top-k pattern relaxation problems, by providing their static analyses, and developing algorithms and optimization for finding and evaluating top-k pattern relaxations. We further propose a notion of explanations for answers to the relaxations and develop algorithms to compute explanations. These together give us a framework for enriching the results of graph pattern matching. Using real-life datasets, we experimentally verify that our framework and techniques are effective and efficient for identifying meaningful matches in practice.

In sparse data, a large fraction of the entries take on zero values. Some examples of sparse data include short text snippets (such as tweets in Twitter) or some feature representations of categorical data sets with a large number of values, in which traditional methods for outlier detection typically fail because of the difficulty of computing distances. To address this, it is important to use the latent relations between such values. Factorization machines represent a natural methodology for this, and are naturally designed for the massive-domain setting because of their emphasis on sparse data sets. In this study, we propose an outlier detection approach for sparse data with factorization machines. Factorization machines are also efficient due to their linear complexity in the number of non-zero values. In fact, because of their efficiency, they can even be extended to traditional settings for numerical data by an appropriate feature engineering effort. We show that our approach is both effective and efficient for sparse categorical, short text and numerical data by an extensive experimental study.

This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

Dense subgraph discovery has proven useful in various applications of temporal networks. We focus on a special class of temporal networks whose nodes and edges are kept fixed, but edge weights constantly and regularly vary with timestamps. However, finding dense subgraphs in temporal networks is nontrivial, and its state of the art solution uses a filter-and-verification framework, which is not scalable on large temporal networks. In this study, we propose a data-driven approach to finding dense subgraphs in large temporal networks with T timestamps. (1) We first develop a data-driven approach employing hidden statistics to identifying k time intervals, instead of T*(T + 1)/2 ones (k is typically much smaller than T), which strikes a balance between quality and efficiency. (2) After proving that the problem has no constant factor approximation algorithms, we design better heuristic algorithms to attack the problem, by building the connection of finding dense subgraphs with a variant of the Prize Collecting Steiner Tree problem. (3) Finally, we have conducted an extensive experimental study to demonstrate the effectiveness and efficiency of our approach, using real-life and synthetic data.

Nowadays, various sensors are collecting, storing and transmitting tremendous trajectory data, and it is known that raw trajectory data seriously wastes the storage, network band and computing resource. Line simplification (LS) algorithms are an effective approach to attacking this issue by compressing data points in a trajectory to a set of continuous line segments, and are commonly used in practice. However, existing LS algorithms are not sufficient for the needs of sensors in mobile devices. In this study, we first develop a one-pass error bounded trajectory simplification algorithm (OPERB), which scans each data point in a trajectory once and only once. We then propose an aggressive one-pass error bounded trajectory simplification algorithm (OPERB-A), which allows interpolating new data points into a trajectory under certain conditions. Finally, we experimentally verify that our approaches (OPERB and OPERB-A) are both efficient and effective, using four real-life trajectory datasets.

A network with n nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Further, even though link prediction is closely related to missing value estimation problems, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity on large networks. Hence, most known link prediction methods are designed for evaluating the link propensity on a specified subset of links, rather than on the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this article, we propose an ensemble enabled approach to scaling up link prediction, by decomposing traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with latent factor models, which can be effectively implemented on networks of modest size. By incorporating with the characteristics of link prediction, the ensemble approach further reduces the sizes of subproblems without sacrificing its prediction accuracy. The ensemble enabled approach has several advantages in terms of performance, and our experimental results demonstrate the effectiveness and scalability of our approach.

Temporal graphs are a class of graphs whose nodes and edges, together with the associated properties, continuously change over time. Recently, systems have been developed to support snapshot queries over temporal graphs. However, these systems barely support aggregate time range queries. Moreover, these systems cannot guarantee ACID transactions, an important feature for data management systems as long as concurrent processing is involved. To solve these issues, we design and develop TGraph, a temporal graph data management system, that assures the ACID transaction feature, and supports fast temporal graph queries.

Network anomaly detection has become very popular in recent years because of the importance of discovering key regions of structural inconsistency in the network. In addition to application-specific information carried by anomalies, the presence of such structural inconsistency is often an impediment to the effective application of data mining algorithms such as community detection and classification. In this paper, we study the problem of detecting structurally inconsistent nodes that connect to a number of diverse influential communities in large social networks. We show that the use of a network embedding approach, together with a novel dimension reduction technique, is an effective tool to discover such structural inconsistencies. We also experimentally show that the detection of such anomalous nodes has significant applications: one is the specific use of detected anomalies, and the other is the improvement of the effectiveness of community detection.

Summarizing large influence graphs is crucial for many graph visualization and mining tasks. Classical graph clustering and compression algorithms focus on summarizing the nodes by their structural-level or attribute-level similarities, but usually are not designed to characterize the flow-level pattern which is the centerpiece of influence graphs. On the other hand, the social influence analysis has been intensively studied, but little is done on the summarization problem without an explicit focus on social networks. Building on the recent study of the Influence Graph Summarization (IGS), this paper presents a new perspective of the underlying flow-based heuristic. It establishes a direct linkage between the optimal summarization and the classic eigenvector centrality of the graph nodes. Such a theoretic linkage has important implications on numerous aspects in the pursuit of a perfect influence graph summarization. In particular, it enables us to develop a suite of algorithms that can: 1) achieve a near-optimal IGS objective, 2) support dynamic summarizations balancing the IGS objective and the stability of transition in navigating the summarization, and 3) scale to million-node graphs with a near-linear computational complexity. Both quantitative experiments on real-world citation networks and the user studies on the task analysis experience demonstrate the effectiveness of the proposed summarization algorithms.

A network with $n$ nodes contains O(n2) possible links. Even for networks of modest size, it is often difficult to evaluate all pairwise possibilities for links in a meaningful way. Furthermore, even though link prediction is closely related to missing value estimation problems, such as collaborative filtering, it is often difficult to use sophisticated models such as latent factor methods because of their computational complexity over very large networks. Due to this computational complexity, most known link prediction methods are designed for evaluating the link propensity over a specified subset of links, rather than for performing a global search over the entire networks. In practice, however, it is essential to perform an exhaustive search over the entire networks. In this paper, we propose an ensemble enabled approach to scaling up link prediction, which is able to decompose traditional link prediction problems into subproblems of smaller size. These subproblems are each solved with the use of latent factor models, which can be effectively implemented over networks of modest size. Furthermore, the ensemble enabled approach has several advantages in terms of performance. We show the advantage of using ensemble-based latent factor models with experiments on very large networks. Experimental results demonstrate the effectiveness and scalability of our approach.

Computing shortest paths and distances is one of the fundamental problems on graphs, and it remains a challenging task today. This article investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. To do this, we propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We first show that routing proxies hold good properties for speeding-up shortest path and distance queries. Then, we design a linear-time algorithm to compute routing proxies and their corresponding DRAs. Finally, we experimentally verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

This paper proposes a natural extension of conditional functional dependencies (CFDs [1]) and conditional inclusion dependencies (CINDs [2]), denoted by CFDps and CINDps, respectively, by specifying patterns of data values with 6 ≠,, and ≥ predicates. As data quality rules, CFDps and CINDps are able to capture errors that commonly arise in practice but cannot be detected by CFDs and CINDs. We establish two sets of results for central technical problems associated with CFDps and CINDps. (a) One concerns the satisfiability and implication problems for CFDps and CINDps, taken separately or together. These are important for, e.g. deciding whether data quality rules are dirty themselves, and for removing redundant rules. We show that despite the increased expressive power, the static analyses of CFDps and CINDps retain the same complexity as their CFDs and CINDs counterparts. (b) The other concerns validation of CFDps and CINDps. We show that given a set X of CFDps and CINDps on a database D, a set of SQL queries can be automatically generated that, when evaluated against D, return all tuples in D that violate some dependencies in Σ. We also experimentally verified the efficiency and effectiveness of our SQL based error detection techniques, using real-life data. This provides commercial DBMS with an immediate capability to detect errors based on CFDps and CINDps.

Recently, with the emergence of event-based online social services(e.g. Meetup), there have been increasing online activities to create, distribute, and organize social events. In this paper, we take the first systematic step to discover influential event organizers from online social networks who are essential to the overall success of social events. Informally, such event organizers comprise a small group of people who not only have the relevant skills or expertise that are required for an event (e.g. conference) but they are also able to influence largest number of people to actively contribute to it. We formulate it as the problem of mining influential cover set (ICS) where we wish to find k users in a social network G that together have the required skills or expertise (modeled as attributes of nodes in G) to organize an event such that they can influence the greatest number of individuals to participate in the event. The problem is, however, NP-hard. Hence, we propose three algorithms to find approximate solutions to the problem. The first two algorithms are greedy; they run faster, but have no guarantees. The third algorithm is 2-approximate and guarantees to find a feasible solution if any. Our empirical study over several real-world networks demonstrates the superiority of our proposed solutions.

Graph pattern matching is finding all matches in a data graph for a given pattern graph and is often defined in terms of subgraph isomorphism, an NP -complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow graph pattern matching to be conducted in cubic time. However, they fall short of capturing the topology of data graphs, that is, graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this article proposes a notion of strong simulation , a revision of graph simulation for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of graph simulation by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation which allows us to develop an effective distributed algorithm to conduct graph pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms using both real-life and synthetic data.

There have been recently quite a few works on optimizing the MapReduce execution plans, which either optimize the join operators or apply a set of translation rules to reduce the number of MapReduce jobs in an execution plan. However, none of these works has put into consideration and utilized how MapReduce jobs are generated and combined. To further improve the efficiency of MapReduce execution plans, we incorporate into our optimization approach the way how MapReduce jobs are generated and combined. In this paper, we propose MRPacker, a novel SQL-to-MapReduce optimizer by (a) using a set of transformation rules to reduce the number of MapReduce jobs, and (b) merging MapReduce jobs in a more reasonable way. We have finally experimentally demonstrated the effectiveness and efficiency of MRPacker, using the TPC-H benchmark.

Network streams have become ubiquitous in recent years because of many dynamic applications. Such streams may show localized regions of activity and evolution because of anomalous events. This paper will present methods for dynamically determining anomalous hot spots from network streams. These are localized regions of sudden activity or change in the underlying network. We will design a localized principal component analysis algorithm, which can continuously maintain the information about the changes in the different neighborhoods of the network. We will use a fast incremental eigenvector update algorithm based on von Mises iterations in a lazy way in order to efficiently maintain local correlation information. This is used to discover local change hotspots in dynamic streams. We will finally present an experimental study to demonstrate the effectiveness and efficiency of our approach.

Graph simulation has been adopted for pattern matching to reduce the complexity and capture the need of novel applications. With the rapid development of the Web and social networks, data is typically distributed over multiple machines. Hence a natural question raised is how to evaluate graph simulation on distributed data. To our knowledge, no such distributed algorithms are in place yet. This paper settles this question by providing evaluation algorithms and optimizations for graph simulation in a distributed setting. (1) We study the impacts of components and data locality on the evaluation of graph simulation. (2) We give an analysis of a large class of distributed algorithms, captured by a message-passing model, for graph simulation. We also identify three complexity measures: visit times, makespan and data shipment, for analyzing the distributed algorithms, and show that these measures are essentially controversial with each other. (3) We propose distributed algorithms and optimization techniques that exploit the properties of graph simulation and the analyses of distributed algorithms. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using both real-life and synthetic data.

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.

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.

Graph pattern matching is often defined in terms of subgraph isomorphism, an np-complete problem. To lower its complexity, various extensions of graph simulation have been considered instead. These extensions allow pattern matching to be conducted in cubic-time. However, they fall short of capturing the topology of data graphs, i.e. , graphs may have a structure drastically different from pattern graphs they match, and the matches found are often too large to understand and analyze. To rectify these problems, this paper proposes a notion of strong simulation , a revision of graph simulation, for graph pattern matching. (1) We identify a set of criteria for preserving the topology of graphs matched. We show that strong simulation preserves the topology of data graphs and finds a bounded number of matches. (2) We show that strong simulation retains the same complexity as earlier extensions of simulation, by providing a cubic-time algorithm for computing strong simulation. (3) We present the locality property of strong simulation, which allows us to effectively conduct pattern matching on distributed graphs. (4) We experimentally verify the effectiveness and efficiency of these algorithms, using real-life data and synthetic data.

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.

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.

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.

The paper proposes an extension of CFDs [1], referred to as extended Conditional Functional Dependencies (eCFDs). In contrast to CFDs, eCFDs specify patterns of semantically related values in terms of disjunction and inequality, and are capable of catching inconsistencies that arise in practice but cannot be detected by CFDs. The increase in expressive power does not incur extra complexity: we show that the satisfiability and implication analyses of eCFDs remain NP - complete and coNP -complete, respectively, the same as their CFDs counterparts. In light of the intractability, we present an algorithm that approximates the maximum number of eCFDs that are satisfiable. In addition, we revise SQL techniques for detecting CFD violations, and show that violations of multiple eCFDs can be captured via a single pair of SQL queries. We also introduce an incremental SQL technique for detecting eCFD violations in response to database updates. We experimentally verify the effectiveness and efficiency of our SQL -based detection methods.

The dependency propagation problem is to determine, given a view defined on data sources and a set of dependencies on the sources, whether another dependency is guaranteed to hold on the view. This paper investigates dependency propagation for recently proposed conditional functional dependencies (CFDs). The need for this study is evident in data integration, exchange and cleaning since dependencies on data sources often only hold conditionally on the view. We investigate dependency propagation for views defined in various fragments of relational algebra, CFDs as view dependencies, and for source dependencies given as either CFDs or traditional functional dependencies (FDs). (a) We establish lower and upper bounds, all matching , ranging from PTIME to undecidable. These not only provide the first results for CFD propagation, but also extend the classical work of FD propagation by giving new complexity bounds in the presence of finite domains. (b) We provide the first algorithm for computing a minimal cover of all CFDs propagated via SPC views; the algorithm has the same complexity as one of the most efficient algorithms for computing a cover of FDs propagated via a projection view, despite the increased expressive power of CFDs and SPC views. (c) We experimentally verify that the algorithm is efficient.