We investigate the data management of temporal property graphs on atemporal Labeled Property Graph (LPG) engines. While existing frameworks define temporal semantics, practitioners lack systematic empirical guidance on mapping these models to concrete representations in the absence of native engine support. We formalize two fundamental representation strategies implemented on top of standard LPG systems: a Versioning strategy that materializes temporal states via topological expansion, and a Property Lists strategy that encapsulates evolution through property-level compression. For each strategy, we define query translations for temporal evolution operators and analytical aggregations, and evaluate them across two heterogeneous real-world datasets. Our evaluation reveals a fundamental trade-off between topological selectivity and historical compactness: Versioning excels at high-throughput ingestion and short-window workloads but suffers from traversal amplification in dense graphs over long horizons, while Property Lists amortizes scan costs for read-heavy, multi-window analytics but incurs higher ingestion overhead and cannot support time-varying labels. We identify workload-dependent crossover points, showing how dataset density and structural volatility determine the superior strategy.

As AI and web agents become pervasive in decision-making, it is critical to design intelligent systems that not only support sustainability efforts but also guard against misinformation. Greenwashing, i.e., misleading corporate sustainability claims, poses a major challenge to environmental progress. To address this challenge, we introduce EmeraldMind, a fact-centric framework integrating a domain-specific knowledge graph with retrieval-augmented generation to automate greenwashing detection. EmeraldMind builds the EmeraldGraph from diverse corporate ESG (environmental, social, and governance) reports, surfacing verifiable evidence, often missing in generic knowledge bases, and supporting large language models in claim assessment. The framework delivers justification-centric classifications, presenting transparent, evidence-backed verdicts and abstaining responsibly when claims cannot be verified. Experiments on a new greenwashing claims dataset demonstrate that EmeraldMind achieves competitive accuracy, greater coverage, and superior explanation quality compared to generic LLMs, without the need for fine-tuning or retraining.

Path-based explanations provide intrinsic insights into graph-based recommendation models. However, most previous work has focused on explaining an individual recommendation of an item to a user. In this paper, we propose summary explanations, i.e., explanations that highlight why a user or a group of users receive a set of item recommendations and why an item, or a group of items, is recommended to a set of users as an effective means to provide insights into the collective behavior of the recommender. We also present a novel method to summarize explanations using efficient graph algorithms, specifically the Steiner Tree and the Prize-Collecting Steiner Tree. Our approach reduces the size and complexity of summary explanations while preserving essential information, making explanations more comprehensible for users and more useful to model developers. Evaluations across multiple metrics demonstrate that our summaries outperform baseline explanation methods in most scenarios, in a variety of quality aspects.

Detecting meaningful communities in networks is essential for understanding complex social, biological, and information systems. Modularity effectively captures the quality of communities by comparing the observed and expected edge densities, but it often overlooks fairness with regards to the connectivity of different groups of nodes within the communities. In this work, we address this limitation by proposing fairness-aware community detection algorithms that incorporate group-sensitive connectivity into the modularity framework. Our approach is based on optimizing distinct sub-matrices of the modularity matrix that isolate intra-group and inter-group connections. We introduce two algorithmic families: (a) Input-based methods, including fair spectral and deep learning algorithms that directly operate on these sub-matrices; and (b) Loss-based methods, which integrate fairness-aware sub-matrix information into the learning objective of deep community detection models. Our experiments on synthetic and real-world networks demonstrate that our algorithms significantly improve group connectivity fairness without compromising community quality.

Communities in networks are groups of nodes that are more densely connected to each other than to the rest of the network, forming clusters with strong internal relationships. When nodes have sensitive attributes, such as demographic groups in social networks, a key question is whether nodes in each group are equally well-connected within each community. We model connectivity fairness using group modularity, an adaptation of modularity that accounts for group structures. We introduce two versions of group modularity, each grounded on a different null model, and propose fairness-aware community detection algorithms. Finally, we provide experimental results on real and synthetic networks, evaluating both the connectivity fairness of community structures in networks and the performance of our fairness-aware algorithms.

Currently, the growing proliferation of information systems generates large volumes of data continuously, stemming from a variety of sources such as web platforms, social networks, and multiple devices. These data, often lacking a defined schema, require an initial process of consolidation and cleansing before analysis and knowledge extraction can occur. In this context, Entity Resolution (ER) plays a crucial role, facilitating the integration of knowledge bases and identifying similarities among entities from different sources. However, the traditional ER process is computationally expensive, and becomes more complicated in the streaming context where the data arrive continuously. Moreover, there is a lack of studies involving fairness and ER, which is related to the absence of discrimination or bias. In this sense, fairness criteria aim to mitigate the implications of data bias in ER systems, which requires more than just optimizing accuracy, as traditionally done. Considering this context, this work presents TREATS, a schema-agnostic and fairness-aware ER workflow developed for managing streaming data incrementally. The proposed fairness-aware ER framework tackles constraints across various groups of interest, presenting a resilient and equitable solution to the related challenges. Through experimental evaluation, the proposed techniques and heuristics are compared against state-of-the-art approaches over five real-world data source pairs, in which the results demonstrated significant improvements in terms of fairness, without degradation of effectiveness and efficiency measures in the streaming environment. In summary, our contributions aim to propel the ER field forward by providing a workflow that addresses both technical challenges and ethical concerns.

Abstract CounterFair is a group counterfactual search algorithm that detects and minimizes biases among sensitive groups and identifies relevant subgroups inside these sensitive groups based on shared counterfactual instances. We investigate the latter capability, analyzing the found subgroups from the perspective of fairness based on counterfactual reasoning, in order to evaluate whether they present different biases with respect to each other and to the sensitive feature groups they belong to. We perform these measurements on the subgroups extracted by CounterFair over six binary classification datasets, providing figures and their respective analysis on the presence of bias.

