Graph clustering is a fundamental data mining task that clusters vertices into different groups. The structural graph clustering algorithm ($SCAN$) is a widely used graph clustering algorithm that derives not only clustering results, but also special roles of vertices like hubs and outliers. In this paper, we consider structural graph clustering on dynamic graphs under Jaccard similarity. The state-of-the-art index-based solution focuses on static graphs and incurs prohibitive update costs to maintain indices. Lately, an efficient approximate dynamic structural graph clustering algorithm DynStrClu under Jaccard similarity is proposed. However, their solution needs to fix input parameters while parameter settings of SCAN usually need to be fine-tuned to achieve good clustering results. Motivated by these limitations, we present a study on devising effective index structures for SCAN algorithm on dynamic graphs. Similar to the state-of-the-art dynamic scheme, our main idea to reduce the time complexity is still by bringing approximation to clustering results. However, our solution does not need to fix the input parameters. To achieve this, our solution includes two key components. The first is to maintain a bottom-$k$sketch for each vertex so that the similarities of affected vertices can be easily updated. The second key is a bucketing strategy that allows us to update clustering results and roles of vertices efficiently. Our theoretical analysis shows that our proposed algorithm achieves$O(\log \log {\frac{M+m}{p_{f}}}\cdot \log {\frac{M+m}{p_{f}}})$expected update cost and guarantees to return approximate clustering results with probability$1-p_{f}$after up to$M$updates. Extensive experiments show that our solution is up to two orders of magnitude faster than the state-of-the-art index-based solution while still achieving high-quality clustering results.

Recent advancements in AI have enabled models to map real-world entities, such as product images, into high-dimensional vectors, making approximate nearest neighbor search (ANNS) crucial for various applications. Often, these vectors are associated with additional attributes like price, prompting the need for range-filtered ANNS where users seek similar items within specific attribute ranges. Naive solutions like pre-filtering and post-filtering are straightforward but inefficient. Specialized indexes, such as SeRF, SuperPostFiltering, and iRangeGraph, have been developed to address these queries effectively. However, these solutions do not support dynamic updates, limiting their practicality in real-world scenarios where datasets frequently change. To address these challenges, we propose DIGRA, a novel dynamic graph index for range-filtered ANNS. DIGRA supports efficient dynamic updates while maintaining a balance among query efficiency, update efficiency, indexing cost, and result quality. Our approach introduces a dynamic multi-way tree structure combined with carefully integrated ANNS indices to handle range filtered ANNS efficiently. We employ a lazy weight-based update mechanism to significantly reduce update costs and adopt optimized choice of ANNS index to lower construction and update overhead. Experimental results demonstrate that DIGRA achieves superior trade-offs, making it suitable for large-scale dynamic datasets in real-world applications.

Given a set O of objects consisting of n high-dimensional vectors, the problem of approximate nearest neighbor (ANN) search for a query vector q is crucial in many applications where objects are represented as feature vectors in high-dimensional spaces. Each object in O often has attributes like popularity or price, which influence the search. Practically, searching for the nearest neighbor to q might include a range filter specifying the desired attribute values, e.g., within a specific price range. Existing solutions for range filtered ANN search often face trade-offs among excessive storage, poor query performance, and limited support for updates. To address this challenge, we propose RangePQ, a novel indexing scheme that supports efficient range filtered ANN searches and updates, requiring only linear space. Our scheme integrates seamlessly with existing PQ-based index---a widely recognized, scalable index type for ANN searches---to enhance range-filtered ANN queries and update capabilities. Our indexing method, supporting arbitrary range filters, has a space complexity of (O(n log K)), where K is a parameter of the PQ-based index and log K scales with O(log n). To reduce the space cost, we further present a hybrid two-layer structure to reduce space usage to O(n), preserving query efficiency without additional update costs. Experimental results demonstrate that our indexing scheme significantly improves query performance while maintaining competitive update performance and space efficiency.

