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.

Similarity search finds objects that are similar to a given query object based on a similarity metric. As the amount and variety of data continue to grow, similarity search in metric spaces has gained significant attention. Metric spaces can accommodate any type of data and support flexible distance metrics, making similarity search in metric spaces beneficial for many real-world applications, such as multimedia retrieval, personalized recommendation, trajectory analytics, data mining, decision planning, and distributed servers. However, existing studies mostly focus on indexing metric spaces on a single machine, which faces efficiency and scalability limitations with increasing data volume and query amount. Recent advancements in similarity search turn towards distributed methods, while they face challenges including inefficient local data management, unbalanced workload, and low concurrent search efficiency. To this end, we proposeDIMS, an efficientDistributedIndex for similarity search inMetricSpaces. First, we design a novel three-stage heterogeneous partition to achieve workload balance. Then, we present an effective three-stage indexing structure to efficiently manage objects. We also develop concurrent search methods with filtering and validation techniques that support efficient distributed similarity search. Additionally, we devise a cost-based optimization model to balance communication and computation cost. Extensive experiments demonstrate that DIMS significantly outperforms existing distributed similarity search approaches.

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.

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.

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.