Counterfactual explanations can be used as a means to explain a models decision process and to provide recommendations to users on how to improve their current status. The difficulty to apply these counterfactual recommendations from the users perspective, also known as burden, may be used to assess the models algorithmic fairness and to provide fair recommendations among different sensitive feature groups. We propose a novel model-agnostic, mathematical programming-based, group counterfactual algorithm that can: (1) detect biases via group counterfactual burden, (2) produce fair recommendations among sensitive groups and (3) identify relevant subgroups of instances through shared counterfactuals. We analyze these capabilities from the perspective of recourse fairness, and empirically compare our proposed method with the state-of-the-art algorithms for group counterfactual generation in order to assess the bias identification and the capabilities in group counterfactual effectiveness and burden minimization.

When the focus is on the relationships or interactions between entities, graphs offer an intuitive model for many real-world data. Such graphs are usually large and change over time, thus, requiring models and strategies that explore their evolution. We study the evolution of aggregate graphs and introduce the GraphTempo model that allows temporal and graph aggregation not only on node level by grouping individual nodes, but on a pattern level as well, where subgraphs are grouped together. Furthermore, we propose an efficient strategy for exploring the evolution of the graph based on identifying time intervals of significant growth, shrinkage, or stability. Finally, we evaluate the efficiency and effectiveness of the proposed approach using four real graphs.

In this paper, we study the fairness of community structures in networks from a group-based perspective. Specifically, we assume that individuals in a social network belong to different groups based on the value of one of their sensitive attributes, such as their age, gender, or race, and we consider community fairness towards the protected group. Most previous work has focused on a balanced-based definition of fairness that seeks for an appropriate representation of the members of the protected group in each community. We introduce a novel form of community fairness, termed modularity-based fairness, that asks that the members of the protected group are well connected in their respective communities. We present results of the balanced-based and modularity-based fairness of several real and synthetic networks.

Nowadays, sequential recommendations are becoming more prevalent. A user expects the system to remember past interactions and not conduct each recommendation round as a stand-alone process. Additionally, group recommendation systems are more prominent since more and more people are able to form groups for activities. Subsequently, the data that a group recommendation system needs to consider becomes more complicated — historical data and feedback for each user, the items recommended and ultimately selected to and by the group, etc. This makes the selection of a group recommendation algorithm to be even more complex. In this work, we propose the SQUIRREL framework — SeQUentIal Recommendations with ReinforcEment Learning, a model that relies on reinforcement learning techniques to select the most appropriate group recommendation algorithm based on the current state of the group. At each round of recommendations, we calculate the satisfaction of each group member, how relevant each item in the group recommendation list is for each user, and based on this the model selects an action, that is, a recommendation algorithm out of a predefined set that will produce the maximum reward. We present a sample of methods that can be used; however, the model is able to be further configured with additional actions, different definitions of rewards or states. We perform experiments on three real world datasets, 20M MovieLens, GoodReads and Amazon, and show that SQUIRREL is able to outperform all the individual recommendation methods used in the action set, by correctly identifying the recommendation algorithm that maximizes the reward function utilized.

Record linkage, the process of identifying records representing the same real world entity in the absence of common unique identifiers, is one of the most intriguing problems in data processing, hence drawing attention for several decades. One approach for addressing this problem is by means of supervised learning. However, when it comes to linking records of individuals, the quality of the results may be low due to hidden bias phenomena, not deliberately caused, but originating from specific properties of the names of people of specific ethnic origin. In this paper, we focus on SVM-based record linkage and considering the fact of hidden bias, we propose a methodology oriented towards Ethnicity group-based training for specific Ethnicity groups, an approach that manages to elevate matching performance, compared to the average case.

Network algorithms play a critical role in various applications, such as recommendations, diffusion maximization, and web search. In this paper, we focus on the fairness of such algorithms and in particular of PageRank. PageRank fairness refers to a fair allocation of the PageRank weights among the nodes. We consider the effect of the network structure on PageRank fairness. Concretely, we provide analytical formulas for computing the effect of edge additions on fairness and for the conditions that an edge must satisfy so that its addition improves fairness. We also provide analytical formulas for evaluating the role of existing edges in fairness. We use our findings to propose efficient linear time link recommendation algorithms for maximizing fairness, and we evaluate them on real datasets. Our approach can be seen as an effort towards making the network itself fairer as opposed to making fairer the network algorithms, or their outputs.

Abstract Recently, group recommendations have gained much attention. Nevertheless, most approaches consider only one round of recommendations. However, in a real-life scenario, it is expected that the history of previous recommendations is exploited to tailor the recommendations towards meeting the needs of the group members. Such history should include not only which items the system suggested, but also the reaction of the members to these items. This work introduces the problem of sequential group recommendations, by exploiting the concept of satisfaction and disagreement. Satisfaction describes how well the group received the suggested items. Disagreement describes the satisfaction bias among the group members. We utilize these concepts in three new aggregation methods, SDAA, SIAA and Average+, designed to address the specific challenges introduced by sequential group recommendations. We experimentally show the effectiveness of our methods using big real datasets for both stable and ephemeral groups.

Abstract We increasingly depend on a variety of data-driven algorithmic systems to assist us in many aspects of life. Search engines and recommender systems among others are used as sources of information and to help us in making all sort of decisions from selecting restaurants and books, to choosing friends and careers. This has given rise to important concerns regarding the fairness of such systems. In this work, we aim at presenting a toolkit of definitions, models and methods used for ensuring fairness in rankings and recommendations. Our objectives are threefold: (a) to provide a solid framework on a novel, quickly evolving and impactful domain, (b) to present related methods and put them into perspective and (c) to highlight open challenges and research paths for future work.

There is an urgent call to detect and prevent "biased data" at the earliest possible stage of the data pipelines used to build automated decision-making systems. In this paper, we are focusing on controlling the data bias in entity resolution (ER) tasks aiming to discover and unify records/descriptions from different data sources that refer to the same real-world entity. We formally define the ER problem with fairness constraints ensuring that all groups of entities have similar chances to be resolved. Then, we introduce FairER, a greedy algorithm for solving this problem for fairness criteria based on equal matching decisions. Our experiments show that FairER achieves similar or higher accuracy against two baseline methods over 7 datasets, while guaranteeing minimal bias.

