Graph Neural Networks (GNNs) have demonstrated strong representation learning capabilities for graph-based tasks. Recent advances on GNNs leverage geometric properties, such as curvature, to enhance their representation capabilities by modeling complex connectivity patterns and information flow within graphs. However, most existing approaches primarily focus on discrete graph topology, overlooking diffusion dynamics and task-specific dependencies essential for effective learning. To address this, we propose a learnable integration of Bakry-Émery curvature, which captures both structural and diffusion aspects of information propagation. We develop an efficient, learnable approximation strategy, making curvature computation scalable for large graphs. Furthermore, we introduce an adaptive depth mechanism that dynamically adjusts message-passing layers per vertex based on its curvature, ensuring efficient propagation. Our theoretical analysis establishes a link between curvature and feature distinctiveness, showing that high-curvature vertices require fewer layers, while low-curvature ones benefit from deeper propagation. Extensive experiments on diverse downstream tasks validate the effectiveness of our approach, showing that the proposed depth-adaptive mechanism consistently uplifts the performance of a wide range of GNN architectures.

Computing the shortest-path distance between any two given vertices in road networks is an important problem. A tremendous amount of research has been conducted to address this problem, most of which are limited to static road networks. Since road networks undergo various real-time traffic conditions, there is a pressing need to address this problem for dynamic road networks. Existing state-of-the-art methods incrementally maintain an indexing structure to reflect dynamic changes on road networks. However, these methods suffer from either slow query response time or poor maintenance performance, particularly when road networks are large. In this work, we propose an efficient solution Dual-Hierarchy Labelling (DHL) for distance querying on dynamic road networks from a novel perspective, which incorporates two hierarchies with different but complementary data structures to support efficient query and update processing. Specifically, our proposed solution is comprised of three main components: query hierarchy, update hierarchy, and hierarchical labelling, where query hierarchy enables efficient query answering by exploring only a small subset of vertices in the labels of two query vertices and update hierarchy supports efficient maintenance of distance labelling under edge weight increase or decrease. We further develop dynamic algorithms to reflect dynamic changes by efficiently maintaining the update hierarchy and hierarchical labelling. We also propose a parallel variant of our dynamic algorithms by exploiting labelling structure which aligns well with parallel processing. We evaluate our methods on 10 large road networks and it shows that our methods significantly outperform the state-of-the-art methods, i.e., achieving considerably faster construction and update time, while being consistently 2-4 times faster in terms of query processing and consuming only 10%-20% labelling space.

The shortest path counting problem is crucial for various applications in road networks, such as network robustness analysis, traffic flow distribution, and navigation optimization. Unlike traditional shortest path problems, it requires enumerating all possible shortest paths, making it computationally challenging, especially in dense urban networks with numerous equal-length paths. Existing methods, such as 2-hop labeling schemes, precompute shortest-path distances and counts for efficient queries but struggle to scale in large networks. In this work, we propose a novel divide-and-conquer approach based on recursive vertex bipartitioning to address this limitation. At its core, we establish a count reconstruction theorem that efficiently combines shortest subpath counts from smaller subgraphs to accurately reconstruct shortest path counts for the entire graph. This approach significantly reduces computational overhead and storage requirements. We also introduce a 2-hop count labeling scheme that integrates effectively with this divide-and-conquer framework. Experimental results show that our approach significantly outperforms state-of-the-art solutions, doubling query processing speed, reducing label construction time to one-fourth, and requiring only around 20% of labeling space.

Efficient route planning is crucial for modern navigation systems, yet traditional methods face challenges in scenarios with unknown or frequently changing traffic dynamics. This paper introduces a general labeling framework based on the 2-hop cover property, enabling robust, metric-independent preprocessing. Using this framework, we propose Customizable Tree Labeling (CTL), a tree-based method combining three key components: metric-independent preprocessing with tree hierarchies, metric customization for dynamic updates, and efficient query algorithms for fast route computation. To allow trade-offs between customization time, labeling size, and query performance, we further develop a parameterized customization technique by dynamically combining tree labels and shortcut graphs. Our key contributions include the introduction of a customizable labeling framework, a novel tree hierarchy for compact and scalable representation, and a hybrid query algorithm that integrates labels and shortcuts for fast and accurate route computation. We conduct extensive experiments on ten large-scale real-world road networks and a case study on the traffic assignment problem. Our algorithms achieve query response times significantly faster than the state-of-the-art methods, while maintaining competitive customization times and labeling size, making it well-suited for real-time and dynamic routing applications.

