In this paper, we study the problem of maximal similar-weight biclique enumeration for large bipartite graphs. Given an edge-weighted bipartite graph$G=(U,\ V,\ E)$and a weight difference threshold$\delta$, we aim to efficiently enumerate all maximal similar-weight bicliques in$G$, where a maximal similar-weight biclique is a maximal complete subgraph$B(L,\ R)$of$G$such that the weight difference of edges in$E(B)$is not larger than$\delta$. This problem has many applications, such as item recommendation, fraud detection, and biclustering of gene expression data, etc. To the best of our knowledge, we are the first to systematically study this problem. It is very challenging to efficiently solve this problem due to its #P-completeness. In this paper, we propose a two-phase branch-and-bound baseline method, namely MSWBE, which explores the search space in a depth-first manner. Although MSWBE offers a useful computation framework to our problem, its performance is not yet satisfactory due to the large candidate set during the enumeration. To alleviate this, we propose an advanced approach, called MSWBE++. In particular, MSWBE++ exploits the search space by utilizing the edge connectivity and weight information simultaneously, and therefore refines the candidate set significantly. Observing that a straightforward implementation of MSWBE++ by following a depth-first search strategy may generate non-maximal bicliques, we develop a breadth-first search strategy to realize MSWBE++, which can discard the non-maximal sets at an early stage. To accelerate the computation, we introduce effective graph reduction techniques. Our extensive experimental results on 10 real-life datasets demonstrate that MSWBE++ significantly outperforms the baseline methods by up to 2 orders of magnitude. We conduct a case study to show that maximal similar-weight bicliques can provide useful searching hints for fraudulent rating detection.

Path enumeration is a fundamental problem and has been extensively studied in the literature. Given two query vertices and a weight threshold, the problem aims to identify all simple paths with weight not exceeding the threshold. Existing studies on path enumeration include DFS-based solutions and join-based solutions, where the join-based solutions only work for unweighted graphs. In this paper, we are the first to propose a join-based framework for weighted graphs. By observing the characteristics of DFS, we design a series of novel data structures and operations based on the join-based framework. In this way, our final solution combines the advantages of both join and DFS. We conduct experiments on several real large graphs. For weighted graphs, our method is much more efficient than existing algorithms. For unweighted graphs, our method is still competitive compared with the state-of-the-art solution which only works for unweighted graphs.

Subgraph counting is a fundamental problem in graph analytics with broad applications, yet remains computationally intractable due to its #P-hardness. To address this, numerous approximate solutions have been proposed, though they often suffer from limited efficiency and accuracy. In this paper, we introduce FlowSC, a novel approach that achieves both high accuracy and efficiency in subgraph counting. Our method starts with an enhanced candidate filtering algorithm, which significantly improves the pruning capability of bipartite graph-based techniques with minimal overhead. Building on this, we propose a bottom-up flow-learning model based on a new Graph Neural Network (GNN) architecture. By employing a carefully designed message-passing mechanism, the model explicitly controls the direction, range, and iterations of information flow, enabling a simulation of the candidate tree-based counting process. This mechanism is further empowered by a customized message aggregation technique, alongside a pretraining strategy that facilitates model training. Extensive experiments show that FlowSC can achieve up to 4 orders of magnitude improvement in accuracy and 3× improvement in efficiency over the baselines across datasets, while scaling to billion-edge graphs.

Continuous subgraph matching (CSM) is a critical task for analyzing dynamic graphs and has a wide range of applications, such as merchant fraud detection, cyber-attack hunting, and rumor detection. Although many efficient CSM algorithms have been recently proposed, they are mainly designed to process a single query. However, in some application scenarios, multi-query oriented continuous subgraph matching (MQCSM) may be of more interest. To our knowledge, the two existing solutions to MQCSM are outdated due to unsatisfactory performance. In this paper, we propose MQ-Match, an efficient approach to MQCSM. First, we design a compact yet effective index structure CCG, which maintains the local matching result of vertices in the data graph using a directed graph. The directed edges in CCG can be utilized as an effective pruning rule for the subsequent incremental matching algorithm when expanding a partial match. Then, we develop a computation sharing incremental matching algorithm. In specific, a set of matching trees is constructed based on the depth-first search trees of the query graphs. By utilizing CCG, we conduct subgraph matching for the matching tree to collect the incremental matches for the query graphs, where the common structures of query graphs are matched only once. Extensive experiments show that MQ-Match can achieve 3.1x-7071.4x speedup over the competitors, and consumes much less memory under the majority of the experiment settings.