Temporal interaction networks capture the history of activities between entities along a timeline. At each interaction, some quantity of data (money, information, traffic) flows from one vertex of the network to another. Flow-based analysis can reveal important information, such as unusually large money transfers in a part of a financial transaction network. In this paper, we introduce the flow computation problem between two vertrices in an interaction network. We propose and study two models of flow computation, one based on a greedy flow transfer assumption and one that finds the maximum possible flow. We show that the greedy flow computation problem can be easily solved by a single scan of the interactions in time order. For the harder maximum flow problem, we propose precomputation and simplification approaches that can greatly reduce its complexity in practice. We also approach the problem of flow pattern enumeration in interaction networks and propose an effective path indexing technique. We evaluate our algorithms using real datasets. The results demonstrate the efficiency and scalability of our algorithms.

We increasingly depend on a variety of data-driven algorithmic systems to assist us in many aspects of life. Search engines and recommendation systems amongst others are used as sources of information and to help us in making all sort of decisions from selecting restaurants and books, to choosing friends and careers. This has given rise to important concerns regarding the fairness of such systems. This tutorial aims at presenting a toolkit of definitions, models and methods used for ensuring fairness in rankings and recommendations. Our objectives are three-fold: (a) to provide a solid framework on a novel, quickly evolving, and impactful domain, (b) to present related methods and put them into perspective, and (c) to highlight challenges and research paths for researchers and practitioners that work in data management and applications.

We increasingly depend on a variety of data-driven algorithmic systems to assist us in many aspects of life. Search engines and recommender systems amongst others are used as sources of information and to help us in making all sort of decisions from selecting restaurants and books, to choosing friends and careers. This has given rise to important concerns regarding the fairness of such systems. In this tutorial, we aim at presenting a toolkit of methods used for ensuring fairness in rankings and recommendations. Our objectives are two-fold: (a) to present related methods of this novel, quickly evolving and impactful domain, and put them into perspective, and (b) to highlight open challenges and research paths for future work.

Algorithmic fairness has attracted significant attention in the past years. In this paper, we consider fairness for link analysis and in particular for the celebrated Pagerank algorithm. Given that the nodes in a network belong to groups (for example, based on demographic or other characteristics), we provide a parity-based definition of fairness that imposes constraints on the proportion of Pagerank allocated to the members of each group. We propose two families of fair Pagerank algorithms: the first (Fairness-Sensitive Pagerank) modifies the jump vector of the Pagerank algorithm to enforce fairness; the second (Locally Fair Pagerank) imposes a fair behavior per node. We then define a stronger fairness requirement, termed universal personalized fairness, that asks that the derived personalized pageranks of all nodes are fair. We prove that the locally fair algorithms achieve also universal personalized fairness, and furthermore, we prove that this is the only family of algorithms with this property, establishing an equivalence between universal personalized fairness and local fairness. We also consider the problem of achieving fairness while minimizing the utility loss with respect to the original Pagerank algorithm. We present experiments with real and synthetic networks that examine the fairness of the original Pagerank and demonstrate qualitatively and quantitatively the properties of our algorithms.

In this paper, we study bias in knowledge graph embeddings. We focus on gender bias in occupations, but our approach is applicable to other types of bias. We start by proposing measures for identifying bias in the dataset (i.e., in the KG) and then present two methods for testing whether any bias in the dataset is amplified by the embeddings. First, we look for gender-specific occupation analogies in the embeddings. Second, we test whether link prediction (i.e., occupation prediction in our case) aggregates gender bias by proposing gender-dominated occupations to people of the corresponding gender more often than expected. Then, we use a debiasing approach based on projections on the gender subspace. We present experimental results using the Wikidata dataset and pretrained TransE embeddings. Our results show that there exists gender bias in the dataset and that such bias is amplified by the embeddings. Our debiasing approach removes bias with a small penalty on accuracy.

Temporal graphs represent relationships and interactions among entities over time, such as those occurring among users in social, transaction, and telecommunication networks. The analysis of their temporal structure help us understand, and predict the behavior of their entities. A typical analysis task in graph networks is the finding of all appearances of an input graph pattern query. Such appearances are called matches. In this paper, we are interested in finding all matches of an interaction pattern query within temporal graphs. To this end, we propose a hybrid approach that achieves effective filtering of potential matches based both on structure and time. Our approach exploits a graph representation where edges are ordered by time. We present experiments with real datasets that illustrate the efficiency of our approach.

Peer reviewed

Teams that bring together experts with different expertise are important for solving complex problems. However, research shows that teaming up people simply based on their ability is not enough. Team members need to have clear roles, and they should mutually endorse and respect their teammates for the role they assume on the team. In this paper, we define the MaxMutualRespect problem, a novel team-formation problem that asks for a set of experts, each assigned to a distinct role, such that the total respect that the individuals receive by the rest of the team members for their assigned role is maximized. We show that the problem is NP-complete and we consider approximation and heuristic algorithms. Experiments with real datasets demonstrate that our problem definitions and algorithms work well in practice and yield intuitive results.

Graphs offer a natural model for the relationships and interactions among entities, such as those occurring among users in social and cooperation networks, and proteins in biological networks. Since most such networks are dynamic, to capture their evolution over time, we assume a sequence of graph snapshots where each graph snapshot represents the state of the network at a different time instance. Given this sequence, we seek to find the top-$k$most durable matchesof an input graph pattern query, that is, the matches that exist for the longest period of time. The straightforward way to address this problem is to apply a state-of-the-art graph pattern matching algorithm at each snapshot and then aggregate the results. However, for large networks and long sequences, this approach is computationally expensive, since all matches have to be generated at each snapshot, including those appearing only once. We propose a new approach that uses a compact representation of the sequence of graph snapshots, appropriate time indexes to prune the search space, and strategies to determine the duration of the seeking matches. Finally, we present experiments with real datasets that illustrate the efficiency and effectiveness of our approach.

