Compressing sorted keys is a fundamental operation in data management and information retrieval. Inspired by the success of learned index, recent studies apply simple ML models to compress large-scale sorted keys, leading to the concept of learned compressor. Intuitively, learned compressors losslessly encode sorted keys by approximating them with an error-bounded ML model (e.g., a piecewise linear function) and a residual array to ensure lossless key restoration. However, determining the optimal configuration of underlying ML models to maximize compression efficacy is nontrivial. To address this, by analyzing the distribution characteristics of input keys, we propose BitTuner, a novel framework that automatically sets model hyper-parameters to provably achieve the best compression ratio. We demonstrate BitTuner on two real-world scenarios: inverted list compression and vectorDB codebook compression. The results show that BitTuner automates the parameter tuning procedure and achieves superior compression efficacy when compared to generic compressors such as LZ4 and LZMA.

Data valuation quantifies the impact of individual data points on model performance, and Shapley values provide a principled approach to this important task due to their desirable axiomatic properties, albeit with high computational complexity. Recent breakthroughs have enabled fast computation of exact Shapley values for unweighted $k$-nearest neighbor ($k$NN) classifiers. However, extending this to weighted $k$NN models has remained a significant open challenge. The state-of-the-art methods either require quadratic time complexity or resort to approximation via sampling. In this paper, we show that a conceptually simple but overlooked approach --- data duplication --- can be applied to this problem, yielding a natural variant of weighted $k$NN-Shapley. However, a straightforward application of the data-duplication idea leads to increased data size and prohibitive computational and memory costs. We develop an efficient algorithm that avoids materializing the duplicated dataset by exploiting the structural properties of weighted $k$NN models, reducing the complexity to near-linear time in the original data size. Besides, we establish theoretical foundations for this approach through axiomatic characterization of the resulting values, and empirically validate the effectiveness and efficiency of our method.

Data Shapley values provide a principled approach for quantifying the contribution of individual training examples to machine learning models. However, computing these values often requires computational complexity that is exponential in the data size, and this has led researchers to pursue efficient algorithms tailored to specific machine learning models. Building on the prior success of the Shapley valuation for $K$-nearest neighbor (KNN) models, in this paper, we introduce a localized data Shapley framework that significantly accelerates the valuation of data points. Our approach leverages the distance-based local structure in the data space to decompose the global valuation problem into smaller, localized computations. Our primary contribution is an efficient valuation algorithm for a threshold-based KNN variant and shows that it provides provable speedups over the baseline under mild assumptions. Extensive experiments on real-life datasets demonstrate that our methods achieve a substantial speedup compared to previous approaches.

Learned indexes have attracted significant research interest due to their potential to offer better space-time trade-offs compared to B+-tree variants. Among various learned indexes, the PGM-Index based on error-bounded piecewise linear approximation is an elegant data structure that has demonstrated provably superior performance over conventional B+-tree indexes. However, despite numerous efforts to optimize the design of the PGM-Index, few systematically study the root causes of performance mismatches observed in practice. In this paper, we explore two key research questions. Q1 : Why are PGM-Indexes theoretically effective? and Q2 : Why do PGM-Indexes underperform in practice? For Q1 , we show that for a set of N sorted keys, the PGM-Index can achieve a lookup time of O (log log N ) while using O ( N ) space. For Q2 , we identify that querying PGM-Indexes is highly memory-bound, where the internal index search operations often become the bottleneck. To fill the performance gap, we propose PGM++, a simple yet effective extension to the original PGM-Index that employs a mixture of different search strategies, with hyper-parameters automatically tuned through a cost model calibrated by theoretical findings. Extensive experiments show that, at comparable space costs, PGM++ speeds up index lookup queries by up to 2.31X and 1.56X when compared to the original PGM-Index and SOTA baselines.

