In this paper, we investigate a novelInfluencePersistenceMaximization (InfPM) problem in temporal social networks. Given a temporal graph, InfPM aims to identify a fixed seed node set$S$that maximizes the total duration of persistent influence across consecutive snapshots. After proving that InfPM is NP-hard, monotonic, and non-submodular, we develop two efficient solutions: (1) RevG, a reverse greedy algorithm that iteratively removes low-contribution nodes, and (2) LRep, a replacement-based method that progressively improves the quality of seed node set. To accelerate influence computation in RevG and LRep, we propose a new influence computation method integrating snapshot compression, probability-aware sampling, and a specialized influence estimator offering unbiased estimation. Additionally, we explore a practical variant of InfPM, termed Win-InfPM, which relaxes the requirement of consecutive snapshots by introducing a flexible time window model. Extensive experiments on seven real-world networks demonstrate that (1) RevG and LRep effectively identify high-quality seed nodes, achieving up to 100% improvement in total influence persistence over the baselines; and (2) the proposed influence computation method improves the efficiency of RevG and LRep by up to 400%, while maintaining comparable influence persistence.

In this paper, we investigate the Time-aware Influence Minimization (TIMIN) problem in social networks, focusing on minimizing negative influence concerning a critical deadline by temporarily blocking specific nodes in the given social network. First, we introduce the Temporal Linear Threshold (TLT) model, a novel framework that incorporates time delay in influence propagation, the decay of influence power over time, and the lifecycle of influence. Building on this model, we formally define the Timin problem and prove its NP-hardness, monotonicity, and supermodularity. To tackle the Timin problem, we develop the Timin-Greedy, a greedy algorithm that achieves$(1\ -1/e)$approximation. Since exact computation of negative influence spread for any node set in Timin-Greedy is #P-hard, we propose TESTIM, a scalable implementation that provides$(1-1/e-\epsilon)$approximation. To further enhance the efficiency, we introduce NReplacer, a heuristic algorithm leveraging the insight that potential blocking nodes often cluster near the negative source. Our extensive experimental evaluations demonstrate several key findings: (1) TESTIM is up to 10× faster than the baselines while achieving 30%–50% more reductions in negative influence spread, and (2) NReplacer exhibits a 5× speedup compared to TESTIM, with comparable reductions in negative influence spread.

In this paper, we address a novel problem in social network analysis: the Most Influenced Community Search (MICS). Given a graph and a seed node set$S$, the MICS problem seeks to identify a densely connected sub graph that is most significantly impacted by$S$. We formally define MICS, prove its NP-hardness, and show that constant-factor approximation is not feasible. To solve MICS efficiently, we propose a two-phase framework. In the first phase, we compute the influenced expectation for each node, representing its likelihood of being influenced by$S$. We develop two algorithms: S-InfExp, a sampling-based method with theoretical guarantees, and L-InfExp, a learning-based approach for faster predictions. In the second phase, we introduce two algorithms, GlobalSearch and LocalSearch, to find the most influenced community. GlobalSearch uses a top-down, greedy approach, while LocalSearch applies a bottom-up strategy. Experiments on eight real-world datasets demonstrate that (1) L-InfExp is up to 100× faster than S-InfExp with comparable accuracy, (2) LocalSearch is 10× faster than GlobalSearch, with both algorithms effectively identifying the community with the highest influenced expectations, and (3) our algorithms outperform all baselines.

The$\eta$-threshold decomposition in uncertain graphs, which calculates the$\eta$-thresholds for each vertex, is a fundamental problem for graph analysis. While existing studies on$\eta$-threshold decomposition primarily focus on static uncertain graphs, numerous real-world scenarios involve highly dynamic uncertain graphs. It is costly to recompute all$\eta$-thresholds from scratch whenever the uncertain graphs face update operations, e.g., edge insertion and deletion, and the modifications on edge probability. Motivated by this, we introduce efficient$\eta$-threshold maintenance algorithms tailored for dynamic uncertain graphs in this paper. Firstly, we investigate the impact of edge insertion and deletion on$\eta$-thresholds. Building upon this analysis, we introduce the maintenance algorithms designed to adjust the$\eta$thresholds for edge insertions or deletions within the uncertain graphs. Our approaches involve identifying a compact subgraph encompassing all vertices necessitating$\eta$-threshold updates, followed by an iterative process of vertex deletion to complete the$\eta$-threshold updates. To improve the efficiency, we devise three optimizations to further reduce the number of candidate$\eta$-thresholds requiring adjustment. Moreover, we extend the proposed algorithms to handle the$\eta$-threshold maintenance for edge probability change. Extensive experiments on both real and synthetic datasets demonstrate the efficiency of the proposed algorithms. The results reveal that our proposed algorithms consistently outperform the baselines, exhibiting improvements ranging from at least three orders of magnitude to as high as seven orders of magnitude.