Recommending packages of items to groups of users has several applications, including recommending vacation packages to groups of tourists, entertainment packages to groups of friends, or sets of courses to groups of students. In this paper, we focus on a novel aspect of package-to-group recommendations, that of fairness. Specifically, when we recommend a package to a group of people, we ask that this recommendation is fair in the sense that every group member is satisfied by a sufficient number of items in the package. We explore two definitions of fairness and show that for either definition the problem of finding the most fair package is NP-hard. We exploit the fact that our problem can be modeled as a coverage problem, and we propose greedy algorithms that find approximate solutions within reasonable time. In addition, we study two extensions of the problem, where we impose category or spatial constraints on the items to be included in the recommended packages. We evaluate the appropriateness of the fairness models and the performance of the proposed algorithms using real data from Yelp, and a user study.

Trolling describes a range of antisocial online behaviors that aim at disrupting the normal operation of online social networks and media. Combating trolling is an important problem in the online world. Existing approaches rely on human-based or automatic mechanisms for identifying trolls and troll posts. In this paper we take a novel approach to the trolling problem: our goal is to identify the targets of the trolls, so as to prevent trolling before it happens. We thus define the troll vulnerability prediction problem, where given a post we aim at predicting whether it is vulnerable to trolling. Towards this end, we define a novel troll vulnerability metric of how likely a post is to be attacked by trolls, and we construct models for predicting troll-vulnerable posts, using features from the content and the history of the post. Our experiments with real data from Reddit demonstrate that our approach is successful in recalling a large fraction of the troll-vulnerable posts.

A wide spectrum of Internet-scale mobile applications, ranging from social networking, gaming and entertainment to emergency response and crisis management, all require efficient and scalable All k Nearest Neighbor (AkNN) computations over millions of moving objects every few seconds to be operational. In this paper we present Spitfire, a distributed algorithm that provides a scalable and high-performance AkNN processing framework to our award-winning geo-social network named Rayzit. The proposed algorithm deploys a fast load-balanced partitioning along with an efficient replication-set selection, to provide fast main-memory computations of the exact AkNN results in a batch-oriented manner. We evaluate, both analytically and experimentally, how the pruning efficiency of the Spitfire algorithm plays a pivotal role in reducing communication and response time up to an order of magnitude, compared to three state-of-the-art distributed AkNN algorithms executed in distributed main-memory.

In this paper, we focus on labeled graphs that evolve over time. Given a sequence of graph snapshots representing the state of the graph at different time instants, we seek to find the most durable matches of an input graph pattern query, that is, the matches that exist for the longest period of time. The straightforward way to address this problem is by running a state-of-the-art graph pattern algorithm at each snapshot and aggregating the results. However, for large networks this approach is computationally expensive, since all matches have to be generated at each snapshot, including those appearing only once. We propose a new approach that uses a compact representation of the sequence of graph snapshots, appropriate time indexes to prune the search space and a threshold on the duration of the pattern to determine the search order. We also present experimental results using real datasets that illustrate the efficiency and effectiveness of our approach.

The success of recommender systems has made them the focus of a massive research effort in both industry and academia. Recent work has generalized recommendations to suggest packages of items to single users, or single items to groups of users. However, to the best of our knowledge, the interesting problem of recommending a package to a group of users (P2G) has not been studied to date. This is a problem with several practical applications, such as recommending vacation packages to tourist groups, entertainment packages to groups of friends, or sets of courses to groups of students. In this paper, we formulate the P2G problem, and we propose probabilistic models that capture the preference of a group towards a package, incorporating factors such as user impact and package viability. We also investigate the issue of recommendation fairness. This is a novel consideration that arises in our setting, where we require that no user is consistently slighted by the item selection in the package. We present aggregation algorithms for finding the best packages and compare our suggested models with baseline approaches stemming from previous work. The results show that our models find packages of high quality which consider all special requirements of P2G recommendation.

Link recommendations are critical for both improving the utility and expediting the growth of social networks. Most previous approaches focus on suggesting links that are highly likely to be adopted. In this paper, we add a different perspective to the problem by aiming at recommending links that also improve specific properties of the network. In particular, our goal is to recommend to users links that if adopted would improve their centrality in the network. Specifically, we introduce the centrality-aware link recommendation problem as the problem of recommending to a user u, k links from a pool of recommended links so as to maximize the expected decrease of the sum of the shortest path distances of $u$ to all other nodes in the network. We show that the problem is NP-hard, but our optimization function is monotone and sub-modular which guarantees a constant approximation ratio for the greedy algorithm. We present a fast algorithm for computing the expected decrease caused by a set of recommendations which we use as a building block in our algorithms. We provide experimental results that evaluate the performance of our algorithms with respect to both the accuracy of the prediction and the improvement in the centrality of the nodes, and we study the tradeoff between the two.

A wide spectrum of Internet-scale mobile applications, ranging from social networking, gaming and entertainment to emergency response and crisis management, all require efficient and scalable All k Nearest Neighbor (AkNN) computations over millions of moving objects every few seconds to be operational. Most traditional techniques for computing AkNN queries are centralized, lacking both scalability and efficiency. Only recently, distributed techniques for shared-nothing cloud infrastructures have been proposed to achieve scalability for large datasets. These batch-oriented algorithms are sub-optimal due to inefficient data space partitioning and data replication among processing units. In this paper, we present Spitfire, a distributed algorithm that provides a scalable and high-performance AkNN processing framework. Our proposed algorithm deploys a fast load-balanced partitioning scheme along with an efficient replication-set selection algorithm, to provide fast main-memory computations of the exact AkNN results in a batch-oriented manner. We evaluate, both analytically and experimentally, how the pruning efficiency of the Spitfire algorithm plays a pivotal role in reducing communication and response time up to an order of magnitude, compared to three other state-of-the-art distributed AkNN algorithms executed in distributed main-memory.

In this paper, we consider large graphs that evolve over time, such as graphs that model social networks. Given two instances of the graph at two points in time, we ask to identify the top pairs of nodes whose shortest path dis-tance has decreased the most. We call these pairs converg-ing. The straightforward way to address this problem is by computing the shortest path distances of all pairs at both instances and keeping the ones with the largest differences. Since for large networks this is computationally infeasible, we consider a budgeted version of the problem, where given a fixed budget of single-source shortest path computations, we seek to identify nodes that participate in as many con-verging pairs as possible. We evaluate a number of different approaches for our problem, that employ centrality-based, dispersion-based, and landmark-based distance estimation metrics. We also consider a classification-based approach that builds a classifier that combines the above features for predicting whether a node participates in one of the top con-verging pairs. We present experimental results using real-world datasets that show that we are able to identify the large majority of the top converging pairs on a very small budget.