Abstract Many real-world applications operate on dynamic graphs to perform important tasks. In this article, we study batch-dynamic algorithms that are capable of updating distance labelling efficiently in order to reflect the effects of rapid changes on such graphs. To explore the full pruning potentials, we first characterize the minimal set of vertices being affected by batch updates. Then, we reveal patterns of interactions among different updates (edge insertions and edge deletions) and leverage them to design pruning rules for reducing update search space. These interesting findings lead us to developing a new batch-dynamic method, called BatchHL $$^+$$ + , which can dynamize labelling for distance queries much more efficiently than existing work. We provide formal proofs for the correctness and minimality of BatchHL $$^+$$ + which are non-trivial and require a delicate analysis of patterns of interactions. Empirically, we have evaluated the performance of BatchHL $$^+$$ + on 15 real-world networks. The results show that BatchHL $$^+$$ + significantly outperforms the state-of-the-art methods with up to 3 orders of magnitude faster in reflecting updates of rapidly changing graphs for distance queries.

Answering the shortest-path distance between two arbitrary locations is a fundamental problem in road networks. Labelling-based solutions are the current state-of-the-arts to render fast response time, which can generally be categorised into hub-based labellings, highway-based labellings, and tree decomposition labellings. Hub-based and highway-based labellings exploit hierarchical structures of road networks with the aim to reduce labelling size for improving query efficiency. However, these solutions still result in large search spaces on distance labels at query time, particularly when road networks are large. Tree decomposition labellings leverage a hierarchy of vertices to reduce search spaces over distance labels at query time, but such a hierarchy is generated using tree decomposition techniques, which may yield very large labelling sizes and slow querying. In this paper, we propose a novel solution hierarchical cut 2-hop labelling (HC2L) to address the drawbacks of the existing works. Our solution combines the benefits of hierarchical structures from both perspectives - reduce the size of a distance labelling at preprocessing time and further reduce the search space on a distance labelling at query time. At its core, we propose a new hierarchy, balanced tree hierarchy, which enables a fast, efficient data structure to reduce the size of distance labelling and to select a very small subset of labels to compute the shortest-path distance at query time. To speed up the construction process of HC2L, we further propose a parallel variant of our method, namely HC2L^p. We have evaluated our solution on 10 large real-world road networks through extensive experiments. The results show that our method is 1.5-4 times faster in terms of query processing while being comparable in terms of labelling construction time and achieving up to 60% smaller labelling size compared to the state-of-the-art approaches.

Tracing a student's knowledge is vital for tailoring the learning experience. Recent knowledge tracing methods tend to respond to these challenges by modelling knowledge state dynamics across learning concepts. However, they still suffer from several inherent challenges including: modelling forgetting behaviors and identifying relationships among latent concepts. To address these challenges, in this paper, we propose a novel knowledge tracing model, namelyDeep Graph Memory Network(DGMN). In this model, we incorporate a forget gating mechanism into an attention memory structure in order to capture forgetting behaviors dynamically during the knowledge tracing process. Particularly, this forget gating mechanism is built upon attention forgetting features over latent concepts considering their mutual dependencies. Further, this model has the capability of learning relationships between latent concepts from a dynamic latent concept graph in light of a student's evolving knowledge states. A comprehensive experimental evaluation has been conducted using four well-established benchmark datasets. The results show that DGMN consistently outperforms the state-of-the-art KT models over all the datasets. The effectiveness of modelling forgetting behaviors and learning latent concept graphs has also been analyzed in our experiments.