The advancement in location technology and the increase in trajectory data have made trajectory data mining a focal point in the field of spatiotemporal data analysis. Unlike the extensive research focused on the similarity of entire trajectories, this paper delves into subtrajectory similarity within collections containing a large number of trajectories, under a specified trajectory similarity metric. We propose the Top-k Representative Similar Subtrajectory Query problem, with the objective of identifying the top-k representative subtrajectories which are most similar to the query trajectory within a large trajectory set. To ensure diversity in the results, we adopt the concept of representative similarity, where only the subtrajectory with the highest similarity score to the query trajectory is reported, thus avoiding the redundancy in the top-$k$results. To address the challenge of high computational costs, we propose a learning-based framework, leveraging a deep learning model called Representative Similarity Score Estimation (RSSE) to approximate subtrajectory similarity scores efficiently and reduce the candidate set significantly. Empirical evaluations conducted on various real-world datasets substantiate the effectiveness and efficiency of our proposed method.

There are two fundamental problems in regular simple path queries (RSPQs). One is the reachability problem which asks whether there exists a simple path between the source and the target vertex matching the given regular expression, and the other is the enumeration problem which aims to find all the matched simple paths. As an important computing component of graph databases, RSPQs are supported in many graph database query languages such as PGQL and openCypher. However, answering RSPQs is known to be NP-hard, making it challenging to design scalable solutions to support a wide range of expressions. In this paper, we first introduce the class of transitive restricted expression , which covers more than 99% of real-world queries. Then, we propose an efficient algorithm framework to support both reachability and enumeration problems under transitive restricted expression constraints. To boost the performance, we develop novel techniques for reachability detection, the search of candidate vertices, and the reduction of redundant path computation. Extensive experiments demonstrate that our exact method can achieve comparable efficiency to the state-of-the-art approximate approach, and outperforms the state-of-the-art exact methods by up to 2 orders of magnitude.

Continuously monitoring structural patterns in streaming graphs is a critical task in many real-time graph-based applications. In this paper, we study the problem of time-constrained continuous subgraph matching (shorted as TCSM) over streaming graphs. Given a query graph Q with timing order constraint and a data graph stream G , TCSM aims to report all incremental matches of Q in G for each update of G , where a match should obey both structure constraint (i.e., isomorphism) and timing order constraint of Q. Although TCSM has a wide range of applications, such as cyber-attack detection and credit card fraud detection, we note that this problem has not been well addressed. The state-of-the-art bears the limitations of high index space cost and intermediate result maintenance cost. In this paper, we propose TC-Match, an effective approach to TCSM. First, we design a space and time cost-effective index CSS, which is essentially a k -partite graph structure where a node corresponds to an edge in G. By carefully creating links between nodes, we can encapsulate into CSS the partial embedding and timing order information between edges in G. We theoretically show that CSS has polynomial space and construction time complexities. Second, based on the property of CSS, we develop an efficient incremental matching algorithm with an effective node merging optimization. Extensive experiments show that TC-Match can achieve up to 3 orders of magnitude query performance improvement over the baseline methods, and meanwhile the memory consumption is reduced by 48.7%-86.7%.

Computing Multi-source Shortest Path query with Assembly points ($\mathsf {MSPA}$) is a fundamental graph problem. The$\mathsf {MSPA}$problem locates a set of assembly points to minimize the overall distance for transporting objects from different sources to a destination, where we can assemble objects at assembly points to reduce the total cost. We prove that the$\mathsf {MSPA}$problem is NP-hard. The intuitive method for computing the optimal set of assembly points and the corresponding set of paths is by Branch-and-Bound. However, the combination of different assembly points is exponential. By analyzing the structure of the path set based on the proposed distance graph, we find that the used paths can be combined into a tree. Hence, by defining the state of subtrees and the state transition equation, we propose a dynamic programming (DP) algorithm by pruning the redundant computation of subtrees. The experiment shows that the DP algorithm can achieve three orders of magnitude speedup in query processing time compared with the optimized Branch-and-Bound algorithm. Moreover, we reduce the transition candidates of the DP algorithm from the entire vertex set to certain neighbors. Extensive experiments are conducted on different types of real-world networks to demonstrate the performance of our DP algorithm.

