Yitong Song
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:
- Bin Yao
Shanghai Jiao Tong University, Shanghai, China
7 shared publications - Jianliang Xu
Hong Kong Baptist University
3 shared publications - Xin Huang
Hong Kong Baptist University
2 shared publications - Anqi Liang
Shanghai Jiao Tong University Shanghai Jiao Tong University Southwestern University of Finance and Economics Shanghai Jiao Tong University
1 shared publication - Anqi Liang
Shanghai Jiao Tong University, Shang Hai, China
1 shared publication - Bojian Zhu
Hong Kong Baptist University
1 shared publication
Latest Publications
- 1 December 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 38 (12) , 8118-8137
Disk-Resident Vector Similarity Search: A Survey
- 1 December 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 38 (12) , 8118-8137
Disk-Resident Vector Similarity Search: A Survey
- Open Access
- 30 May 2026
- Published by Association for Computing Machinery (ACM)
- p. 580-587
Vector Search for the Future: From Memory-Resident, Static Heterogeneous Storage, to Cloud-Native Architectures
- 30 May 2026
- Published by Association for Computing Machinery (ACM)
- p. 580-587
Open AccessVector Search for the Future: From Memory-Resident, Static Heterogeneous Storage, to Cloud-Native Architectures
- Open Access
- 18 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-27
Balancing Global and Local: Representative Sampling for Large?Scale Vector Data
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.
- 18 May 2026
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 4 (3) , 1-27
Open AccessBalancing Global and Local: Representative Sampling for Large?Scale Vector Data
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
- 4 December 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (6) , 1-26
TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning
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.
- 4 December 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (6) , 1-26
Open AccessTRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning
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
- 22 September 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (4) , 1-27
PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs
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.
- 22 September 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (4) , 1-27
Open AccessPGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs
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
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 AccessPGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs
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
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.
Open AccessTRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning
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.
- 4 January 2025
- Published by Springer Nature in The VLDB Journal
- Vol. 34 (1) , 1-21
Efficient top-k spatial-range-constrained approximate nearest neighbor search on geo-tagged high-dimensional vectors
- 4 January 2025
- Published by Springer Nature in The VLDB Journal
- Vol. 34 (1) , 1-21
Efficient top-k spatial-range-constrained approximate nearest neighbor search on geo-tagged high-dimensional vectors
- Open Access
- 13 February 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 18 (4) , 1-20
Enhancing Heterogeneous Knowledge Graph Completion with a Novel GAT-based Approach
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.
- 13 February 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 18 (4) , 1-20
Open AccessEnhancing Heterogeneous Knowledge Graph Completion with a Novel GAT-based Approach
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
- 1 February 2024
- Published by Elsevier in Information Sciences
- Vol. 662
Dynamic heterogeneous attributed network embedding
- 1 February 2024
- Published by Elsevier in Information Sciences
- Vol. 662
Open AccessDynamic heterogeneous attributed network embedding