In the era of big data, the demand for historical data analytics is growing across various applications. Simultaneously, range queries have been extensively explored within the domain of databases. Binary search trees are a classic type of in-memory index for facilitating range queries. Persistent binary search trees provide read-only snapshots of these trees, allowing range queries to be processed during updates while ensuring consistency. Additionally, multiple versions of snapshots support queries related to historical moments to meet the demands of numerous applications. However, existing implementations do not support both highspeed updates and efficient, accurate historical queries on multi-core platforms. Motivated by this gap, we propose a novel concurrent update strategy to balance update and query performance. For a binary search tree containing n elements, our approach completes m updates in O (log n + m ) time using O (log n ) threads. We further implement a hybrid concurrent strategy to improve the scalability and practical performance of our solution. The experimental results demonstrate that our proposal strikes a good balance between update and query performance. In particular, our proposal outperforms existing solutions under workloads with different data distributions and varying update-query ratios.

Real-time data warehouses are essential for modern applications. Extract-Transform-Load (ETL) as a fundamental component of offline data warehouses also provides crucial support within realtime data warehouses. Among various traditional ETL approaches, Lambda and Kappa have emerged as classic real-time data processing solutions due to their freshness and query performance, which best meet business demands. However, both of them often require the integration of external stream processing engines, introducing challenges related to complexity, efficiency, and consistency. ZeroETL has emerged as an approach to address these issues. Nevertheless, existing ZeroETL-based solutions primarily emphasize the implementation of extraction and loading, resulting in limitations in handling transformation. Incremental View Maintenance (IVM) offers an alternative that can enhance ZeroETL. However, existing IVM implementations often focus on query acceleration rather than supporting high-throughput, complex real-time workloads. To address these challenges, we propose Streaming View, an efficient real-time data processing engine integrated within AnalyticDB of Alibaba Cloud. Unlike existing solutions, Streaming View supports high-throughput, complex data processing for realtime streaming ETL workloads. Furthermore, it can be leveraged to optimize ZeroETL-based approaches by enhancing transformation capabilities. We design tailored algorithms and optimizations for diverse syntaxes and high-throughput scenarios, ensuring the system meets complex application needs. By integrating incremental computation into the data warehouse, Streaming View reduces complexity, ensures data consistency, and boosts performance, offering a robust solution for real-world applications. Experiments show Streaming View improves processing performance by up to 7x and 20x over traditional ETL and IVM methods, respectively, and addresses complex scenarios unsolved by existing solutions.

In the era of big data, the landscape of data management and analytics has significantly transformed, presenting diverse challenges for cloud platforms. Modern data warehouses face increasing challenges in handling hybrid transactional and analytical processing (HTAP) workloads efficiently in cloud environments. Traditional shared-nothing architectures provide high-performance query execution but suffer from high storage costs and limited elasticity, while shared-storage approaches improve scalability but often struggle with query efficiency due to increased data movement and indexing overhead. Furthermore, existing execution engines lack optimized support for vectorized processing and real-time analytics, limiting their ability to handle large-scale workloads efficiently. To address these limitations, we introduce AnalyticDB-PG (ADB-PG), a cloud-native, high-performance data warehouse designed for modern analytical workloads. It integrates a unified architecture supporting both Shared-Nothing and Shared-Storage modes, allowing flexible deployment and seamless elasticity. In ADB-PG, we introduce Beam, a hybrid storage engine that efficiently balances row-based and columnar storage for real-time analytics, and Laser, an optimized execution engine leveraging vectorized execution and Just-In-Time compilation to accelerate query processing. The system further incorporates advanced indexing mechanisms, adaptive runtime filtering, and dictionary encoding to enhance performance. Extensive evaluations on TPC-H and TPC-DS benchmarks demonstrate that ADB-PG achieves significant performance improvements while reducing storage and operational costs, making it a compelling solution for modern cloud-based data analytics.

