Query rewriting is essential for database performance optimization, but existing automated rule enumeration methods suffer from exponential search spaces, severe redundancy, and poor scalability, especially when handling complex query plans with five or more nodes, where a node represents an operator in the plan tree. We present SLER, a scalable system that enables efficient and effective rewrite rule discovery by combining standardized template enumeration with a learning to rank approach. SLER uses standardized templates, abstractions of query plans with operator structures preserved but data specific details removed, to eliminate structural redundancies and drastically reduce the search space. A learn to rank model guides enumeration by pre filtering the most promising template pairs, enabling scalable rule generation for large node templates. Evaluated on over 11000 real world SQL queries from both open source and commercial workloads, SLER has automatically constructed a rewrite rule repository exceeding 1 million rules - the largest empirically validated rewrite rule library to date. Notably, at the scale of one million rules, SLER supports query plan templates with complexity up to channel level depth. This unprecedented scale opens the door to discovering highly intricate transformations across diverse query patterns. Critically, SLER's template driven design and learned ranking mechanism are inherently extensible, allowing seamless integration of new and complex operators, paving the way for next generation optimizers powered by comprehensive, adaptive rule spaces.

Communities, formed by a subset of vertices that are densely connected to each other and loosely connected to outside community members, widely exist to represent functional modules in real-world complex systems. Most existing community detection and search methods aim at finding communities at one single level, neglecting the natural properties of overlapping and hierarchy in communities. Therefore, the discovery of hierarchical graph clustering (HGC) to find communities at different levels, which is particularly useful in many applications. However, existing HGC studies suffer from two significant limitations: 1) inefficiency over large-scale networks, and 2) generating too many levels of community hierarchy without distinguishing the hierarchy differences. To address the above limitations, we revisit the problem of hierarchical graph clustering and formulate the problem based on our proposed three important properties. To tackle it, we propose theoretical-guaranteed fast solutions, in terms of algorithm complexity and hierarchy levels. We first formulate our HGC problem to admit three key properties of hierarchical communities. Based on the natural hierarchical structure of$k$-core, we develop a simple and importantly useful technique of core propagation. The key idea of core propagation is to take each$k$-core as one seed of hierarchical communities and find disjoint communities within$k$-core using a linear-time algorithm of label propagation. We propose two core propagation approaches of top-down and bottom-up algorithms, in terms of different search directions of$k$-cores by increment and decrement on$k$, respectively. The top-down method can find a given level of hierarchical communities in$O(t m)$time, where$t$is an input of hierarchy levels and$m$is the graph size. To dismiss the hardness of users' input hierarchy parameter$t$, the bottom-up algorithm is equipped with a well-designed strategy of auto-adjusting hierarchical levels based on the graph structure itself. We also develop the coreness weight-based label propagation to ensure the accurate label voting of compressed communities at low levels. The bottom-up method runs fast in$O(m \log \delta(G))$, where$\log \delta(G)$is a small value of the maximum coreness in graph$G$. Extensive experiments conducted on real-world graphs with ground-truth HGCs validate the effectiveness and efficiency of our proposed core propagation methods against state-of-the-art methods. Two case studies on the world-wide flight network and the Hong Kong road network demonstrate the particular usage of our HGC methods.

The problem of structural diversity search has been widely studied recently, which aims to find out the users with the highest structural diversity in social networks. The structural diversity of a user is depicted by the number of social contexts inside his/her contact neighborhood. Three structural diversity models based on cohesive subgraph models (e.g., k-sized component, k-core, and k-truss), have been proposed. Previous solutions only focus on CPU-based sequential solutions, suffering from several key steps of that cannot be highly parallelized. GPUs enjoy high-efficiency performance in parallel computing for solving many complex graph problems such as triangle counting, subgraph pattern matching, and graph decomposition. In this paper, we provide a unified framework to utilize multiple GPUs to accelerate the computation of structural diversity search under the mentioned three structural diversity models. We first propose a GPU-based lock-free method to efficiently extract ego-networks in CSR format in parallel. Second, we design detailed GPU-based solutions for computingk-sized component-based,k-core-based, and alsok-truss-based structural diversity scores by dynamically grouping GPU resources. To effectively optimize the workload balance among multiple GPUs, we propose a greedy work-packing scheme and a dynamic work-stealing strategy to fulfill usage. Extensive experiments on real-world datasets validate the superiority of our GPU-based structural diversity search solutions in terms of efficiency and effectiveness.