Since most graphs evolve over time, it is useful to be able to query their history. We consider historical reachability queries that ask for the existence of a path in some time interval in the past, either in the whole duration of the interval (conjunctive queries), or in at least one time instant in the interval (disjunctive queries). We study both alternatives of storing the full transitive closure of the evolving graph and of performing an online traversal. Then, we propose an appropriate reachability index, termed TimeReach index, that exploits the fact that most real-world graphs contain large strongly connected components. Finally, we present an experimental evaluation of all approaches, for dierent graph sizes, historical query types and time granularities.

The small world phenomenon is a desirable property of social networks, since it guarantees short paths between the nodes of the social graph and thus efficient information spread on the network. It is thus in the benefit of both network users and network owners to enforce and maintain this property. In this work, we study the problem of finding a subset of k edges from a set of candidate edges whose addition to a network leads to the greatest reduction in its average shortest path length. We formulate the problem as a combinatorial optimization problem, and show that it is NP-hard and that known approximation techniques are not applicable. We describe an efficient method for computing the exact effect of a single edge insertion on the average shortest path length, as well as several heuristics for efficiently estimating this effect. We perform experiments on real data to study the performance of our algorithms in practice.

Recently, result diversification has attracted a lot of attention as a means to improve the quality of results retrieved by user queries. In this article, we introduce a novel definition of diversity called DisC diversity. Given a tuning parameter r , which we call radius, we consider two items to be similar if their distance is smaller than or equal to r . A DisC diverse subset of a result contains items such that each item in the result is represented by a similar item in the diverse subset and the items in the diverse subset are dissimilar to each other. We show that locating a minimum DisC diverse subset is an NP-hard problem and provide algorithms for its approximation. We extend our definition to the multiple radii case, where each item is associated with a different radius based on its importance, relevance, or other factors. We also propose adapting DisC diverse subsets to a different degree of diversification by adjusting r , that is, increasing the radius (or zooming-out) and decreasing the radius (or zooming-in). We present efficient implementations of our algorithms based on the M-tree, a spatial index structure, and experimentally evaluate their performance.

Result diversification has recently attracted considerable attention as a means of increasing user satisfaction in recommender systems, as well as in web and database search. In this paper, we focus on the problem of selecting the k-most diverse items from a result set. Whereas previous research has mainly considered the static version of the problem, in this paper, we exploit the dynamic case in which the result set changes over time, as for example, in the case of notification services. We define the CONTINUOUS k-DIVERSITY PROBLEM along with appropriate constraints that enforce continuity requirements on the diversified results. Our proposed approach is based on cover trees and supports dynamic item insertion and deletion. The diversification problem is in general NP-hard; we provide theoretical bounds that characterize the quality of our cover tree solution with respect to the optimal one. Since results are often associated with a relevance score, we extend our approach to account for relevance. Finally, we report experimental results concerning the efficiency and effectiveness of our approach on a variety of real and synthetic datasets.

The ten papers included in this special section were presented at the 28th International Conference on Data Engineering was held in Washington, DC, on April 1-5, 2012. All papers were revised and substantially extended, over their conference versions and went through a rigorous review process to ensure the high quality standards of the IEEE Transactions on Knowledge and Data Engineering. They cover a broad range of topics highlighting the liveliness of the data engineering field.

To assist users in database exploration, we present the YmalDB system, a database system enhanced with a recommendation functionality. Along with the results of each user query, YmalDB computes and presents to the users additional results, called Ymal (i.e., "You May Also Like") results, that are highly related with the results of their original query. Such results are computed using the most interesting sets of attribute values, called faSets, that appear either in the results of the original query or in the results of an appropriately expanded one. The interestingness of a faSet is based on its frequency both in the query result and in the database.

Search result diversification has attracted considerable attention as a means of improving the quality of results retrieved by user queries. In this demonstration, we present Poikilo, a tool to assist users in locating and evaluating diverse results. We provide implementations of a wide suite of models and algorithms to compute and compare diverse results. Users can tune various diversification parameters, combine diversity with relevance and also see how diverse results change over time in the case of streaming data.

Result diversification has recently attracted considerable attention as a means of increasing user satisfaction in recommender systems, as well as in web and database search. In this paper, we focus on the problem of selecting the k-most diverse items from a result set. Whereas previous research has mainly considered the static version of the problem, in this paper, we exploit the dynamic case in which the result set changes over time, as for example, in the case of notification services. We define the Continuous k-Diversity Problem along with appropriate constraints that enforce continuity requirements on the diversified results. Our proposed approach is based on cover trees and supports dynamic item insertion and deletion. The diversification problem is in general NP-complete; we provide theoretical bounds that characterize the quality of our solution based on cover trees with respect to the optimal solution. Finally, we report experimental results concerning the efficiency and effectiveness of our approach on a variety of real and synthetic datasets.

Recently, result diversification has attracted a lot of attention as a means to improve the quality of results retrieved by user queries. In this paper, we propose a new, intuitive definition of diversity called DisC diversity. A DisC diverse subset of a query result contains objects such that each object in the result is represented by a similar object in the diverse subset and the objects in the diverse subset are dissimilar to each other. We show that locating a minimum DisC diverse subset is an NP-hard problem and provide heuristics for its approximation. We also propose adapting DisC diverse subsets to a different degree of diversification. We call this operation zooming. We present efficient implementations of our algorithms based on the M-tree, a spatial index structure, and experimentally evaluate their performance.

Typically, users interact with database systems by formulating queries. However, many times users do not have a clear understanding of their information needs or the exact content of the database, thus, their queries are of an exploratory nature. In this paper, we propose assisting users in database exploration by recommending to them additional items that are highly related with the items in the result of their original query. Such items are computed based on the most interesting sets of attribute values (or faSets) that appear in the result of the original user query. The interestingness of a faSet is defined based on its frequency both in the query result and in the database instance. Database frequency estimations rely on a novel approach that employs an e-tolerance closed rare faSets representation. We report evaluation results of the efficiency and effectiveness of our approach on both real and synthetic datasets.