Given a directed graph$G$and two non-negative integers$k$and$l$, a D-core, or ($k$, l)-core, is the maximal subgraph$H\subseteq G$where each vertex in$H$has an in-degree and out-degree not smaller than$k$and$I$, respectively. D-cores have found extensive applications, such as social network analysis, fraud detection, and graph visualization. In these applications, graphs are highly dynamic and frequently updated with the insertions and deletions of vertices and edges, making it costly to recompute the D-cores from scratch to handle the updates. In the literature, the peeling-based algorithm has been proposed to handle D-core maintenance. However, the peeling-based method suffers from efficiency issues, e.g., it may degenerate into recomputing all the D-cores and is inefficient for batch updates due to sequential processing. To address these limitations, we introduce novel algorithms for incrementally maintaining D-cores in dynamic graphs. We begin by presenting the theoretical findings to identify the D-cores that should be updated. By leveraging these theoretical analysis results, we propose a local-search-based algorithm with optimizations to handle single-edge insertions and deletions. We further propose an H-index-based algorithm for scenarios involving batch updates. Several novel edge-grouping strategies are proposed to improve the efficiency of the H-index-based algorithm. Extensive empirical evaluations over both real-world and synthetic networks demonstrate that our proposed algorithms are up to 5 orders of magnitude faster than the peeling-based method.

An average person usually contains more than 10 trillion human cells, and each cell's transcriptome can be profiled by a single-cell RNA sequence (scRNA-seq). The huge volume and high complexity of scRNA-seq data put challenges on fundamental tasks of scRNA-seq data analysis, i.e., cell type identification and new cell type discovery. In this paper, we demonstrate scRAG, which can efficiently remove batch effect in cell-type identification and enable reliable new cell discovery, facilitated by GPU-based scRNA-seq data management and Large Language Models (LLMs). The GPU-based scRNA-seq data management enables high throughput scRNA-seq data retrieval and update, while the LLM utilizes the retrieval results to remove the batch effect and discover novel cells. We demonstrate scRAG for its: (a) interfaces, (b) GPU-based scRNA-seq data management, and (c) applications in batch effect removal and cancer cell discovery.

In directed graphs, the relationship between users is asymmetric, resulting in two types of triangles: cycle triangles and flow triangles. This paper studies the problem of privacy-preserving triangle counting in directed graphs. Based on different applications, we consider two scenarios, i.e., trusted and untrusted servers. In the literature, privacy-preserving triangle counting in undirected graphs has been widely studied. However, directly applying these algorithms to address our problem suffers from many issues. Concretely, for the trusted server scenario, the differentially private triangle counting algorithms, designed for undirected graphs, exhibit suboptimal performance when applied to directed graphs. Hence, we propose a new centralized differentially private algorithm that adds Laplacian noise to the exact numbers by analyzing global sensitivity. Furthermore, for the untrusted server scenario, the existing techniques cannot be used to count cycle and flow triangles with differential privacy because the local view of each user in directed graphs is limited to out-neighbors rather than all neighbors. Therefore, we design a novel locally differentially private algorithm to provide local unbiased estimation, which implies that after aggregating all the local estimations on the central server side, an unbiased estimation for the numbers of cycle and flow triangles is deduced. Empirical experiments on six real-world graph datasets demonstrate that our proposed algorithms achieve high efficiency and utility.

In this paper, we investigate a new problem of truss-based why-not community search. Given a k-truss community C in a graph G and a why-not vertex w ∉ C, the goal is to insert the minimum number of new edges into G to ensure that w becomes part of the k-truss community. This problem has a wide range of applications, such as friends recommendation and transportation planning. We prove that the truss-based why-not community search problem is NP-hard and propose two efficient heuristic algorithms: the expansion-based algorithm and the simulation-based algorithm. Specifically, the expansion-based algorithm incrementally inserts the edges one by one, guided by a carefully designed edge goodness function that quantifies edge quality to ensure optimal selection. In contrast, the simulation-based algorithm firstly inserts a sufficient number of edges into G to immediately include w in a k-truss community and then removes redundant edges to minimize insertions. Furthermore, we implement a set of optimizations to further enhance the efficiency of both algorithms. Extensive experiments on real-world graphs demonstrate the efficiency and effectiveness of our proposed methods and optimizations.