In this paper, we study the problem of maximal biclique enumeration on large signed bipartite graphs. Given a signed bipartite graph$G=(U,V,E,s)$, a parameter$\theta \in [0.5, 1.0]$, our goal is to efficiently enumerate all maximal$\theta$-bicliques in$G$, where a maximal$\theta$-biclique$B(L,R)$is a complete subgraph of$G$with (1) the proportion of positive neighbors for each vertex in$B$is at least$\theta$, and (2)$B$is not contained in another biclique$B^{\prime }$, while$B^{\prime }$also satisfies (1). This problem has many applications, such as biclustering for genes, recommendation of similar groups, collaboration in communities, etc. However, it is computationally challenging due to its #P-completeness. Besides, we prove that even determining the maximality of a$\theta$-biclique is NP-hard. To the best of our knowledge, there is no efficient and scalable solution to this problem in the literature. In this paper, we first propose a branch-and-bound framework, namely${\sf MSiBE}$, which enumerates all maximal$\theta$-bicliques in a depth-first manner. Then, we develop three effective optimizations to improve the performance of${\sf MSiBE}$. (1) The local information of each search space is utilized to enhance the pruning capacity. (2) When expanding the partial biclique, we always focus on the side with fewer candidates first, by which fruitless search branches can be skipped early. (3) We implement${\sf MSiBE}$with efficient array reordering techniques and set intersection strategy. To further accelerate the computation, we introduce useful graph reduction techniques. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by up to 3 orders of magnitude.

The requirement for appropriate ways to measure the similarity between data objects is a common but vital task in various domains, such as data mining, machine learning and so on. Driven by abundant real-world applications, many well-known similarity (distance) metrics are proposed to measure the pairwise similarity of data pairs, e.g., graph edit distance for graphs and dynamic time warping for time series. However, many similarity metrics suffer from the high time complexity. More specifically, most of the well-known similarity metrics often need quadratic time or even much more time to compute the ground truth similarity and some of them are proven to be NP-hard. With the development of deep learning techniques, there is an emerging research trend on the learning for similarity computation on various data types in the field of database (DB) and data mining, which is quite different with the metric learning studies in the machine learning (ML) literature. Specifically, the studies in the ML focus on the learning for semantic similarity in specific tasks, which is implicitly indicated by the training data, on the data in the feature space. While the studies in the DB literature usually consider the learning for well-defined similarity metrics (e.g., graph edit distance) on the data objects (e.g., graphs), such that it can benefit the similarity computation on data in terms of multiple aspects, such as computation time, metric quality and search heuristic, and the learned representation of data can also be naturally fed to downstream tasks. This survey paper provides a comprehensive review of similarity computation learning on several data types, including set, sequence and graph. Moreover, we first classify the learning-based approaches in terms of their learning target into three categories, i.e., similarity learning, cost matrix learning and search heuristic learning. Then we detail some representative approaches for each category on every data type, and analyze some key features that are utilized by these approaches. Finally, we discuss some challenges and future directions towards the learning for similarity learning on these data types.

Set intersection is a fundamental operation in many applications, such as common neighbor computation in graph-based algorithms, set similarity computation, item recommendation, etc. In the literature, many set intersection methods are proposed. We observe that the state-of-the-art algorithm${\sf RCode}$bears several limitations, such as high index time complexity, inefficient for large-sized sets, and not friendly to the generic set intersection. In this paper, we introduce theBucket Signature forSet(${\sf BigSet}$), an efficient generic set intersection algorithm.${\sf BigSet}$consists of two phases, namely the preprocessing phase and the query phase. In the preprocessing phase,${\sf BigSet}$partitions the elements of a record into$O(2^{k})$buckets and uses a bitmap to indicate the status of the buckets where$n$is the record length and$k$is the number of bits in the signature. In the query phase,${\sf BigSet}$calculates the results using a candidate generating-and-verification framework. Specifically, a set of candidate elements is identified as those falling in the same buckets. Then, for each bucket,${\sf BigSet}$collects the common elements using a merge-based method. To improve the performance, we introduce two optimizations, including bucket sharing and size-aware signature construction techniques. We conduct experiments on 10 real graph datasets and 5 real generic set datasets to evaluate the performance of our proposals. The experiment results show that${\sf BigSet}$is 20× faster than the leading generic set intersection algorithms. Besides it outperforms the${\sf RCode}$with 5× speedup, and while uses up to 8× less memory.