Social decisions made by individuals are easily influenced by information from their social neighborhoods. A key predictor of social contagion is the multiplicity of social contexts inside the individual’s contact neighborhood, which is termed structural diversity. However, the existing models have limited decomposability for analyzing large-scale networks, and suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to overcome the weak decomposability. Based on this model, we study a novel problem of truss-based structural diversity search in a graph$G$, that is, to find the$r$vertices with the highest truss-based structural diversity and return their social contexts. To tackle this problem, we propose an online structural diversity search algorithm in$O(\rho (m+\mathcal {T}))$time, where$\rho$,$m$, and$\mathcal {T}$are respectively the arboricity, the number of edges, and the number of triangles in$G$. To improve the efficiency, we design an elegant and compact index, called TSD-index, which keeps the structural diversity information for all individual vertices. We further optimize the structure of TSD-index into a highly compressed GCT-index. Our GCT-index-based structural diversity search utilizes the global triangle information for fast index construction and finds answers in$O(m)$time. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.

Structural diversity, the multiplicity of social contexts inside an individual's contact neighborhood, is shown to play an important role in the social contagion process. Existing models have limited decomposability for analyzing large-scale networks, which may suffer from the inaccurate reflection of social context diversity. In this paper, we propose a truss-based structural diversity model to address the limitations. We study the problem of top-r structural diversity search to find r vertices with the largest truss-based structural diversity scores in a graph. We propose two novel index structures of TSD-index and GCT-index, and efficient index-based query processing algorithms to solve the problem. Extensive experiments demonstrate the effectiveness and efficiency of our proposed model and algorithms, against state-of-the-art methods.

The eruption of a pandemic, such as COVID-19, can cause an unprecedented global crisis. Contact tracing, as a pillar of communicable disease control in public health for decades, has shown its effectiveness on pandemic control. Despite intensive research on contact tracing, existing schemes are vulnerable to attacks and can hardly simultaneously meet the requirements of data integrity and user privacy. The design of a privacy-preserving contact tracing framework to ensure the integrity of the tracing procedure has not been sufficiently studied and remains a challenge. In this paper, we propose P2B-Trace, a privacy-preserving contact tracing initiative based on blockchain. First, we design a decentralized architecture with blockchain to record an authenticated data structure of the user's contact records, which prevents the user from intentionally modifying his local records afterward. Second, we develop a zero-knowledge proximity verification scheme to further verify the user's proximity claim while protecting user privacy. We implement P2B-Trace and conduct experiments to evaluate the cost of privacy-preserving tracing integrity verification. The evaluation results demonstrate the effectiveness of our proposed system.

Hierarchical directed acyclic graph (HDAG) is an essential graph model to represent terminology relationships in a hierarchy, such as Disease Ontology, Gene Ontology, and Wikipedia. However, due to massive terminologies and complex structures in a HDAG, an end user might feel difficult to explore and summarize the whole graph, which is practically useful but less studied in the literature. In this demo, we develop an interactive system of HDAG-Explorer to help users summarize HDAG with highly important and diverse vertices. Our HDAG-Explorer system exhibits several useful features including summarized visualization, interactive exploration, and structural statistics report. All these features facilitate in-depth understanding of the HDAG data. We showcase the usability of the HDAG-Explorer through two real-world applications of summarized topic recommendation and visual data exploration.