Given a social network G , a cost associated with each user, and an influence threshold η, the minimum cost seed selection problem (MCSS) aims to find a set of seeds that minimizes the total cost to reach η users. Existing works are mainly devoted to providing an expected coverage guarantee on reaching η, classified as MCSS-ECG, where their solutions either rely on an impractical influence oracle or cannot attain the expected influence threshold. More importantly, due to the expected coverage guarantee, the actual influence in a campaign may drift from the threshold evidently. Thus, the advertisers would like to request for a probability guarantee of reaching η. This motivates us to further solve the MCSS problem with a probabilistic coverage guarantee, termed MCSS-PCG. In this paper, we first propose our algorithm CLEAR to solve MCSS-ECG, which reaches the expected influence threshold without any influence oracle or influence shortfall but a practical approximation ratio. However, the ratio involves an unknown term (i.e., the optimal cost). Thus, we further devise the STAR method to derive a lower bound of the optimal cost and then obtain the first explicit approximation ratio for MCSS-ECG. In MCSS-PCG, it is necessary to estimate the probability that the current seeds reach η, to decide when to stop seed selection. To achieve this, we design a new technique named MRR, which provides efficient probability estimation with a theoretical guarantee. With MRR in hand, we propose our algorithm SCORE for MCSS-PCG, whose performance guarantee is derived by measuring the gap between MCSS-ECG and MCSS-PCG, and applying the theoretical results in MCSS-ECG. Finally, extensive experiments demonstrate that our algorithms achieve up to two orders of magnitude speed-up compared to alternatives while meeting the requirement of MCSS-PCG with the smallest cost.

Abstract Active learning for graph neural networks (GNNs) aims to select B nodes to label for the best possible GNN performance. Carefully selected labeled nodes can help improve GNN performance and hence motivates a line of research works. Unfortunately, existing methods still provide inferior GNN performance or cannot scale to large networks.Motivated by these limitations, in this paper, we present FICOM, an effective and scalable GNN active learning framework. Firstly, we formulate the node selection as an optimization problem where we consider the importance of a node from (i) the importance of a node during the feature propagation with a connection to the personalized PageRank (PPR), and (ii) the diversity of a node brings in the embedding space generated by feature propagation. We show that the defined problem is submodular, and a greedy solution can provide a $$(1-1/e)$$ ( 1 - 1 / e ) -approximate solution.However, a standard greedy solution requires getting the node with the maximum marginal gain of the objective score in each iteration, which incurs a prohibitive running cost and cannot scale to large datasets. As our main contribution, we present FICOM, an efficient and scalable solution that provides $$(1-1/e)$$ ( 1 - 1 / e ) -approximation guarantee and scales to graphs with millions of nodes on a single machine. The main idea is that we adaptively maintain the lower- and upper-bound of the marginal gain for each node v. In each iteration, we can first derive a small subset of candidate nodes and then compute the exact score for this subset of candidate nodes so that we can find the node with the maximum marginal gain efficiently. Extensive experiments on six benchmark datasets using four GNNs, including GCN, SGC, APPNP, and GCNII, show that our FICOM consistently outperforms existing active learning approaches on semi-supervised node classification tasks using different GNNs. Moreover, our solution can finish within 5 h on a million-node graph.

Trend analysis is a fundamental type of analytical query in online analytical processing (OLAP) systems. In trend analysis, a key step is to identify k valuable attributes whose distributions in two subsets under different predicates significantly differ for further investigation, where the difference is measured by metric functions. However, the exact solution that involves scanning all records is prohibitively expensive, particularly when handling large datasets in the era of big data. To minimize unnecessary data access, the existing state-of-the-art solution TopKAttr adopts sampling to avoid the expensive data scan. However, their solution still has two main drawbacks. Firstly, their solution is tailored only for two limited metric functions: the Earth Mover distance and Euclidean distance, and cannot be generalized to more complicated metric functions. Besides, their solution still aims to return the exact top-k answers via the sampling method, which still causes high running costs as shown in our experiment. Motivated by these limitations, we propose a general approximation framework for attribute recommendation that efficiently returns the top-k attributes with theoretical guarantees while supporting an extensive range of metric functions, such as the Kolmogorov-Smirnov test (KS-test), Chebyshev distance, the Earth Mover distance, Euclidean distance, and with the potential to more metrics. The key to our framework is a new bound estimation strategy that can be applied to a wide spectrum of metrics, as we listed above. Based on our estimation framework, we further devise an efficient approximation algorithm with theoretical guarantees to answer the top-k queries, which is widely used in attribute recommendation. Extensive experiments on four real large datasets show that our framework gains up to an order of magnitude speed-up and consistently high accuracy compared to TopKAttr, providing a promising alternative for attribute recommendation in OLAP systems.