Many real-world applications operate on dynamic graphs that undergo rapid changes in their topological structure over time. However, it is challenging to design dynamic algorithms that are capable of supporting such graph changes efficiently. To circumvent the challenge, we propose a batch-dynamic framework for answering distance queries, which combines offline labelling and online searching to leverage the advantages from both sides - accelerating query processing through a partial distance labelling that is of limited size but provides a good approximation to bound online searches. We devise batch-dynamic algorithms to dynamize a distance labelling efficiently in order to reflect batch updates on the underlying graph. In addition to providing theoretical analysis for the correctness, labelling minimality, and computational complexity, we have conducted experiments on 14 real-world networks to empirically verify the efficiency and scalability of the proposed algorithms.

Finding the shortest path distance between an arbitrary pair of vertices is a fundamental problem in graph theory. A tremendous amount of research has been successfully attempted on this problem, most of which is limited to static graphs. Due to the dynamic nature of real-world networks, there is a pressing need to address this problem for dynamic networks undergoing changes. In this paper, we propose an online incremental method to efficiently answer distance queries over very large dynamic graphs. Our proposed method incorporates incremental update operations, i.e. edge and vertex additions, into a highly scalable framework of answering distance queries. We theoretically prove the correctness of our method and the preservation of labelling minimality. We have also conducted extensive experiments on 12 large real-world networks to empirically verify the efficiency, scalability, and robustness of our method.

We propose a learning framework for graph kernels, which is theoretically grounded on regularizing optimal transport. This framework provides a novel optimal transport distance metric, namely Regularized Wasserstein (RW) discrepancy, which can preserve both features and structure of graphs via Wasserstein distances on features and their local variations, local barycenters and global connectivity. Two strongly convex regularization terms are introduced to improve the learning ability. One is to relax an optimal alignment between graphs to be a cluster-to-cluster mapping between their locally connected vertices, thereby preserving the local clustering structure of graphs. The other is to take into account node degree distributions in order to better preserve the global structure of graphs. We also design an efficient algorithm to enable a fast approximation for solving the optimization problem. Theoretically, our framework is robust and can guarantee the convergence and numerical stability in optimization. We have empirically validated our method using 12 datasets against 16 state-of-the-art baselines. The experimental results show that our method consistently outperforms all state-of-the-art methods on all benchmark databases for both graphs with discrete attributes and graphs with continuous attributes.

Computing shortest paths is a fundamental operation in processing graph data. In many real-world applications, discovering shortest paths between two vertices empowers us to make full use of the underlying structure to understand how vertices are related in a graph, e.g. the strength of social ties between individuals in a social network. In this paper, we study the shortest-path-graph problem that aims to efficiently compute a shortest path graph containing exactly all shortest paths between any arbitrary pair of vertices on complex networks. Our goal is to design an exact solution that can scale to graphs with millions or billions of vertices and edges. To achieve high scalability, we propose a novel method, Query-by-Sketch (QbS), which efficiently leverages offline labelling (i.e., precomputed labels) to guide online searching through a fast sketching process that summarizes the important structural aspects of shortest paths in answering shortest-path-graph queries. We theoretically prove the correctness of this method and analyze its computational complexity. To empirically verify the efficiency of QbS, we conduct experiments on 12 real-world datasets, among which the largest dataset has 1.7 billion vertices and 7.8 billion edges. The experimental results show that QbS can answer shortest-path-graph queries in microseconds for million-scale graphs and less than half a second for billion-scale graphs.

Sentence representation learning is a key component in distantly supervised relation extraction. Text chunks (i.e., a group of n consecutive words) are meaningful units to understand relations. However, existing works suffer from extracting useful structural features from text chunks for relation extraction due to two challenges: (1) Prepositions often occur in text chucks but their semantics are hardly captured. (2) Chunk structures vary in different sentences with different sizes. In this paper, we propose a new model, dynamic chunkwise CNN (DCW-CNN), to tackle these challenges. We develop structural convolution to extract chunk features from sentences, and design a dynamic chunk module to dynamically determine the "most proper" chunk size for sentences of varying structures and contents. We have conducted experiments on two benchmark datasets. The experimental results show that our proposed model improves performance significantly compared with the state-of-the-art methods.