Approximate nearest neighbor (ANN) search is a fundamental search in multi-dimensional databases, which has numerous real-world applications, such as image retrieval, recommendation, entity resolution, and sequence matching. Proximity graph (PG) has been the state-of-the-art index for ANN search. However, the search on existing PGs either suffers from a high time complexity or has no performance guarantee on the search result. In this paper, we propose a novel τ-monotonic graph (τ- MG) to address the limitations. The novelty of τ-MG lies in a τ-monotonic property. Based on this property, we prove that if the distance between a query q and its nearest neighbor is less than a constant τ, the search on τ-MG guarantees to find the exact nearest neighbor of q and the time complexity of the search is smaller than all existing PG-based methods. For index construction efficiency, we propose an approximate variant of τ-MG, namely τ-monotonic neighborhood graph (τ- MNG), which only requires the neighborhood of each node to be τ-monotonic. We further propose an optimization to reduce the number of distance computations in search. Our extensive experiments show that our techniques outperform all existing methods on well-known real-world datasets.

In this article, we study the problem of maximal biclique enumeration on large uncertain bipartite graphs. Given an uncertain bipartite graph$\mathcal {G}=(U,V,E,p)$, a probability threshold$\tau$, and two size constraints$\alpha$and$\beta$, we aim to efficiently enumerate all maximal$\tau$-bicliques in$\mathcal {G}$, where a maximal$\tau$-biclique$B(L,R)$is a complete subgraph of$\mathcal {G}$with (1) the probability of$B$is no less than$\tau$, (2)$|L| \geq \alpha$and$|R| \geq \beta$, and (3)$B$is a maximal complete subgraph satisfying (1) and (2). This problem has many applications, such as biclustering of gene expression data, fraud detection, similar group identification, etc. Despite the wide range of applications, to the best of our knowledge, we note that there are no efficient and scalable solutions to this problem in the literature. This problem is computationally challenging due to its #P-completeness. In this article, we propose a competitive branch-and-bound method, namely${\sf MBEN}$, which explores the search space in a depth-first manner with a variety of pruning techniques. To improve the performance of${\sf MBEN}$, we propose several novel and efficient search processing optimizations. First, we always select the side with fewer candidates to expand the search space. With this search strategy, we have a chance to prune the fruitless branches early. Second, we devise an advanced pruning technique by considering the size pruning and probability pruning at the same time to boost the pruning capacity. Last, we implement${\sf MBEN}$with pre-allocated arrays and pointer maintaining techniques such that the frequent work sets creating operations can be substituted by array element switching operations. In addition, we introduce useful graph reduction techniques to further accelerate the computation. Comprehensive performance studies on 10 real datasets demonstrate that our proposals can significantly outperform the baseline methods by more than two orders of magnitude.

Given a bipartite graph, the maximum edge biclique problem (MEB) aims to find a biclique with the largest number of edges. MEB is a fundamental problem with many real applications, such as community analysis, E-commerce services and bioinformatics. However, in some scenarios, the weight of an edge reflects valuable and important information on the relationship between two entities. Motivated by this, in this paper, we investigate the problem of maximum edge-weighted biclique search (MEWB), which finds a biclique with the largest total weight of edges in a weighted bipartite graph. MEWB has many real applications, including item recommendation, fraud detection, gene clustering, etc. Although we show that MEWB can be resolved by adapting the search algorithm designed for MEB, the performance of this method is yet unsatisfactory. To improve the computation efficiency, two optimizations in terms of upper bound and search order are proposed. For the upper bound, we consider the degree distribution for vertices in the candidate set, and thus have a chance to discard a few edges to tighten the upper bound. For search order, we theoretically show that a vertex order generating the most similar search depth on vertices can achieve the least time cost for MEWB. Guided by this fact, we propose the global summation vertex order. To further accelerate the computation, we extend our approach to a parallel environment, and develop a heuristic approach to deal with large-scale graphs by slightly sacrificing the answer quality. Extensive performance studies conducted on real datasets demonstrate that our proposals can significantly outperform the baseline method by up to two orders of magnitude. Besides, our heuristic approach gives the optimal result on 8 out of 10 real datasets, while achieving more than an order of magnitude of speed-up.