The rapid advancements of generative artificial intelligence (GenAI) have recently led to renewed attention towards approximate nearest neighbor (ANN) search and vector databases (VectorDB). Among various ANN methodologies, vector quantization techniques like product quantization (PQ) are widely used to generate space-efficient representations for large-scale dense vectors. However, the code-books generated by PQ often reach several gigabytes in size, making them impractical for web-scale, high-dimensional vectors in resource-constrained environments like mobile devices. In this study, we propose SegPQ , a simple yet effective framework for losslessly compressing codebooks generated by any PQ variants, enabling efficient in-memory vector search on devices with limited memory. SegPQ represents the raw PQ codewords as a trained error-bounded piecewise linear approximation model (ϵ-PLA) and pre-computed low-bit residuals. We theoretically demonstrate that, with high probability, the number of bits per compressed codeword is 1.721 + ⌈log 2 ϵ OPT ⌉, where ϵ OPT is the optimal error parameter that can be determined by data characteristics. To accelerate query execution, we further design SIMD-aware query processing algorithms on compressed codebooks to fully exploit the hardware parallelism offered by modern architectures. Extensive experimental studies on real datasets showcase that, for 1 billion vectors, SegPQ reduces PQ codebook memory consumption by up to 4.7 x (approx. 851 MB ) while incurring only 3.3% additional query processing overhead caused by decompression.

Higher-order graph clustering partitions graphs use frequently occurring subgraphs instead of edges, proving effective in community detection and knowledge discovery. Motif conductance, known for its strong interpretability, is a leading model. However, existing motif conductance algorithms are hindered by a two-stage reweighting framework that requires enumerating motif instances to generate an edge-weighted graph for partitioning. This framework has two major drawbacks: (1) It provides only a quadratic bound for three-vertex motifs, with no provable approximation guarantees for other motifs. (2) Enumerating motif instances is computationally prohibitive for large motifs or dense graphs due to combinatorial explosions. Besides, costly spectral clustering or local graph diffusion on the edge-weighted graph limits their scalability. In this paper, we propose a novel peeling-based clustering framework, PSMC, offering a motifindependent approximation ratio for any motif. Specifically, PSMC first defines a new locally computable vertex metric Motif Resident based on the given motif. Then, it iteratively deletes vertices with the smallest motif resident using efficient dynamic update techniques, outputting a locally optimal result with approximation guarantees. Besides, we introduce several powerful optimization techniques to further reduce computational costs. Empirical results on real-world and synthetic datasets showcase our proposed solutions' superiority over ten competitors.

Efficient indexing is fundamental to managing and analyzing multi-dimensional data. A growing trend is to directly learn the storage layout of multi-dimensional data using simple machine learning models, leading to the concept of Learned Index . Compared to conventional indexing methods that have been used for decades (e.g., k d-tree and R-tree variants), learned indexes have demonstrated empirical advantages in both space and time efficiency on modern architectures. However, there is a lack of comprehensive evaluation across existing multi-dimensional learned indexes under a standardized benchmark, making it challenging to identify the most suitable index for specific data types and query patterns. This gap also hinders the widespread adoption of learned indexes in practical applications. In this paper, we present the first in-depth empirical study to answer the question: how good are multi-dimensional learned indexes? We evaluate ten recently published indexes under a unified experimental framework, which includes standardized implementations, datasets, query workloads, and evaluation metrics. We thoroughly investigate the evaluation results and discuss the findings that may provide insights for future learned index design.

Abstract Graph neural networks (GNNs) have emerged due to their success at modeling graph data. Yet, it is challenging for GNNs to efficiently scale to large graphs. Thus, distributed GNNs come into play. To avoid communication caused by expensive data movement between workers, we propose Sancus and its advanced version Sancus"Equation missing", the staleness and quantization-aware communication-avoiding decentralized GNN system. By introducing a set of novel bounded embedding staleness metrics and adaptively skipping broadcasts, Sancus abstracts decentralized GNN processing as sequential matrix multiplication and uses historical embeddings via cache. To further mitigate the communication volume, Sancus"Equation missing" conducts quantization-aware communication on embeddings to reduce the size of broadcast messages. Theoretically, we show bounded approximation errors of embeddings and gradients with a known fastest convergence guarantee. Empirically, we evaluate Sancus and Sancus"Equation missing" with common GNN models via different system setups on large-scale benchmark datasets. Compared to SOTA works, Sancus"Equation missing" can avoid up to $$86\%$$ 86 % communication with $$3.0\times $$ 3.0 × faster throughput on average without accuracy loss.