Community search is a fundamental problem in graph analysis and has attracted much attention for its ability to discover personalized communities. In this paper, we focus on community search over multilayer graphs. We design a novel cohesive subgraph model called synergetic core for multilayer graphs, which requires both local and global cohesiveness. Specifically, the synergetic core mandates that the vertices within the subgraph are not only densely connected on some individual layers but also form more cohesive connections on the projected graph that considers all layers. The local and global cohesiveness collectively ensure the superiority of the synergetic core. Based on this new model, we formulate the problem of synergetic community search. To efficiently retrieve the community, we propose two algorithms. The first is a progressive search algorithm, which enumerates potential layer combinations to compute the synergetic core. The second is a trie-based search algorithm , leveraging our novel index called dominant layers-based trie (DLT). DLT compactly stores synergetic cores within the trie structure. By traversing the DLT, we can efficiently identify the synergetic core. We conduct extensive experiments on ten real-world datasets. Experimental results demonstrate that (1) the synergetic core can find communities with the best quality among the state-of-the-art models, and (2) our proposed algorithms are up to five orders of magnitude faster than the basic method.

Nowadays, geo-textual data, which consists of both spatial and textual information, have become increasingly preva-lent. The location-based services are ubiquitous in daily life to help users find desirable geo-textual objects. For example, spatial keyword queries return the geo-textual objects that are the most relevant to query location and query keywords. However, entering complete queries (e.g., the query keywords) can be cumbersome and prone to errors. To overcome these limitations, we present a real-time query system called TASKS for instant error-tolerant spatial keyword queries on road networks. TASKS not only returns the results as soon as users type in some characters instead of a complete keyword, but also tolerates typographical errors of input keywords and supports the queries over road networks. We have implemented four modules for TASKS, i.e., Index Module, Query Module, Update Module, and Route Module. In this demonstration, participants will be invited to use TASKS to explore geo-textual objects and routes in a “search-as-you-type” manner.

Top-k sparsification has recently been widely used to reduce the communication volume in distributed deep learning. However, due to the Sparse Gradient Accumulation (SGA) dilemma, the performance of top-k sparsification still has limitations. Recently, a few methods have been put forward to handle the SGA dilemma. Regrettably, even the state-of-the-art method suffers from several drawbacks, e.g., it relies on an inefficient communication algorithm and requires extra transmission steps. Motivated by the limitations of existing methods, we propose a novel efficient sparse communication framework, called SparDL. Specifically, SparDL uses the Spar-Reduce-Scatter algorithm, which is based on an efficient Reduce-Scatter model, to handle the SGA dilemma without additional communication operations. Besides, to further reduce the latency cost and improve the efficiency of SparDL, we propose the Spar-All-Gather algorithm. Moreover, we propose the global residual collection algorithm to ensure fast convergence of model training. Finally, extensive experiments are conducted to validate the superiority of SparDL.

Core models are well-known cohesive subgraph models for graph analytics that have been extensively studied. These models, including (α, β)-core, (k, l)-core, and k -core, have multiple parameters, which are referred to as multi-dimensional cores. The goal of core search is to retrieve subgraphs from a graph that satisfy the semantics of a given core model. In the literature, various indexes have been proposed to accelerate core search for different core models. However, existing indexes suffer from several limitations, such as significant redundancy, lack of scalability with respect to the number of parameters, limited generality, and inadequate consideration of index maintenance. To address these limitations, in this paper, we thoroughly investigate the problem of multi-dimensional core search. In particular, we propose a novel index called MCR-Tree, which can be applied to different core models. The MCR-Tree projects all vertices into a multi-dimensional space by leveraging the skyline corenesses, which are indexed by an R-tree. Furthermore, the MCR-Tree integrates the connectivity information of subgraphs into the nodes of the R-tree to facilitate multi-dimensional core search. Subsequently, an efficient branch-and-bound algorithm is designed to perform multi-dimensional core search by traversing the MCR-Tree. Additionally, we discuss how to maintain the MCR-Tree for graph updates. Extensive experiments demonstrate that the MCR-Tree is up to two orders of magnitude smaller than existing indexes and the MCR-Tree-based core search method is up to an order of magnitude faster than existing algorithms.