Given a graph G, a cost associated with each node, and a budget B, the budgeted influence maximization (BIM) aims to find the optimal set S of seed nodes that maximizes the influence among all possible sets such that the total cost of nodes in S is no larger than B. Existing solutions mainly follow the non-adaptive idea, i.e., determining all the seeds before observing any actual diffusion. Due to the absence of actual diffusion information, they may result in unsatisfactory influence spread. Motivated by the limitation of existing solutions, in this paper, we make the first attempt to solve the BIM problem under the adaptive setting, where seed nodes are iteratively selected after observing the diffusion result of the previous seeds. We design the first practical algorithm which achieves an expected approximation guarantee by probabilistically adopting a cost-aware greedy idea or a single influential node. Further, we develop an optimized version to improve its practical performance in terms of influence spread. Besides, the scalability issues of the adaptive IM-related problems still remain open. It is because they usually involve multiple rounds (e.g., equal to the number of seeds) and in each round, they have to construct sufficient new reverse-reachable set (RR-set) samples such that the claimed approximation guarantee can actually hold. However, this incurs prohibitive computation, imposing limitations on real applications. To solve this dilemma, we propose an incremental update approach. Specifically, it maintains extra construction information when building RR-sets, and then it can quickly correct a problematic RR-set from the very step where it is first affected. As a result, we recycle the RR-sets at a small computational cost, while still providing correctness guarantee. Finally, extensive experiments on large-scale real graphs demonstrate the superiority of our algorithms over baselines in terms of both influence spread and running time.

\em Personalized PageRank (PPR) stands as a fundamental proximity measure in graph mining. Given an input graph G with the probability of decay α, a source node s and a target node t, the PPR score π(s,t) of target t with respect to source s is the probability that an α-decay random walk starting from s stops at t. A \em single-source PPR (SSPPR) query takes an input graph G with decay probability α and a source s, and then returns the PPR π(s,v) for each node v ∈ V. Since computing an exact SSPPR query answer is prohibitive, most existing solutions turn to approximate queries with guarantees. The state-of-the-art solutions for approximate SSPPR queries are index-based and mainly focus on static graphs, while real-world graphs are usually dynamically changing. However, existing index-update schemes can not achieve a sub-linear update time. Motivated by this, we present an efficient indexing scheme for single-source PPR queries on evolving graphs. Our proposed solution is based on a classic framework that combines the forward-push technique with a random walk index for approximate PPR queries. Thus, our indexing scheme is similar to existing solutions in the sense that we store pre-sampled random walks for efficient query processing. One of our main contributions is an incremental updating scheme to maintain indexed random walks in expected O(1) time after each graph update. To achieve O(1) update cost, we need to maintain auxiliary data structures for both vertices and edges. To reduce the space consumption, we further revisit the sampling methods and propose a new sampling scheme to remove the auxiliary data structure for vertices while still supporting O(1) index update cost on evolving graphs. Extensive experiments show that our update scheme achieves orders of magnitude speed-up on update performance over existing index-based dynamic schemes without sacrificing the query efficiency.

A bipartite graph is a graph that consists of two disjoint sets of vertices and only edges between vertices from different vertex sets. In this paper, we study the counting problems of two common types of em motifs in bipartite graphs: (i) butterflies (2x2 bicliques) and (ii) bi-triangles (length-6 cycles). Unlike most of the existing algorithms that aim to obtain exact counts, our goal is to obtain precise enough estimations of these counts in bipartite graphs, as such estimations are already sufficient and of great usefulness in various applications. While there exist approximate algorithms for butterfly counting, these algorithms are mainly based on the techniques designed for general graphs, and hence, they are less effective on bipartite graphs. Not to mention that there is still a lack of study on approximate bi-triangle counting. Motivated by this, we first propose a novel butterfly counting algorithm, called one-sided weighted sampling, which is tailored for bipartite graphs. The basic idea of this algorithm is to estimate the total butterfly count with the number of butterflies containing two randomly sampled vertices from the same side of the two vertex sets. We prove that our estimation is unbiased, and our technique can be further extended (non-trivially) for bi-triangle count estimation. Theoretical analyses under a power-law random bipartite graph model and extensive experiments on multiple large real datasets demonstrate that our proposed approximate counting algorithms can reach high accuracy, yet achieve up to three orders (resp. four orders) of magnitude speed-up over the state-of-the-art exact butterfly (resp. bi-triangle) counting algorithms. Additionally, we present an approximate clustering coefficient estimation framework for bipartite graphs, which shows a similar speed-up over the exact solutions with less than 1% relative error.