Tree similarity join is useful for analyzing tree structured data. The traditional threshold-based tree similarity join requires a similarity threshold, which is usually a difficult task for users. To remedy this issue, we advocate the problem of top-k tree similarity join. Given a collection of trees and a parameter k, the top-k tree similarity join aims to find k tree pairs with minimum tree edit distance (TED). Although we show that this problem can be resolved by utilizing the threshold-based join, the efficiency is unsatisfactory. In this paper, we propose an efficient algorithm, namely TopKTJoin, which generates the candidate tree pairs incrementally using an inverted index. We also derive TED lower bound for the unseen tree pairs. Together with TED value of the k-th best join result seen so far, we have a chance to terminate the algorithm early without missing any correct results. To further improve the efficiency, we propose two optimization techniques in terms of index structure and verification mechanism. We conduct comprehensive performance studies on real and synthetic datasets. The experimental results demonstrate that TopKTJoin significantly outperforms the baseline method.

NN-Descent is a classic k-NN graph construction approach. It is still widely employed in machine learning, computer vision, and information retrieval tasks due to its efficiency and genericness. However, the current design only works well on CPU. In this paper, NN-Descent has been redesigned to adapt to the GPU architecture. A new graph update strategy called selective update is proposed. It reduces the data exchange between GPU cores and GPU global memory significantly, which is the processing bottleneck under GPU computation architecture. This redesign leads to full exploitation of the parallelism of the GPU hardware. In the meantime, the genericness, as well as the simplicity of NN-Descent, are well-preserved. Moreover, a procedure that allows to k-NN graph to be merged efficiently on GPU is proposed. It makes the construction of high-quality k-NN graphs for out-of-GPU-memory datasets tractable. Our approach is 100-250× faster than the single-thread NN-Descent and is 2.5-5× faster than the existing GPU-based approaches as we tested on million as well as billion scale datasets.

Abstract With the prevalence of Internet access and online services, various big graphs are generated in many real applications (e.g., online social networks and knowledge graphs). An important task on analyzing and mining these graphs is keyword search. Essentially, given a graphGand queryQassociated with a set of keywords, the keyword search aims to find a substructure (e.g., rooted tree or subgraph)SinGsuch that nodes inScollectively cover part of or all keywords inQ, and in the meanwhile,Sis optimal on some user specified semantics. Keyword search on graphs can be applied in many real-life applications, such as point-of-interests recommendation and web search facility. In spite of the great importance of graph keyword search, we, however, notice that the latest survey on this topic is far out of date. Consequently, there is prompt need to conduct a comprehensive survey in this research direction. Motivated by this, in this survey, we systematically review graph keyword search studies by classifying the existing works into different categories according to the specific problem definition. This survey aims to provide the researchers a comprehensive understanding of existing graph keyword search solutions.

In this paper, we study the problem of ( p , q)-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite G = ( U, V , E), and two integer parameters p and q, we aim to efficiently count and enumerate all (p, q)-bicliques in G , where a (p, q)-biclique B ( L, R ) is a complete subgraph of G with L ⊆ U, R ⊆ V , |L| = p, and |R| = q. The problem of (p, q)-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis, etc. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature. This problem is computationally challenging, due to the worst-case exponential number of (p, q)-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p + q. To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer based exploring strategy to enumerate ( p, q )-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p, q)-bicliques optimize the efficiency of graph neural networks.

