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.

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.

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.

In today's fast-paced world, advertisers are increasingly demanding real-time and accurate personalized ad delivery based on dynamic preference modeling, which emphasizes the temporality existing in both user preference and product characteristics. Meanwhile, with the development of graph neural networks (GNNs), E-commerce knowledge graphs (KG) with rich semantic relatedness are invoked to improve accuracy and provide appropriate explanations to encourage advertisers' willingness to invest in ad expenses. However, it is still challenging for existing methods to comprehensively consider both time-series interactions and graph-structured knowledge triples in a unified model, i.e., the case in knowledge-aware dynamic advertising. The interaction graph between users and products changes rapidly over time, while the knowledge in KG remains relatively stable. This results in an uneven distribution of temporal and semantic information, causing existing GNNs to fail in this scenario. In this work, we quantitatively define the above phenomenon as temporal unevenness and introduce the Incremental Leveling Network (InLN) with three novel techniques: the periodic-focusing window for node-level dynamic modeling, the biased temporal walk for subgraph-level dynamic modeling and the incremental leveling mechanism for KG updating. Verified by comprehensive and intensive experiments, InLN outperforms nine baseline models in three tasks by substantial margins, reaching up to a 9.9% improvement and averaging a 5.7% increase.

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, a staleness-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. Theoretically, we show bounded approximation errors of embeddings and gradients with convergence guarantee. Empirically, we evaluate Sancus with common GNN models via different system setups on large-scale benchmark datasets. Compared to SOTA works, Sancus can avoid up to 74% communication with at least 1.86X faster throughput on average without accuracy loss.

Graph neural networks (GNNs) have gained increasing attention in their great success at graph representation learning. In GNNs, the neighborhood of the target node is aggregated iteratively to capture and learn its local structure and neighbor information. Observing that different nodes often require a distinct number of iterations to better learn the representation, we propose an adaptive and structure-aware graph sampling scheme GraphANGEL for GNNs. However, it is quite challenging because both the suitable range of exploration and the important substructure in the neighborhood are difficult to determine. Exploiting the unique feature of random walk mixing time and various node structural role importance measures, we first propose a lightweight component to flexibly estimate the proper neighborhood exploration depth for each target node. Then we investigate different importance metrics to identify and sample the most structurally critical subgraphs that carry a larger influence in messaging passing. Moreover, since different importance metrics unveil different aspects of the graph, we combine and ensemble various importance measures with attention to boost the final performance. In this manner, our method adaptively and explicitly embeds the structural importance information of a node and its critical neighborhood at the same time for finer structure-aware graph representation learning. Evaluation on the benchmark datasets suggests the competitive performance of GraphANGEL to the state-of-the-art approaches, demonstrating the effectiveness of our adaptive and structure-aware sampling approach.

Transfer learning has gained increasing attention due to the inferior performance of machine learning algorithms with insufficient training data. Most of the previous homogeneous or heterogeneous transfer learning works aim to learn a mapping function between feature spaces based on the inherent correspondence across the source and target domains or labeled instances. However, in many real world applications, existing methods may not be robust when the correspondence across domains is noisy or labeled instances are not representative. In this paper, we develop a novel transfer learning framework called Transfer Learning via Feature Isomorphism Discovery (abbreviated to TLFid), which owns high tolerance for noisy correspondence between domains as well as scarce or non-existing labeled instances. More specifically, we propose a feature isomorphism approach to discovering common substructures across feature spaces and learning a feature mapping function from the target domain to the source domain. We evaluate the performance of TLFid on the cross-lingual sentiment classification tasks. The results show that our method achieves significant improvement in terms of accuracy compared with the state-of-the-art methods.