Entity resolution targets at identifying records that represent the same real-world entity from one or more datasets. A major challenge in learning-based entity resolution is how to reduce the label cost for training. Due to the quadratic nature of record pair comparison, labeling is a costly task that often requires a significant effort from human experts. Inspired by recent advances of generative adversarial network (GAN), we propose a novel deep learning method, called ErGAN, to address the challenge. ErGAN consists of two key components: a label generator and a discriminator which are optimized alternatively through adversarial learning. To alleviate the issues of overfitting and highly imbalanced distribution, we design two novel modules for diversity and propagation, which can greatly improve the model generalization power. We have conducted extensive experiments to empirically verify the labeling and learning efficiency of ErGAN. The experimental results show that ErGAN beats the state-of-the-art baselines, including unsupervised, semi-supervised, and unsupervised learning methods.

Linking records from different data sources, referred to as record linkage, is a longstanding but not yet satisfactorily resolved question in many fields of science. For practitioners, it is difficult to ensure the quality of linkage at the time of applying linkage techniques in real world applications. Instead, linkage errors are often detected later on, mostly by users of the applications. This not only requires us to repair errors, but also provides us with opportunities to observe the linkage quality and uncover why such errors occur. In viewing that record linkage is a complex and evolving process, we study how to acquire insights from linkage errors for achieving high-quality linkage. We propose a generic repairing framework which allows us to start with imperfect linkage models, and dynamically repair linkage models and errors for improved linkage quality. We have evaluated our repairing framework over three real-world datasets and the experimental results show that the performance of the proposed tree-structured classifier SVM-tree outperforms the baseline methods.

Answering exact shortest path distance queries is a fundamental task in graph theory. Despite a tremendous amount of research on the subject, there is still no satisfactory solution that can scale to billion-scale complex networks. Labelling-based methods are well-known for rendering fast response time to distance queries; however, existing works can only construct labelling on moderately large networks (million-scale) and cannot scale to large networks (billion-scale) due to their prohibitively large space requirements and very long preprocessing time. In this work, we present novel techniques to efficiently construct distance labelling and process exact shortest path distance queries for complex networks with billions of vertices and billions of edges. Our method is based on two ingredients: (i) a scalable labelling algorithm for constructing minimal distance labelling, and (ii) a querying framework that supports fast distance-bounded search on a sparsified graph. Thus, we first develop a novel labelling algorithm that can scale to graphs at the billion-scale. Then, we formalize a querying framework for exact distance queries, which combines our proposed highway cover distance labelling with distance-bounded searches to enable fast distance computation. To speed up the labelling construction process, we further propose a parallel labelling method that can construct labelling simultaneously for multiple landmarks. We evaluated the performance of the proposed methods on 12 real-world networks. The experiments show that the proposed methods can not only handle networks with billions of vertices, but also be up to 70 times faster in constructing labelling and save up to 90% of labelling space. In particular, our method can answer distance queries on a billion-scale network of around 8B edges in less than 1ms, on average.

Meta-learning algorithms for active learning are emerging as a promising paradigm for learning the "best" active learning strategy. However, current learning-based active learning approaches still require sufficient training data so as to generalize meta-learning models for active learning. This is contrary to the nature of active learning which typically starts with a small number of labeled samples. The unavailability of large amounts of labeled samples for training meta-learning models would inevitably lead to poor performance (e.g., instabilities and overfitting). In our paper, we tackle these issues by proposing a novel learning-based active learning framework, called Learning To Sample (LTS). This framework has two key components: a sampling model and a boosting model, which can mutually learn from each other in iterations to improve the performance of each other. Within this framework, the sampling model incorporates uncertainty sampling and diversity sampling into a unified process for optimization, enabling us to actively select the most representative and informative samples based on an optimized integration of uncertainty and diversity. To evaluate the effectiveness of the LTS framework, we have conducted extensive experiments on three different classification tasks: image classification, salary level prediction, and entity resolution. The experimental results show that our LTS framework significantly outperforms all the baselines when the label budget is limited, especially for datasets with highly imbalanced classes. In addition to this, our LTS framework can effectively tackle the cold start problem occurring in many existing active learning approaches.