Given a weighted setSofnelements,weighted set sampling (WSS)samples an element inSso that each elementai; is sampled with a probability proportional to its weightw(ai). The classic alias method pre-processes an index inO(n) time withO(n) space and handles WSS withO(1) time. Yet, the alias method does not support dynamic updates. By minor modifications of existing dynamic WSS schemes, it is possible to achieve an expectedO(1) update time and drawtindependent samples in expectedO(t) time with linear space, which is theoretically optimal. But such a method is impractical and even slower than a binary search tree-based solution. How to support both efficient sampling and updates in practice is still challenging. Motivated by this, we designBUS, an efficient scheme that handles an update inO(1) amortized time and drawstindependent samples inO(logn + t)time with linear space. A natural extension of WSS is theweighted independent range sampling (WIRS), where each element inSis a data point from R. Given an arbitrary rangeQ= [ℓ,r] at query time, WIRS aims to do weighted set sampling on the setSQof data points falling into rangeQ.We show that by integrating the theoretically optimal dynamic WSS scheme mentioned above, it can handle an update inO(logn) time and can drawtindependent samples for WIRS inO(logn + t) time, the same as the state-of-the-art static algorithm. Again, such a solution by integrating the optimal dynamic WSS scheme is still impractical to handle WIRS queries. We further propose WIRS-BUS to integrate BUS to handle WIRS queries, which handles each update inO(logn) time and drawstindependent samples inO(log2n + t) time with linear space. Extensive experiments show that our BUS and WIRS-BUS are efficient for both sampling and updates.

Empirical variance is a fundamental concept widely used in data management and data analytics, e.g., query optimization, approximate query processing, and feature selection. A direct solution to derive the empirical variance is scanning the whole data table, which is expensive when the data size is huge. Hence, most current works focus on approximate answers by sampling. For results with approximation guarantees, the samples usually need to be uniformly independent random, incurring high cache miss rates especially in compact columnar style layouts. An alternative uses block sampling to avoid this issue, which directly samples a block of consecutive records fitting page sizes instead of sampling one record each time. However, this provides no theoretical guarantee. Existing studies show that the practical estimations can be inaccurate as the records within a block can be correlated.

Graph clustering is a fundamental data mining task that clusters vertices into different groups. The structural graph clustering algorithm ( SCAN ) is a widely used graph clustering algorithm that derives not only clustering results, but also special roles of vertices like hubs and outliers. In this paper, we consider structural graph clustering on dynamic graphs under Jaccard similarity. The state-of-the-art index-based solution focuses on static graphs and incurs prohibitive update costs to maintain indices. Lately, an efficient approximate dynamic structural graph clustering algorithm Dyn-StrClu under Jaccard similarity is proposed. However, their solution needs to fix input parameters while parameter settings of SCAN usually need to be fine-tuned to achieve good clustering results. Motivated by these limitations, we present a study on devising effective index structures for SCAN algorithm on dynamic graphs. Similar to the state-of-the-art dynamic scheme, our main idea to reduce the time complexity is still by bringing approximation to clustering results. However, our solution does not need to fix the input parameters. To achieve this, our solution includes two key components. The first is to maintain a bottom- k sketch for each vertex so that the similarities of affected vertices can be easily updated. The second key is a bucketing strategy that allows us to update clustering results and roles of vertices efficiently. Our theoretical analysis shows that our proposed algorithm achieves O (log n · log M + m / pf ) expected update cost and guarantees to return approximate clustering results with probability 1 - pf after up to M updates. Extensive experiments show that our solution is up to two orders of magnitude faster than the state-of-the-art index-based solution while still achieving high-quality clustering results.