Community search aims to retrieve dense subgraphs that contain the query vertices. While many effective community models and algorithms have been proposed in the literature, none of them address the unique challenges posed by streaming graphs, where edges are continuously generated over time. In this paper, we investigate the problem of truss-based community search over streaming directed graphs. To address this problem, we first present a peeling-based algorithm that iteratively removes edges that do not meet the support constraints. To improve the efficiency of the peeling-based algorithm, we propose three optimizations that leverage the time information of the streaming graph and the structural information of trusses. As the peeling-based algorithm may suffer from inefficiency when the input peeling graph is large, we further propose a novel order-based algorithm that preserves the community by maintaining the deletion order of edges in the peeling algorithm. Extensive experimental results on real-world datasets show that our proposed algorithms outperform the baseline by up to two orders of magnitude in terms of throughput.

(α, β)-core is an important cohesive subgraph model for bipartite graphs. Given a bipartite graph G, the problem of (α, β)-core decomposition is to compute non-empty (α, β)-cores for all possible values of α and β. The state-of-the-art (α, β)-core decomposition algorithm is a peeling-based algorithm, which iteratively deletes the vertex from high degree to low degree. However, as the peeling-based algorithm is designed for centralized environments, it cannot be applied to distributed environments, where graphs are partitioned and stored in different machines. Motivated by this, in this paper, we study the distributed (α, β)-core decomposition problem, aiming to develop new algorithms to support (α, β)-core decomposition in distributed environments. To this end, first, we analyze the local properties of (α, β)-core, and devise n-order Bi-indexes for the vertex, which are iteratively defined using the vertex neighbors’ (n − 1)-order Bi-indexes. Next, we propose an algorithm for (α, β)-core decomposition through iteratively calculating n-order Bi-indexes for every vertex. To further improve the efficiency of the algorithm, we propose two optimizations. Then, we extend our proposed algorithms to different distributed graph processing frameworks to make them run in distributed environments. Finally, extensive experimental results on both real and synthetic bipartite graphs demonstrate the efficiency of our proposed algorithms.

K-truss is a useful notion of dense subgraphs, which can represent cohesive parts of a graph in a hierarchical way. In practice, in order to enable various truss-based applications to answer queries faster, the edge trussnesses are computed in advance. However, real-world graphs may not always be static and often have edges inserted or removed, leading to costly truss maintenance of recomputing all edge trussnesses. In this paper, we focus on dynamic graphs with star insertions/deletions, where a star insertion can represent a newly joined user with friend connections in social networks or a recently published paper with cited references in citation networks. To tackle such star-based truss maintenance, we propose a new structure of AffBall based on the local structure of an inserted/deleted star motif. With AffBall, we make use of the correlation of inserted edges to compute the trussnesses of the inner edges surrounding the star. Then, we analyze the onion layer of k-truss and conduct truss maintenance for the edges beyond the star, which can be efficiently achieved with a time complexity related to the number of the edges that change the onion layer. Moreover, we extend star-based truss maintenance to handle general updates and single-edge insertions/deletions. Extensive experiments on real-world dynamic graphs verify the effectiveness and efficiency of proposed algorithms against state-of-the-art truss maintenance algorithms.

Bipartite graphs characterize relationships between two different sets of entities, like actor-movie, user-item, and author-paper. The butterfly, a 4-vertices 4-edges (2,2)-biclique, is the simplest cohesive motif in a bipartite graph and is the fundamental component of higher-order substructures. Counting and enumerating the butterflies offer significant benefits across various applications, including fraud detection, graph embedding, and community search. While the corresponding motif, the triangle, in the unipartite graphs has been widely studied in both static and temporal settings, the extension of butterfly to temporal bipartite graphs remains unexplored. In this paper, we investigate the temporal butterfly counting and enumeration problem: count and enumerate the butterflies whose edges establish following a certain order within a given duration. Towards efficient computation, we devise a non-trivial baseline rooted in the state-of-the-art butterfly counting algorithm on static graphs, further, explore the intrinsic property of the temporal butterfly, and develop a new optimization framework with a compact data structure and effective priority strategy. The time complexity is proved to be significantly reduced without compromising on space efficiency. In addition, we generalize our algorithms to practical streaming settings and multi-core computing architectures. Our extensive experiments on 11 large-scale real-world datasets demonstrate the efficiency and scalability of our solutions.