Graph Neural Networks (GNNs) have achieved remarkable performance in various applications, including social media analysis, computer vision, and natural language processing. Decoupled GNNs are a ubiquitous framework because of their high efficiency. However, existing decoupled GNNs suffer from the following several defects. (1) Their studies on GNN feature propagation are isolated, with each study emphasizing a user-specified propagation matrix. (2) They still have high computation costs to achieve provable performance on massive graphs with millions of nodes and billions of edges. (3) Their feature propagation steps are uniform, which makes it difficult for them to escape the dilemmas of over-smoothing. In this paper, we propose GSD-GNN, a Generalized and Scalable Decoupled GNN framework based on the spectral graph theory, which offers the following advantages. Firstly, through minor parameter adjustments, it can degenerate into most existing Decoupled GNNs, such as APPNP, GDC, SGC, etc. Secondly, it efficiently computes an arbitrary propagation matrix with near-linear time complexity and theoretical guarantees. Thirdly, it customizes the adaptive feature propagation mechanism for each node to mitigate the over-smoothing dilemma. Finally, extensive experiments on massive graphs demonstrate that the proposed GSD-GNN indeed is effective, scalable, and flexible.

The emerging deep learning techniques prefer mapping complex data objects (e.g., images, documents) to compact binary vectors (i.e., hash codes) for efficient similarity search. In this paper, we study the problem of indexing large-scale binary databases to support fast Hamming distance-based similarity queries. Existing Hamming space indices usually divide long binary vectors into short disjoint pieces and apply the Pigeonhole Principle to prune unnecessary candidates. In our work, we relax the disjoint partition constraint by allowing dimension redundancy, which yields a tighter pruning bound named Augmented Pigeonhole Principle (APP). Intuitively, APP enables more optimization opportunities by capturing the correlation between database and query workloads. Based on APP, we propose HAP, an efficient Hamming space index framework to support both Hamming range queries and k-NN queries.

Data synopsis is widely adopted to speed-up query processing over large spatial databases. As one of the most popular spatial data synopses, multi-dimensional histograms (MH) have been studied and adopted by modern DBMS and analytical systems for decades. However, existing MH construction techniques highly rely on expert knowledge and statistical assumptions, making them hard to achieve consistently satisfactory performance across different datasets. Inspired by the emerging learned index techniques where the widely used index structures like B-tree can be further improved by integrating simple machine learning models, in this paper, we propose a learned data synopsis technique named Learned Multi-dimensional Histogram (LHist). Compared with the traditional data synopsis techniques, LHist is fully data-driven, easy-to-implement, and has the potential to achieve better storage-accuracy trade-off. On the typical task of range COUNT query estimation, the extensive experimental studies on large-scale real-world datasets and synthetic benchmarks reveal that LHist can outperform the existing synopsis structures in terms of storage cost, query processing efficiency, and estimation accuracy.

As an important operator for spatial data analytics, Region of Interest (ROI) query is of great importance in many location-based services such as event detection, location recommendation and smart transportation. To address the challenge of conducting ROI queries on the increasingly complex spatial data, we present RIDE, an efficient and effective system for generalized ROI Discovery and Exploration. Different from existing studies and systems, RIDE supports a large spectrum of region score functions and query geometries, enabling customized ROI queries for different application scenarios. This demonstration proposal introduces the basic concept of ROI queries and key components of the RIDE system, including data storage and indexing, ROI query processing and optimization and user interface.