Can machines trace human knowledge like humans? Knowledge tracing (KT) is a fundamental task in a wide range of applications in education, such as massive open online courses (MOOCs), intelligent tutoring systems, educational games, and learning management systems. It models dynamics in a student's knowledge states in relation to different learning concepts through their interactions with learning activities. Recently, several attempts have been made to use deep learning models for tackling the KT problem. Although these deep learning models have shown promising results, they have limitations: either lack the ability to go deeper to trace how specific concepts in a knowledge state are mastered by a student, or fail to capture long-term dependencies in an exercise sequence. In this paper, we address these limitations by proposing a novel deep learning model for knowledge tracing, namely Sequential Key-Value Memory Networks (SKVMN). This model unifies the strengths of recurrent modelling capacity and memory capacity of the existing deep learning KT models for modelling student learning. We have extensively evaluated our proposed model on five benchmark datasets. The experimental results show that (1) SKVMN outperforms the state-of-the-art KT models on all datasets, (2) SKVMN can better discover the correlation between latent concepts and questions, and (3) SKVMN can trace the knowledge state of students dynamics, and a leverage sequential dependencies in an exercise sequence for improved predication accuracy.

Vertices in a real-world social network can be grouped into densely connected communities that are sparsely connected to other groups. Moreover, these communities can be partitioned into successively more cohesive communities. Despite an ever-growing pile of research on hierarchical community detection, existing methods suffer from either inefficiency or inappropriate modeling. Yet, some cut-based approaches have shown to be effective in finding communities without hierarchies. In this paper, we study the hierarchical community detection problem in large networks and show that it is NP-hard. We then propose an efficient algorithm based on edge-cuts to identify the hierarchy of communities. Since communities at lower levels of the hierarchy are denser than the higher levels, we leverage a fast network sparsification technique to enhance the running time of the algorithm. We further propose a randomized approximation algorithm for information centrality of networks. We finally evaluate the performance of the proposed algorithms by conducting extensive experiments using real datasets. Our experimental results show that the proposed algorithms are promising and outperform the state-of-the-art algorithms by several orders of magnitude.

Vertex classification is a critical task in graph analysis, where both contents and linkage of vertices are incorporated during classification. Recently, researchers proposed using deep neural network to build an end-to-end framework, which can capture both local content and structure information. These approaches were proved effective in incorporating semantic meanings of neighbouring vertices, while the usefulness of this information was not properly considered. In this paper, we propose an Attentive Graph-based Recursive Neural Network (AGRNN), which exerts attention on neural network to make our model focus on vertices with more relevant semantic information. We evaluated our approach on three real-world datasets and also datasets with synthetic noise. Our experimental results show that AGRNN achieves the state-of-the-art performance, in terms of effectiveness and robustness. We have also illustrated some attention weight samples to demonstrate the rationality of our model.

The temporal linkage of census data allows the detailed analysis of population-related changes in an area of interest. It should not only link records about the same person but also support the linkage of groups of related persons such as households. In this paper, we thus propose a new approach to both temporal record and group (household) linkage for census data and study its application for change analysis. The approach utilizes the relationships between individuals to determine the similarity of groups and their members within a graph-based method. The approach is also iterative by first identifying high quality matches that are subsequently extended by matches found with less restrictive similarity criteria. A comprehensive evaluation using historical census data from the UK indicates a high effectiveness of the proposed approach. Furthermore, the linkage enables an insightful analysis of household changes determined by so-called evolution patterns.

A data analytics flow typically operates on three layers: ingestion, analytics, and storage, each of which is provided by a data-intensive system. These systems are often available as cloud managed services, enabling the users to have pain-free deployment of data analytics flow applications such as click-stream analytics. Despite straightforward orchestration, elasticity management of the flows is challenging. This is due to: a) heterogeneity of workloads and diversity of cloud resources such as queue partitions, compute servers and NoSQL throughputs capacity, b) workload dependencies between the layers, and c) different performance behaviours and resource consumption patterns. In this demonstration, we present Flower, a holistic elasticity management system that exploits advanced optimization and control theory techniques to manage elasticity of complex data analytics flows on clouds. Flower analyzes statistics and data collected from different data-intensive systems to provide the user with a suite of rich functionalities, including: workload dependency analysis, optimal resource share analysis, dynamic resource provisioning, and cross-platform monitoring. We will showcase various features of Flower using a real-world data analytics flow. We will allow the audience to explore Flower by visually defining and configuring a data analytics flow elasticity manager and get hands-on experience with integrated data analytics flow management.