The growth of online services has created the need for duplicate elimination in high-volume streams of events. The sheer volume of data in applications such as pay-per-click clickstream processing, RSS feed syndication and notification services in social sites such Twitter and Facebook makes traditional centralized solutions hard to scale. In this paper, we propose an approach based on distributed filtering. To this end, we introduce a suite of distributed Bloom filters that exploit different ways of partitioning the event space. To address the continuous nature of event delivery, the filters are extended to support sliding window semantics. Moreover, we examine locality-related tradeoffs and propose a tree-based architecture to allow for duplicate elimination across geographic locations. We cast the design space and present experimental results that demonstrate the pros and cons of our various solutions in different settings.

Preferences have been traditionally studied in philosophy, psychology, and economics and applied to decision making problems. Recently, they have attracted the attention of researchers in other fields, such as databases where they capture soft criteria for queries. Databases bring a whole fresh perspective to the study of preferences, both computational and representational. From a representational perspective, the central question is how we can effectively represent preferences and incorporate them in database querying. From a computational perspective, we can look at how we can efficiently process preferences in the context of database queries. Several approaches have been proposed but a systematic study of these works is missing. The purpose of this survey is to provide a framework for placing existing works in perspective and highlight critical open challenges to serve as a springboard for researchers in database systems. We organize our study around three axes: preference representation, preference composition, and preference query processing.

Keyword-based search in relational databases allows users to discover relevant information without knowing the database schema or using complicated queries. However, such searches may return an overwhelming number of results, often loosely related to the user intent. In this paper, we propose personalizing keyword database search by utilizing user preferences. Query results are ranked based on both their relevance to the query and their preference degree for the user. To further increase the quality of results, we consider two new metrics that evaluate the goodness of the result as a set, namely coverage of many user interests and content diversity. We present an algorithm for processing preference queries that uses the preferential order between keywords to direct the joining of relevant tuples from multiple relations. We then show how to reduce the complexity of this algorithm by sharing computational steps. Finally, we report evaluation results of the efficiency and effectiveness of our approach.

This tutorial provides an overview of the key research results in the area of user preferences from a database perspective. The objective is to survey in a systematic and holistic way a number of approaches for preference representation and composition, querying with preferences and preference learning. Open research problems are also presented.

In this paper, we address the problem of database selection for XML document collections, that is, given a set of collections and a user query, how to rank the collections based on their goodness to the query. Goodness is determined by the relevance of the documents in the collection to the query.

The appropriate deployment of web service operations at the service provider site plays a critical role in the efficient provision of services to clients. In this paper, the authors assume that a service provider has several servers over which web service operations can be deployed. Given a workflow of web services and the topology of the servers, the most efficient mapping of operations to servers must then be discovered. Efficiency is measured in terms of two cost functions that concern the execution time of the workflow and the fairness of the load distribution among the servers. The authors study different topologies for the workflow structure and the server connectivity and propose a suite of greedy algorithms for each combination.

Due to the structural heterogeneity of XML, queries are often interpreted approximately. This is achieved by relaxing the query and ranking the results based on their relevance to the original query. Query relaxation over distributed XML repositories may incur large communication costs, since partial result lists from different sites need to be gathered and ranked to assembly the overall top-k results. To process such queries efficiently, we propose using a distributed clustered index to group documents based on their structural similarity. The clustered index proves to be very effective in reducing the sizes of the partial lists that need to be combined. Furthermore, it can be used as the basis of a pay-as-you-go approach, where clusters of documents are accessed gradually providing the user with increasingly improving results. To reduce the cost of constructing and maintaining the clustered index, we use a compact data structure that trades-off accuracy for storage and communication efficiency. The index is also used for selectivity estimation so that query relaxation is geared towards the most promising structural transformations. Our experimental results show that our approach significantly reduces the communication cost for retrieving the top-k results, while maintaining a low construction cost for the clustered index.

In many large-scale content sharing applications, participants or peers are grouped together forming clusters based on their content or interests. In this paper, we deal with the maintenance of such clusters in the presence of updates. We model the evolution of the system as a strategic game, where peers determine their cluster membership based on a utility function of the query recall. Peers are guided either by selfish or altruistic motives: selfish peers aim at improving the recall of their own queries, whereas altruistic peers aim at improving the recall of the queries of other peers. We study the evolution of such clusters both theoretically and experimentally under a variety of conditions. We show that, in general, local decisions made independently by each peer enable the system to adapt to changes and maintain the overall recall of the query workload.

To provide users with only relevant data from the huge amount of available information, personalization systems utilize preferences to allow users to express their interest on specific pieces of data. Most often, user preferences vary depending on the circumstances. For instance, when with friends, users may like to watch thrillers, whereas, when with their kids, they may prefer to watch cartoons. Contextual preference systems address this challenge by supporting preferences that depend on the values of contextual attributes such as the surrounding environment, time or location. In this paper, we address the problem of finding interesting data items based on contextual preferences that assign interest scores to pieces of data based on context. To this end, we propose a number of pre-processing steps. Instead of pre-computing scores for all data items under all potential context states, we exploit the hierarchical nature of context attributes to identify representative context states. Furthermore, we introduce a method for grouping preferences based on the similarity of the scores that they produce. This method uses a bitmap representation of preferences and scores with various levels of precision that lead to approximate rankings with different degrees of accuracy. We evaluate our approach using both real and synthetic data sets and present experimental results showing the quality of the scores attained using our methods.