Automatic pneumothorax segmentation on chest X-ray images is very crucial for diagnosis and treatment as large pneumothorax could be fatal. The pneumothorax segmentation is challenging, as some small pneumothoraces can be subtle, and may overlap with the ribs and clavicles. Meanwhile, the shape variation of pneumothorax is also very large, which also makes the segmentation more difficult. In this paper, we propose a novel automated pneumothorax segmentation framework which consists of three modules: 1) a fully convolutional DenseNet (FC-DenseNet), 2) a spatial and channel squeeze and excitation module (scSE), and 3) a multi-scale module. In order to improve boundary segmentation accuracy, a novel spatial weighted cross-entropy loss function is proposed, which penalize the target, background and contour pixels with different weights. Extensive experiments are conducted on the 2213 chest X-ray images of testing data and the results suggest that proposed segmentation algorithm outperforms the state-of-the-art methods in terms of mean pixel-wise accuracy (MPA) of 0.93±0.13 and dice similarity coefficient (DSC) of 0.92±0.14 etc. Accordingly, the effectiveness of our method is corroborated.

Attributes like texture, lobulation, malignancy, etc., are commonly used to describe the phenotype of a pulmonary nodule in computed tomography (CT) image, which can provide useful medical knowledge for the identification of early stage lung cancer. There may exist certain relations among these attributes, and some attributes may naturally imply or boost others that have been less comprehensively exploited in previous studies. In this paper, we explicitly model the relations among 11 attributes of nodules by way of transfer learning and extract a meta-structure that captures the transferabilities across deep features of these attributes. Specifically, a higher-order transfer learning scheme is proposed by involving three phases, i.e., semantic attribute-specific modeling, semantic attributes transfer modeling and pathologic attribute generalizing, to explore the strongest association across various attributes and to boost the nodule attribute predictions in chest CT images. The proposed approach has been evaluated on the 2632 nodules in the public Lung Image Database Consortium and Image Database Resource Initiative (LIDC-IDRI) dataset. The experimental results suggest that our higher-order transfer approach shows the superior predictive performance not only in the most of the semantic attributes compared with the schemes of learning from scratch and the first-order transfer but also for the pathologic attribute compared with the related studies. In addition, we demonstrate an attribute transfer graph to reveal which attributes combination can supply the most useful information to boost the predictive performance of target attributes.

Maximum Range-Sum (MaxRS) query is an important operator in spatial database for retrieving regions of interest (ROIs). Given a rectangular query size a × b and a set of spatial objects associated with positive weights, MaxRS retrieves rectangular regions Q of size a × b, such that the sum of object weights covered by Q (i.e., range-sum) is maximized. Due to the inaccuracy of the location acquisition, the collected locations of spatial objects are inherently uncertain and imprecise, which can be modeled by uncertain objects. In this paper, we propose a Probabilistic Maximum Range-Sum (PMaxRS) query over uncertain spatial objects, which obtains a set γ* of rectangles such that the probability that each region Q ϵ γ* has the maximum range-sum exceeds a user-specified threshold Pt. We show that determining whether a given region Q is #P-complete. To tackle the hardness, we introduce the PMaxRS_Framework based on pruning and refinement strategies. In the pruning step, we propose a candidate generation technique to reduce the search space. In the refinement step, we design an efficient sampling-based approximation algorithm to verify the remaining candidate regions. Extensive experiments are conducted to demonstrate the effectiveness and efficiency of our algorithms.

With the increasing awareness towards protecting environment, people are paying more attention to the electric vehicles (EVs). Accompanying the rapid growing number of EVs, challenges raise at the same time about how to place EV chargers (EVC), within a city, to satisfy multiple types of charging demand. To provide a better EVC station deployment plan to benefit the whole society, we propose a problem called Social-Aware Optimal Electric Vehicle Charger Deployment (SOCD) on road network. The SOCD problem is hard and different from existing work in three aspects, 1) we assume that the charging demand should be satisfied not only in urban areas but also in relatively rural areas; 2) our work is the first one that considers an EVC station should have multiple types of charging plugs, which is more reasonable in real world; 3) different from the regional deployment solutions in previous literature, our SOCD directly works on a real road network and EVC stations are placed at appropriate POIs laying on the road network. We show that the SOCD problem is NP-hard. To deal with the hardness, we design two heuristic algorithms whose efficiency and effectiveness can be experimentally demonstrated. Furthermore, we investigate the incremental case, that is, given an existing EVC station deployment plan and extra more budget, we need to decide where and how many to place more chargers. Finally, we conduct extensive experiments on real road network of Shanghai to demonstrate both effectiveness and efficiency of our algorithms.