Instant spatial keyword queries return the results as soon as users type in some characters instead of a complete keyword, which allow users to query the geo-textual data in a type-as-you-search manner. However, the existing methods of instant spatial keyword queries suffer from several limitations. For example, the existing methods do not consider the typographical errors of input keywords, and cannot be applied to the road networks. To overcome these limitations, in this paper, we propose a new query type, i.e., instant error-tolerant spatial keyword queries on road networks. To answer the queries efficiently, we present a framework, termed as Task, which consists of index component, query component, and update component. In the index component, we design a novel index called reverse 2-hop label based trie, which seamlessly integrates spatial and textual information for each vertex of the road network. Based on our proposed index, we devise efficient algorithms to progressively return and update the query results in the query component and update component, respectively. Finally, we conduct extensive experiments on real-world road networks to evaluate the performance of our presented Task. Empirical results show that our proposed index and algorithms are up to 1--2 orders of magnitude faster than the baseline.

Given a directed graph G and integers k and l , a D-core is the maximal subgraph H ⊆ G such that for every vertex of H , its in-degree and out-degree are no smaller than k and l , respectively. For a directed graph G , the problem of D-core decomposition aims to compute the non-empty D-cores for all possible values of k and l. In the literature, several peeling-based algorithms have been proposed to handle D-core decomposition. However, the peeling-based algorithms that work in a sequential fashion and require global graph information during processing are mainly designed for centralized settings, which cannot handle large-scale graphs efficiently in distributed settings. Motivated by this, we study the distributed D-core decomposition problem in this paper. We start by defining a concept called anchored coreness , based on which we propose a new H-index-based algorithm for distributed D-core decomposition. Furthermore, we devise a novel concept, namely skyline coreness , and show that the D-core decomposition problem is equivalent to the computation of skyline corenesses for all vertices. We design an efficient D-index to compute the skyline corenesses distributedly. We implement the proposed algorithms under both vertex-centric and block-centric distributed graph processing frameworks. Moreover, we theoretically analyze the algorithm and message complexities. Extensive experiments on large real-world graphs with billions of edges demonstrate the efficiency of the proposed algorithms in terms of both the running time and communication overhead.

A reverse top-k keyword-based location query returns the influence zone for the query object. Given a specified query object q, the influence zone of q varies for different key-word sets. Users may be interested in identifying the maximum influence zone of the query object. To this end, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. To address the MaxiZone problem, we propose three algorithms, including a basic algorithm, an index-centric algorithm together with a series of optimizations and a sampling-based algorithm. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of proposed algorithms.

Given a geo-textual dataset O, a set φ of keywords, a query object q ∈ O keyword-based location query returns the influence zoneRof q such that q belongs to the result of a top-k spatial keyword query with query keywords φ and any location inRas arguments. For a query object q, the influence zone of q varies for different keywords φ. Users may be interested in identifying the maximum influence zone of the query object. To this end, in this paper, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. A straightforward way to tackle the MaxiZone problem is to compute the influence zone for every candidate keyword set. Obviously, this is infeasible if there are a large number of candidate keyword sets. We propose a more efficient index-centric algorithm together with a series of optimizations as well as a sampling-based algorithm, to facilitate the query processing. Moreover, we extend the proposed algorithms to address a variant of MaxiZone problem called τ-MaxiZone problem, which finds top-τ keyword sets having the maximum influence zones. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of our proposed algorithms.

Attributed community search aims to find the community with strong structure and attribute cohesiveness from attributed graphs. However, existing works suffer from two major limitations: (i) it is not easy to set the conditions on query attributes; (ii) the queries support only a single type of attributes. To make up for these deficiencies, in this paper, we study a novel attributed community search called vertex-centric attributed community (VAC) search. Given an attributed graph and a query vertex set, the VAC search returns the community which is densely connected (ensured by the k-truss model) and has the best attribute score. We show that the problem is NP-hard. To answer the VAC search, we develop both exact and approximate algorithms. Specifically, we develop two exact algorithms. One searches the community in a depth-first manner and the other is in a best-first manner. We also propose a set of heuristic strategies to prune the unqualified search space by exploiting the structure and attribute properties. In addition, to further improve the search efficiency, we propose a 2-approximation algorithm. Comprehensive experimental studies on various realworld attributed graphs demonstrate the effectiveness of the proposed model and the efficiency of the developed algorithms.