Supporting top-k queries over distributed collections of schemaless XML data poses two challenges. While XML supports expressive query languages such as XPath and XQuery, these languages require schema knowledge so as to write an appropriate query which may not be available in distributed systems with autonomous and dynamic sources. Thus, there is a need for approximate query processing. Furthermore, retrieving the top-k results incurs large communication and processing cost, since partial result lists from numerous sites need to be combined and ranked to assembly the top-k answers. To address both of these issues, we present an approach for approximate XPath processing over distributed collections of XML data based on a clustered path index, where data is grouped based on structural information. Our method gradually generalizes a query by applying a set of structural transformations to it and the retrieved results are ranked based on the edit distance between two path expressions. A compact indexing data structure is used to reduce the index construction cost. Our experimental results show that our approach significantly reduces the communication cost for retrieving the top-k results, while maintaining a low construction cost for the clustered index.

Motivated by the fact that XML is increasingly being used in distributed applications, we propose building a cooperative caching scheme for XML documents. Our scheme allows sharing cache content among a number of peers. To facilitate sharing, a distributed prefix-based index is built based on the queries whose results are cached. In the loosely-coupled sharing approach, each peer stores in its local cache results of its own queries and just publishes the associated queries to the index. In the tightly-coupled approach, each peer is assigned a specific part of the query space and stores in its local cache the results of the corresponding queries. Both approaches result in a dynamic organization of content that evolves over time based on the query load, the number of peers and the overall storage available. We present a number of associated design choices such as using a DHT for distributing the prefix-based index and a proactive cache replacement policy. We also report on a number of experiments that show the benefits of cooperative caching and highlight the pros and cons of loosely and tightly coupled cache sharing.

To handle the overwhelming amount of information currently available, personalization systems allow users to specify the information that interests them through preferences. Most often, users have different preferences depending on context. In this paper, we introduce a model for expressing such contextual preferences. Context is modeled as a set of multidimensional attributes. We formulate the context resolution problem as the problem of (a) identifying those preferences that qualify to encompass the context state of a query and (b) selecting the most appropriate among them. We also propose an algorithm for context resolution that uses a data structure, called the profile tree, that indexes preferences based on their associated context. Finally, we evaluate our approach from two perspectives: usability and performance.

Personalization systems exploit preferences for providing users with only relevant data from the huge volume of information that is currently available. We consider preferences that dependent on context, such as the location of the user. We model context as a set of attributes, each taking values from hierarchical domains. Often, the context of the query may be too specific to match any of the given preferences. In this paper, we consider possible expansions of the query context produced by relaxing one or more of its context attributes. A hierarchical attribute may be relaxed upwards by replacing its value by a more general one, downwards by replacing its value by a set of more specific values or sideways by replacing its value by sibling values in the hierarchy. We present an algorithm based on a prefix-based representation of context for identifying the preferences whose context matches the relaxed context of the query and some initial performance results.