Different from previous imputation methods which impute missing values in the incomplete samples by using the information in the complete samples, this paper proposes a Date-drive Incremental imputation Model, DIM for short, which uses all available information in the data set to impute missing values economically, effectively, orderly, and iteratively. To this end, we propose a scoring rule to rank the missing features by taking into account both the economical criterion and the effective imputation information. The economical criterion takes both the imputation cost and the discriminative ability of the feature into account, while the effective imputation information enables to use all observed information in the data set including the imputed missing values to impute the left missing values. During the imputation process, our DIM first detects the neednot-impute samples for reducing the imputation cost and noise, and then selects the missing features with the top rank to impute first. The imputation process orderly imputes the missing features until all missing values are imputed or the imputation cost is exhausted. Experimental results on UCI data sets demonstrated the advantages of our proposed DIM, compared to the comparison methods, in terms of prediction accuracy and classification accuracy.

With the prevalence of Internet access and user generated content, a large number of documents/records, such as news and web pages, have been continuously generated in an unprecedented manner. In this paper, we study the problem of efficient stream set similarity join over distributed systems, which has broad applications in data cleaning and data integration tasks, such as on-line near-duplicate detection. In contrast to prefix-based distribution strategy which is widely adopted in offline distributed processing, we propose a simple yet efficient length-based distribution framework which dispatches incoming records by their length. A load-aware length partition method is developed to find a balanced partition by effectively estimating local join cost to achieve good load balance. Our length-based scheme is surprisingly superior to its competitors since it has no replication, small communication cost, and high throughput. We further observe that the join results from the current incoming record can be utilized to guide the index construction, which in turn can facilitate the join processing of future records. Inspired by this observation, we propose a novel bundle-based join algorithm by grouping similar records on-the-fly to reduce filtering cost. A by-product of this algorithm is an efficient verification technique, which verifies a batch of records by utilizing their token differences to share verification costs, rather than verifying them individually. Extensive experiments conducted on Storm, a popular distributed stream processing system, suggest that our methods can achieve up to one order of magnitude throughput improvement over baselines.

Clique is one of the most fundamental models for cohesive subgraph mining in network analysis. Existing clique model mainly focuses on unsigned networks. In real world, however, many applications are modeled as signed networks with positive and negative edges. As the signed networks hold their own properties different from the unsigned networks, the existing clique model is inapplicable for the signed networks. Motivated by this, we propose the balanced clique model that considers the most fundamental and dominant theory, structural balance theory, for signed networks, and study the maximal balanced clique enumeration problem which computes all the maximal balanced cliques in a given signed network. We show that the maximal balanced clique enumeration problem is NP-Hard. A straightforward solution for the maximal balanced clique enumeration problem is to treat the signed network as two unsigned networks and leverage the off-the-shelf techniques for unsigned networks. However, such a solution is inefficient for large signed networks. To address this problem, in this paper, we first propose a new maximal balanced clique enumeration algorithm by exploiting the unique properties of signed networks. Based on the new proposed algorithm, we devise two optimization strategies to further improve the efficiency of the enumeration. We conduct extensive experiments on large real and synthetic datasets. The experimental results demonstrate the efficiency, effectiveness and scalability of our proposed algorithms.

Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-clique percolation community with the maximum k value that contains a given set of query nodes. We adopt an index based approach to solve this problem. Based on the observation that a k-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC-Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC-Index, we can answer the densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm.

Maximal clique enumeration is a fundamental problem in graph database. In this paper, we investigate this problem in the context of spatial database. Given a set P of spatial objects in a 2-dimensional space (e.g., geo-locations of users or point of interests) and a distance threshold r, we can come up with a spatial neighbourhood graph Prby connecting every pair of objects (vertices) in P within distance r. Given a clique S of Pr, namely a spatial clique, it is immediate that any pairwise distance among objects in S is bounded by r. As the maximal pairwise distance has been widely used to capture the spatial cohesiveness of a group of objects, the maximal spatial clique enumeration technique can identify groups of spatially close objects in a variety of location-based-service (LBS) applications. In addition, we show that the maximal spatial clique enumeration can also be used to identify maximal clique pattern instances in the co-location pattern mining applications. Given the existing techniques for maximal clique enumeration, which can be immediately applied on the spatial neighbourhood graph Pr, two questions naturally arise for the enumeration of maximal spatial cliques: (1) the maximal clique enumeration on general graph is NP hard, can we have a polynomial time solution on the spatial neighbourhood graph? and (2) can we exploit the geometric property of the spatial clique to speed up the computation? In this paper, we give a negative answer to the first question by an example where the number of maximal spatial cliques is exponential to the number of the objects. While the answer to the second question is rather positive: we indeed develop two pruning techniques based on geometric properties of the maximal spatial clique to significantly enhance the computing efficiency. Extensive experiments on real-life geolocation data demonstrate the superior performance of proposed methods compared with two baseline algorithms.