In this work we propose a semantic-aware blocking framework for entity resolution (ER). The proposed framework is built using locality-sensitive hashing (LSH) techniques to efficiently unify both textual and semantic features into an ER blocking process. In order to understand how similarity metrics may affect the effectiveness of ER blocking, we study the robustness of similarity metrics and their properties in terms of LSH families. We further discuss how the semantic similarity of records can be captured, measured, and integrated with LSH techniques over multiple similarity spaces. We have evaluated our proposed framework over two real-world data sets, and compared it with the state-of-the-art blocking techniques. The experimental study shows that using a combination of semantic features and textual features can considerably improve the quality of blocking. Due to the probabilistic nature of LSH, this semantic-aware blocking framework also enables us to build fast and reliable blocking for performing entity resolution tasks in a large-scale data environment.

Network analytics has become increasingly popular in recent years. Various graph systems have been developed for analysing networks, while network data is still largely stored and managed in relational database systems in the first place. As two separate systems are often used to manage and analyse network data, it not only increases the difficulty for users to learn and maintain these different systems simultaneously, but also impedes performing more sophisticated analysis on relational and topological properties of network data. Aiming to tackle these issues, we present Rogas in this paper, which is a declarative framework that allows the user to formulate analysis queries naturally without thinking about the tedious implementation details of graph algorithms and query processing.

In this paper, we propose a semantic-aware blocking framework for entity resolution (ER). The proposed framework is built using locality-sensitive hashing (LSH) techniques, which efficiently unifies both textual and semantic features into an ER blocking process. In order to understand how similarity metrics may affect the effectiveness of ER blocking, we study the robustness of similarity metrics and their properties in terms of LSH families. Then, we present how the semantic similarity of records can be captured, measured, and integrated with LSH techniques over multiple similarity spaces. In doing so, the proposed framework can support efficient similarity searches on records in both textual and semantic similarity spaces, yielding ER blocking with improved quality. We have evaluated the proposed framework over two real-world data sets, and compared it with the state-of-the-art blocking techniques. Our experimental study shows that the combination of semantic similarity and textual similarity can considerably improve the quality of blocking. Furthermore, due to the probabilistic nature of LSH, this semantic-aware blocking framework enables us to build fast and reliable blocking for performing entity resolution tasks in a large-scale data environment.

Entity resolution (ER) is the task of deciding which records in one or more databases refer to the same real-world entities. A crucial step in ER is the accurate classification of pairs of records into matches and non-matches. In most practical ER applications, obtaining training data %of high quality is costly and time consuming. Various techniques have been proposed for ER to interactively generate training data and learn an accurate classifier. We propose an approach for training data selection for ER that exploits the cluster structure of the weight vectors (similarities) calculated from compared record pairs. Our approach adaptively selects an optimal number of informative training examples for manual labeling based on a user defined sampling error margin, and recursively splits the set of weight vectors to find pure enough subsets for training. We consider two aspects of ER that are highly significant in practice: a limited budget for the number of manual labeling that can be done, and a noisy oracle where manual labels might be incorrect. Experiments on four real public data sets show that our approach can significantly reduce manual labeling efforts for training an ER classifier while achieving matching quality comparative to fully supervised classifiers.

Schema mapping plays an important role in many database-related transformation tasks, such as data exchange, data integration and data migration. In this paper, we study the dependency propagation problem in the context of schema mappings. This allows us to understand and discover logical consequences among source constraints, target constraints and mapping constraints of a schema mapping. In order to precisely characterize the relationships between source and target schemas, we consider mapping constraints as being bipartite TGDs, i.e., a class of tuple-generating dependencies (TGDs) that include both source-to-target dependencies and target-to-source dependencies. We then develop propagation graphs to represent the relationships among the attributes of different relations and, based on such propagation graphs, we propose algorithms to propagate inclusion and functional dependencies between source and target schemas. We have also designed a schema mapping reasoning tool to implement and evaluate our proposed approach.