Community search enables personalized community discovery and has wide applications in large real-world graphs. While community search has been extensively studied for undirected graphs, the problem for directed graphs has received attention only recently. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time. To address the limitations, in this paper, we systematically study the problem of community search over large directed graphs. We start by presenting a novel community model, called D-truss, based on two distinct types of directed triangles, i.e., flow triangle and cycle triangle. The D-truss model brings nice structural and computational properties and has many advantages in comparison with the existing models. With this new model, we then formulate the D-truss community search problem, which is proved to be NP-hard. In view of its hardness, we propose two efficient 2-approximation algorithms, named Global and Local, that run in polynomial time yet with quality guarantee. To further improve the efficiency of the algorithms, we devise an indexing method based on D-truss decomposition. Consequently, the D-truss community search can be solved upon the D-truss index without time-consuming accesses to the original graph. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.

Owing to the widespread use of location-aware devices and the increased popularity of micro-blogging applications, we are witnessing a rapid proliferation of geo-textual data. In this demonstration, we present iZone, an efficient system for determining influence zones over geo-textual data. Specifically, iZone allows users to browse geo-textual objects, evaluate the influence zones of specified geo-textual objects, and obtain explanations of the evaluation results. The iZone system adopts a browser-server model. The server side integrates two types of spatial keyword search, namely top-k spatial keyword query and reverse top-k keyword-based location query, to support the functionality of the system. A variety of spatial indexes are employed to enhance the efficiency of the system. The browser side provides a map-based GUI interface, which enables convenient and user-friendly interaction with the system. Using a real hotel dataset from Hong Kong, iZone offers hands-on experience with influence zone evaluation in real-life applications.

This paper explores the causality and responsibility problem (CRP) for the non-answers to probabilistic reverse skyline queries (PRSQ). Towards this, we propose an efficient algorithm called CP to compute the causality and responsibility for the non-answers to PRSQ. CP first finds candidate causes, and then, it performs verification to obtain actual causes with their responsibilities, during which several strategies are used to boost efficiency. Extensive experiments using both real and synthetic data sets demonstrate the effectiveness and efficiency of the presented algorithms.

We develop IS2R, an efficient interactive system for refining reverse top-k queries, to eliminate unexpected query results including (i) the absence of expected objects, (ii) the presence of unexpected objects, and (iii) the empty query result. The IS2R returns the refinement suggestions with the minimal costs based on penalty models. In this demonstration (available at https://youtu.be/GnSm4T9Uslk), we show different scenarios on how IS2R can be used to refine the original reverse top-k query, and verify its effectiveness and efficiency.

Causality and responsibility is an essential tool in the database community for providing intuitive explanations for answers/non-answers to queries. Causality denotes the causes for the answers/non-answers to queries, and responsibility represents the degree of a cause which reflects its influence on the answers/non-answers to queries. In this paper, we study the causality and responsibility problem (CRP) for the non-answers to probabilistic reverse skyline queries (PRSQ). We first formalize CRP on PRSQ, and then, we propose an efficient algorithm termed as CP to compute the causality and responsibility for the non-answers to PRSQ. CP first finds candidate causes, and then, it performs verification to obtain actual causes with their responsibilities, during which several strategies are used to boost efficiency. Further, we explore the CRP for the non-answers to reverse skyline queries. Towards this, we extend CP to identify directly all the actual causes and their responsibilities for a non-answer to reverse skyline queries without additional verification. Extensive experiments using both real and synthetic data sets demonstrate the effectiveness and efficiency of our presented algorithms.

Why-not questions, which aim to seek clarifications on the missing tuples for query results, have recently received considerable attention from the database community. In this paper, we systematically explore why-not questions on reverse top-k queries , owing to its importance in multi-criteria decision making. Given an initial reverse top- k query and a missing/why-not weighting vector set W m that is absent from the query result, why-not questions on reverse top- k queries explain why W m does not appear in the query result and provide suggestions on how to refine the initial query with minimum penalty to include W m in the refined query result. We first formalize why-not questions on reverse top- k queries and reveal their semantics, and then propose a unified framework called WQRTQ to answer why-not questions on both monochromatic and bichromatic reverse top- k queries. Our framework offers three solutions, namely, (i) modifying a query point q , (ii) modifying a why-not weighting vector set W m and a parameter k , and (iii) modifying q , W m , and k simultaneously, to cater for different application scenarios. Extensive experimental evaluation using both real and synthetic data sets verifies the effectiveness and efficiency of the presented algorithms.