YSYitong Song

Yitong Song

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article


Yitong Song has a total of 37 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Disk-Resident Vector Similarity Search: A Survey

    by Yitong Song, Huiling Li, Zheng Wu, Lanjing Yi, Bojian Zhu, Xuanhe Zhou, Xin Huang, Jianliang Xu

  • Open Access

    Balancing Global and Local: Representative Sampling for Large?Scale Vector Data

    by Zheng Wu, Yitong Song, Xuliang Zhu, Huiling Li, Jianliang Xu, Xin Huang

    Representative sampling, which extracts a small subset of representative instances from massive, high-dimensional vector data, is useful for many applications, such as visualization, model prototyping, and data exploration. Existing methods often suffer from either over-representing dense regions while neglecting sparse ones or failing to capture fine-grained data distributions . To address these challenges, we study representative sampling with two objectives: global coverage and local fidelity . Specifically, given a dataset D and a sampling ratio ρ ∈ (0, 1], we seek a subset S ⊆ D with | S |=ρ| D | that minimizes the local-fidelity cost subject to a global-coverage constraint. Here, the global coverage of S measures the average distance from data points to their nearest samples in S . We define local fidelity by comparing local intrinsic dimensionality (LID) estimates computed on S and on the full dataset D at a matched evaluation scale, which measures how well fine-grained local distributions are preserved. Unfortunately, efficiently computing an optimal solution is challenging; we prove that the representative sampling problem is NP-hard. To address this challenge, we first propose LASS-Lite, a heuristic that improves global coverage by selecting widely separated initial samples across diverse LID levels and then enhances local fidelity by adding their nearby neighbors. Since LASS-Lite selects neighbors for each sample independently, we further propose LASS-NA, which employs a more effective joint selection strategy by prioritizing points that can serve as shared neighbors for multiple samples. This approach better utilizes the sampling budget to improve overall local fidelity. We formulate this strategy as a submodular maximization problem, yielding an efficient greedy algorithm with a provable (1-1/ e )-approximation guarantee. To validate the effectiveness of our methods, we conduct extensive experiments on four large-scale, real-world vector datasets. In terms of local fidelity, our algorithms use only 5.0% of the data and reduce the local fidelity cost by 58.6%-62.7% compared to three state-of-the-art competitors at similar levels of global coverage. In addition, we demonstrate the practical utility of our representative sampling in data visualization, self-supervised model prototyping, graph-based approximate nearest neighbor search (ANNS) and label-efficient model selection. Our source code is available at https://github.com/i11ume/LASS.

  • Open Access

    TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning

    by Yitong Song, Pengcheng Zhang, Chao Gao, Bin Yao, Kai Wang, Zongyuan Wu, Lin Qu

    High-dimensional vector similarity search (HVSS) is critical for many data processing and AI applications. However, traditional HVSS methods often require extensive data access for distance calculations, leading to inefficiencies. Triangle-inequality-based lower bound pruning is a widely used technique to reduce the number of data access in low-dimensional spaces but becomes less effective in high-dimensional settings. This is attributed to the ''distance concentration'' phenomenon, where the lower bounds derived from the triangle inequality become too small to be useful. To address this, we propose TRIM, which enhances the effectiveness of traditional triangle-inequality-based pruning in high-dimensional vector similarity search using two key ways: (1) optimizing landmark vectors used to form the triangles, and (2) relaxing the lower bounds derived from the triangle inequality, with the relaxation degree adjustable according to user's needs. TRIM is a versatile operation that can be seamlessly integrated into both memory-based (e.g., HNSW, IVFPQ) and disk-based (e.g., DiskANN) HVSS methods, reducing distance calculations and disk access. Extensive experiments show that TRIM enhances memory-based methods, improving graph-based search by up to 90% and quantization-based search by up to 200%, while achieving a pruning ratio of up to 99%. It also reduces I/O costs by up to 58% and improves efficiency by 102% for disk-based methods, while preserving high query accuracy. Our source code is available at https://github.com/petrizhang/TRIM.


  • Open Access

    PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs

    by Hao Duan, Yitong Song, Bin Yao, Anqi Liang

    Approximate Nearest Neighbor Search (ANNS) plays a crucial role in many key areas. Proximity graphs (PGs) are the leading method for ANNS, offering the best balance between query efficiency and accuracy. However, their performance heavily depends on various construction and query parameters, which are difficult to optimize due to their complex interdependencies. Given that users often prioritize specific accuracy levels, efficiently identifying the optimal PG configurations to meet these targets is essential. Although some studies have explored automatic configuration tuning for PGs, they are limited by inefficiencies and suboptimal results. These issues stem from the need to construct numerous PGs for searching and re-tuning from scratch whenever the dataset changes, as well as the failure to capture the complex dependencies between configurations, query performance, and tuning objectives. To address these challenges, we propose PGTuner, an efficient framework for automatic PG configuration tuning leveraging pre-training knowledge and model transfer techniques. PGTuner improves efficiency through a pre-trained query performance prediction (QPP) model, eliminating the need to build multiple PGs. It also features a deep reinforcement learning-based parameter configuration recommendation (PCR) model to recommend optimal configurations for specific datasets and accuracy targets. Additionally, PGTuner incorporates out-of-distribution detection and deep active learning for efficient tuning in dynamic scenarios and transferring to new datasets. Extensive experiments demonstrate that PGTuner can stably achieve the top-level tuning effect across different datasets while significantly improving tuning efficiency by up to 14.69X, with a 14.64X boost in dynamic scenarios. The code and data for PGTuner are available online at https://github.com/hao-duan/PGTuner.


  • Open Access

    PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs

    by Hao Duan, Yitong Song, Bin Yao, Anqi Liang

    Approximate Nearest Neighbor Search (ANNS) plays a crucial role in many key areas. Proximity graphs (PGs) are the leading method for ANNS, offering the best balance between query efficiency and accuracy. However, their performance heavily depends on various construction and query parameters, which are difficult to optimize due to their complex inter-dependencies. Given that users often prioritize specific accuracy levels, efficiently identifying the optimal PG configurations to meet these targets is essential. Although some studies have explored automatic configuration tuning for PGs, they are limited by inefficiencies and suboptimal results. These issues stem from the need to construct numerous PGs for searching and re-tuning from scratch whenever the dataset changes, as well as the failure to capture the complex dependencies between configurations, query performance, and tuning objectives. To address these challenges, we propose PGTuner, an efficient framework for automatic PG configuration tuning leveraging pre-training knowledge and model transfer techniques. PGTuner improves efficiency through a pre-trained query performance prediction (QPP) model, eliminating the need to build multiple PGs. It also features a deep reinforcement learning-based parameter configuration recommendation (PCR) model to recommend optimal configurations for specific datasets and accuracy targets. Additionally, PGTuner incorporates out-of-distribution detection and deep active learning for efficient tuning in dynamic scenarios and transferring to new datasets. Extensive experiments demonstrate that PGTuner can stably achieve the top-level tuning effect across different datasets while significantly improving tuning efficiency by up to 14.69X, with a 14.64X boost in dynamic scenarios. The code and data for PGTuner are available online at https://github.com/hao-duan/PGTuner.

  • Open Access

    TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning

    by Yitong Song, Pengcheng Zhang, Chao Gao, Bin Yao, Kai Wang, Zongyuan Wu, Lin Qu

    High-dimensional vector similarity search (HVSS) is critical for many data processing and AI applications. However, traditional HVSS methods often require extensive data access for distance calculations, leading to inefficiencies. Triangle-inequality-based lower bound pruning is a widely used technique to reduce the number of data access in low-dimensional spaces but becomes less effective in high-dimensional settings. This is attributed to the "distance concentration" phenomenon, where the lower bounds derived from the triangle inequality become too small to be useful. To address this, we propose TRIM, which enhances the effectiveness of traditional triangle-inequality-based pruning in high-dimensional vector similarity search using two key ways: (1) optimizing landmark vectors used to form the triangles, and (2) relaxing the lower bounds derived from the triangle inequality, with the relaxation degree adjustable according to user's needs. TRIM is a versatile operation that can be seamlessly integrated into both memory-based (e.g., HNSW, IVFPQ) and disk-based (e.g., DiskANN) HVSS methods, reducing distance calculations and disk access. Extensive experiments show that TRIM enhances memory-based methods, improving graph-based search by up to 90% and quantization-based search by up to 200%, while achieving a pruning ratio of up to 99%. It also reduces I/O costs by up to 58% and improves efficiency by 102% for disk-based methods, while preserving high query accuracy.

  • Efficient top-k spatial-range-constrained approximate nearest neighbor search on geo-tagged high-dimensional vectors

    by Yitong Song, Bin Yao, Zhida Chen, Xin Yang, Jiong Xie, Feifei Li, Mengshi Chen


  • Open Access

    Enhancing Heterogeneous Knowledge Graph Completion with a Novel GAT-based Approach

    by Wanxu Wei, Yitong Song, Bin Yao

    Knowledge graphs (KGs) play a vital role in enhancing search results and recommendation systems. With the rapid increase in the size of KGs, they are becoming inaccurate and incomplete. This problem can be solved by the KG completion methods, of which graph attention network (GAT)-based methods stand out because of their superior performance. However, existing GAT-based KG completion methods often suffer from overfitting issues when dealing with heterogeneous KGs, primarily due to the unbalanced number of samples. Additionally, these methods demonstrate poor performance in predicting the tail (head) entity that shares the same relation and head (tail) entity with others. To solve these problems, we propose GATH, a novel GAT -based method designed for H eterogeneous KGs. GATH incorporates two separate attention network modules that work synergistically to predict the missing entities. We also introduce novel encoding and feature transformation approaches, enabling the robust performance of GATH in scenarios with imbalanced samples. Comprehensive experiments are conducted to evaluate GATH’s performance. Compared with the existing state-of-the-art GAT-based model on Hits@10 and MRR metrics, our model improves performance by 5.2% and 5.2% on the FB15K-237 dataset and by 4.5% and 14.6% on the WN18RR dataset, respectively.


  • Open Access

    Dynamic heterogeneous attributed network embedding

    by Hongbo Li, Wenli Zheng, Feilong Tang, Yitong Song, Bin Yao, Yanmin Zhu