Entity resolution (ER) is a common data cleaning task that involves determining which records from one or more data sets refer to the same real-world entities. Because a pairwise comparison of all records scales quadratically with the number of records in the data sets to be matched, it is common to use blocking or indexing techniques to reduce the number of comparisons required. These techniques split the data sets into blocks and only records within blocks are compared with each other. Most existing blocking techniques do not provide control over the size of the generated blocks, despite this control being important in many practical applications of ER, such as privacy-preserving record linkage and real-time ER. We propose two novel hierarchical clustering approaches which can generate blocks within a specified size range, and we present a penalty function which allows control of the trade-off between block quality and block size in the clustering process. We evaluate our techniques on three real-world data sets and compare them against three baseline approaches. The results show our proposed techniques perform well on the measures of pairs completeness and reduction ratio compared to the baseline approaches, while also satisfying the block size restrictions.

Constraints ubiquitously exist in many real-life applications for entity resolution. However, it is always challenging to effectively specify and use such constraints for performing ER tasks. In particular, not every constraint is equally robust. Adding weights to express the “confidence” on constraints thus becomes a natural choice. In this paper, the authors study entity resolution (ER), the problem of determining which records in one or more databases refer to the same entities, in the presence of weighted constraints. They propose a unified framework that allows us to associate a weight for each constraint, capturing the confidence for its robustness in an ER model. The authors develop an approach to learn weighted constraints based on domain knowledge, and investigate how effectively and efficiently weighted constraints can be used for generating an ER clustering and for determining a propagation order across multiple entity types. Their experimental study shows that using weighted constraints can lead to improved ER quality and scalability.

Partial updates arise when a location bound to a complex value is updated in parallel. Compatibility of such partial updates to disjoint locations can be assured by applying applicative algebras. However, due to the arbitrary nesting of type constructors, locations of complex-value database are often defined at multiple abstraction levels and thereby non-disjoint. Thus, applicative algebras is not as smooth as its simple definition suggests. In this paper, we investigate this problem in the context of complex-value databases, where partial updates arise naturally in database transformations. We show that a more efficient solution can be obtained when generalising the notion of location and thus permitting dependencies between locations. On these grounds we develop a systematic approach to consistency checking for update sets that involve partial updates.

In order to increase the expressiveness of XML query languages we define an XML object model that provides a rich description of XML data using the notions of class schema and class tuple. Based on this model we develop a novel query language, the XML Identity Query Language (XIQL) based on identifier generation and fixed-point computation. However, XIQL cannot deal with finite tree duplicates in an XML object graph. To solve this problem we extend XIQL by integrating termsdenoting hereditarily finite sets. With respect to determinate transformations the extended XIQL+is still incomplete, but becomes complete with respect to a modified completeness criterion for XML database transformations, which aims at capturing more non-determinism.

Data warehouses integrate and aggregate data from various sources to support decision making within an enterprise. Usually, it is assumed that data are extracted from operational databases used by the enterprise. Web warehousing relaxes this view permitting data sources to be located anywhere on the world-wide web. In this paper we even go one step further and propose that web warehousing should exploit data-intensive web services. For this we adopt the view of the recently introduced model of abstract state services (ASSs). An ASS combines a hidden database layer with an operation-equipped view layer, and can be anything from a simple function to a full-fledged Web Information System, thus provides an abstraction of web services that can be made available for use by other systems, e.g. via the web. We demonstrate how data warehouses and OLAP systems can be considered in a natural way as ASSs, i.e. selected data and functionality of a data warehouse may be made available in the form of a generalised web service, and consequently ASS composition can be used for web warehousing. In order to become workable the model of ASSs has to be extended in a way that allows services to be searched for. For this we propose federations of services together with an ontology that specifies their semantics.

The exact validation of streaming XML documents can be realised by using visibly push-down automata (VPA) that are defined by Extended Document Type Definitions (EDTD). It is straightforward to represent such an automaton as an Abstract State Machine (ASM). However, creating a whole VPA is not an efficient validation approach. In this paper it is shown, how the VPA construction can be avoided by using a refined ASM that only requires knowledge of the EDTD. In a second step this approach is extended to approximate validation of streaming XML documents taking at most k updates to the document into consideration.