Peer-to-peer(p2p) systems over an efficient means of data sharing among a dynamically changing set of a large number of a tonomous nodes.Each node in a p2p system is connected with a small number of other nodes thus creating an overlay network of nodes. A query posed at a node is routed through the overlay network towards nodes hosting data items that satisfy it. In this paper, we consider building overlays that exploit the query workload so that nodes are clustered based on their results to a given query workload. The motivation is to create overlays where nodes that match a large number of similar queries are a fewlinks apart. Query frequency is also taken into account so that popular queries have a greater effect on the formation of the overlay than unpopular ones. We focus on range selection queries and se histograms to estimate the query results of each node. Then, nodes are clustered based on the similarity of their histograms. To this end,we introd ce a workload-aware edit distance metric between histograms that takes into account the query workload. Our experimental results show that workload-aware overlays increase the percentage of query results returned for a given number of nodes visited as compared to both random (i.e., unclustered)overlays and non workload-aware clustered overlays (i.e., overlays that cluster nodes based solely on the nodes' content).

In this paper, we consider semantic service discovery in a global computing environment. We propose creating a dynamic overlay network by grouping together semantically related services. Each such group of services is termed a community. Communities are organized in a global taxonomy whose nodes are related contextually. The taxonomy can be seen as an expandable distributed semantic index over the system services, which aims at improving service discovery. Our performance results indicate that in certain cases, our service discovery mechanism outperforms even the case in which service indexes are fully replicated at all system sites.

Broadcasting provides an efficient means for disseminating information in both wired and wireless settings, especially for popular data items. Multiversion (MV) data broadcast, i.e., data broadcast in which more than one value is broadcast per data item, has the advantage of allowing more client transactions to read consistent data and complete their operation successfully. Naturally, the MV broadcast can satisfy both historical queries in which a client accesses many versions of the same data item and snapshot queries in which a client accesses different data items of the same version. Furthermore, multiple versions increase clients' tolerance to network disconnections that are common in wireless communications. In this paper, we expand our previous work on MV broadcasts to support efficient selective tuning. Selective tuning is important for energy constraint mobile devices since it enables the client to be active only when data of interest appear on the broadcast. The rest of the time the client stays in doze mode with its antenna powered down. In its simplest form, we adopt (1,1)-Indexing and organize multiversion data in buckets, so that the average energy consumption is significantly reduced while minimally affecting the average access time.

Together with wireless communication technologies, portable computers and hand-held devices provide a pervasive base for mobile computing. Mobile computing involves mobility of users, hardware, software and data. In addition to advances in communications and hardware, mobile and wireless access requires innovative theories and paradigms in data management and new data engineering techniques in order to cope with the inherent limitations of the mobile environment while satisfying the users’ new expectations and needs. This seminar aims at covering such data engineering aspects along two dimensions: (a) the wireless network perspective, and (b) the information processing perspective. Thus, this seminar provides a good overview of current methods and practices in building mobile information systems, examine mobile and wireless infrastructures and discuss challenging research problems in all aspects of mobile information processing.

We propose a novel approach to shape-based image retrieval that builds upon a similarity criterion which is based on the average point set distance. Compared to traditional techniques, such as dimensionality reduction, our method exhibits better behavior in that it maintains the average topology of shapes independently of the number of points used to represent them and is more resilient to noise. An efficient algorithm is presented based on an incremental "fattening," of the query shape until the best match is discovered. The algorithm uses simplex range search techniques and fractional cascading to provide an average polylogarithmic time complexity on the total number of shape vertices. The algorithm is extended to perform additional fast approximate matching, when there is no image sufficiently similar to the query image. We present techniques for the efficient external storage of the shape base and of the auxiliary geometric data structures used by the algorithm. Finally, we show how our approach can be used for processing queries, containing pairwise relations of object boundaries such as contain, tangent, and overlap. Such queries are either extracted from some user drafted sketch or defined explicitly by the user. Alternative methods are presented for forming query execution plans.

Given the undeniable popularity of the Web, providing efficient and secure access to remote databases using a Web browser is crucial for the emerging cooperative information systems and applications. In this paper, we evaluate all currently available Java-based approaches that support persistent connections between Web clients and database servers. These approaches include Java applets, Java Sockets, Servlets, Remote Method Invocation, CORBA, and mobile agents technology. Our comparison is along the dimensions of performance and programmability. Our findings point out that best performance is not always achievable with high programmability and low resource requirements. Moreover, the mobile agent technology needs to improve its programmability while giving particular emphasis on its infrastructure.

In current distributed systems, the notion of mobility is emerging in many forms and applications. Mobility arises naturally in wireless computing since the location of users changes as they move. Besides mobility in wireless computing, software mobile agents are another popular form of moving objects. Locating objects, i.e., identifying their current location, is central to mobile computing. We present a comprehensive survey of the various approaches to the problem of storing, querying, and updating the location of objects in mobile computing. The fundamental techniques underlying the proposed approaches are identified, analyzed, and classified along various dimensions.

Summary form only given, as follows. We are in the midst of a wireless and mobile revolution. In the near future, a typical computing environment - business, personal, scientific or educational - will provide wireless network connectivity between powerful data servers and mobile, sometimes disconnected, computers and devices. This has created exciting opportunities for developing a wide range of innovative database applications and systems. However, an open question remains: What kind of system will be capable of offering scalable data services and exhibit scalable performance? Besides advances in communications and hardware, does achieving pervasive mobile computing require innovative theories and paradigms in data management or new data engineering techniques? The objective of this tutorial is to provide an answer to the above questions by presenting the current state-of-the-research and contrasting it with the state-of-the-practice. Towards this, it will provide an overview of the commercial-state-of-the-art for supporting mobile database access and present a summary of the significant research advances in theories and techniques for mobile and wireless data access. It will also discuss some future directions in the context of pervasive and invisible computing applications.

The popularity of the Web as a universal access mechanism for network information has created the need for developing Web-based DBMS client/server applications. However, the current commercial applet-based approaches for accessing database systems offer limited flexibility, scalability, and robustness. We propose a new framework for Web-based distributed access to database systems based on Java-based mobile agents. The framework supports lightweight, portable, and autonomous clients as well as operation on slow or expensive networks. The implementation of the framework using the aglet workbench shows that its performance is comparable to, and in some case outperforms, the current approach. In fact, in wireless and dial-up environments and for average size transactions, a client/agent/server adaptation of the framework provides a performance improvement of approximately a factor of ten. For the fixed network, the gains are about 40 percent and 30 percent, respectively. We expect our framework to perform even better when deployed using different implementation platforms as indicated by our preliminary results from an implementation based on Voyager.

The popularity of the Web as a universal access mechanism for network information has created the need for developing Web based DBMS client/server applications. However, the current commercial applet based methodologies for accessing database systems offer limited flexibility, scalability and robustness. We propose a new framework for Web based distributed access to database systems based on Java based mobile agents. The framework supports lightweight, portable and autonomous clients as well as operation on slow or expensive networks. The implementation of the framework shows that its performance is comparable to, and in some cases outperforms, the current approach. In fact, in wireless and dial-up environments and for average size transactions, a client/agent/server adaptation of the framework provides a performance improvement of approximately a factor of ten. For the fixed network, the gains are about 40% and 30% respectively.

Mobile computing introduces a new form of distributed computation in which communication is most often intermittent, low-bandwidth, or expensive, thus providing only weak connectivity. We present a replication scheme tailored for such environments. Bounded inconsistency is defined by allowing controlled deviation among copies located at weakly connected sites. A dual database interface is proposed that in addition to read and write operations with the usual semantics supports weak read and write operations. In contrast to the usual read and write operations that read consistent values and perform permanent updates, weak operations access only local and potentially inconsistent copies and perform updates that are only conditionally committed. Exploiting weak operations supports disconnected operation since mobile clients can employ them to continue to operate even while disconnected. The extended database interface coupled with bounded inconsistency offers a flexible mechanism for adapting replica consistency to the networking conditions by appropriately balancing the use of weak and normal operations. Adjusting the degree of divergence among copies provides additional support for adaptivity. We present transaction-oriented correctness criteria for the proposed schemes, introduce corresponding serializability-based methods, and outline protocols for their implementation. Then, some practical examples of their applicability are provided. The performance of the scheme is evaluated for a range of networking conditions and varying percentages of weak transactions by using an analytical model developed for this purpose.

To accommodate the increase in user population in future personal communication systems, hierarchical architectures of location databases have been proposed. In this paper, a scheme based on forwarding pointers is presented, that reduces the cost of the overall network and database traffic generated by frequent location updates in such hierarchical architectures. To reduce the number of forwarding pointers that need to be traversed to locate a user, auxiliary caching techniques are presented. Various conditions for purging the chain of forwarding pointers and updating the database are also introduced. Special care is given so that the scheme correctly supports the concurrent execution of updates and lookups. The applicability of the scheme and the performance of the caching techniques are demonstrated through a number of experiments for a range of call to mobility ratios and for a variety of moving and calling behaviors. 1 Introduction Advances in wireless telecommunications and in t...

It is expected that in the near future, tens of millions of users will have access to distributed information systems through wireless connections. The technical characteristics of the wireless medium and the resulting mobility of both data resources and data consumers raise new challenging questions regarding the development of information systems appropriate for mobile environments. In this paper, we report on the development of such a system. First, we describe the general architecture of the information system and the main considerations of our design. Then, based on these considerations, we present our system support for maintaining the consistency of replicated data and for providing transaction schemas that account for the frequent but predictable disconnections, the mobility, and the vulnerability of the wireless environment.