Community search is important in graph analysis and can be used in many real applications. In the literature, various community models have been proposed. However, most of them cannot well identify the overlaps between communities which is an essential feature of real graphs. To address this issue, the k-clique percolation community model was proposed and has been proven effective in many applications. Motivated by this, in this paper, we adopt the k-clique percolation community model and study the densest clique percolation community search problem which aims to find the k-clique percolation community with the maximum k value that contains a given set of query nodes. We adopt an index-based approach to solve this problem. Based on the observation that a k-clique percolation community is a union of maximal cliques, we devise a novel compact index, DCPC-Index, to preserve the maximal cliques and their connectivity information of the input graph. With DCPC-Index, we can answerthe densest clique percolation community query efficiently. Besides, we also propose an index construction algorithm based on the definition of DCPC-Index and further improve the algorithm in terms of efficiency and memory consumption. We conduct extensive performance studies on real graphs and the experimental results demonstrate the efficiency of our index-based query processing algorithm and index construction algorithm.

In this paper, we study the problem of set containment join. Given two collections R and S of records, the set containment join R ∞I⊆ S retrieves all record pairs {(r, s)} ∈ R × S such that r ⊆ s. This problem has been extensively studied in the literature and has many important applications in commercial and scientific fields. Recent research focuses on the in-memory set containment join algorithms, and several techniques have been developed following intersection-oriented or union-oriented computing paradigms. Nevertheless, we observe that two computing paradigms have their limits due to the nature of the intersection and union operators. Particularly, intersection-oriented method relies on the intersection of the relevant inverted lists built on the elements of S. A nice property of the intersection-oriented method is that the join computation is verification free. However, the number of records explored during the join process may be large because there are multiple replicas for each record in S. On the other hand, the union-oriented method generates a signature for each record in R and the candidate pairs are obtained by the union of the inverted lists of the relevant signatures. The candidate size of the union-oriented method is usually small because each record contributes only one replica in the index. Unfortunately, union-oriented method needs to verify the candidate pairs, which may be cost expensive especially when the join result size is large. As a matter of fact, the state-of-the-art union-oriented solution is not competitive compared to the intersection-oriented ones. In this paper, we propose a new union-oriented method, namely TT-Join, which not only enhances the advantage of the previous union-oriented methods but also integrates the goodness of intersection-oriented methods by imposing a variant of prefix tree structure. We conduct extensive experiments on 20 real-life datasets by comparing our method with 7 existing methods. The experiment results demonstrate that TT-Join significantly outperforms the existing algorithms on most of the datasets, and can achieve up to two orders of magnitude speedup.

The popularity of e-business and preference learning techniques have contributed a huge amount of product and user preference data. Analyzing the influence of an existing or new product among the users is critical to unlock the great scientific and social-economic value of these data. In this paper, we advocate the problem of influence-based cost optimization for the user preference and product data, which is fundamental in many real applications such as marketing and advertising. Generally, we aim to find a cost optimal position for a new product such that it can attract at least k or a particular percentage of users for the given user preference functions and competitors' products. Although we show the solution space of our problem can be reduced to a finite number of possible positions (points) by utilizing the classical k-level computation techniques, the computation cost is still very expensive due to the nature of the high combinatorial complexity of the k-level problem. To alleviate this issue, we develop efficient pruning and query processing techniques to significantly improve the performance. In particular, our traverse-based 2-dimensional algorithm is very efficient with time complexity O(n) where n is the number of user preference functions. For general multi-dimensional spaces, we develop space partition based algorithm to significantly improve the performance by utilizing cost-based, influence-based and local dominance based pruning techniques. Then, we show that the performance of the partition based algorithm can be further enhanced by utilizing sampling approach, where the problem can be reduced to the classical half-space intersection problem. We demonstrate the efficiency of our techniques with extensive experiments over real and synthetic datasets.