Yingfan Liu
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Yingfan Liu has a total of 62 co-authors. Here are the top co-authors by number of shared publications:
- Jiangtao Cui
Xidian University, Xi'an, China and Xi’an University of Posts & Telecommunications, Xi'an, China
8 shared publications - Jeffrey Xu Yu
The Chinese University of Hong Kong, Hong Kong, China
6 shared publications - Jiadong Xie
The Chinese University of Hong Kong, Hong Kong, Hong Kong
6 shared publications - Hui Li
Xidian University, Xi'an, China
5 shared publications - Hui Zhang
Shanghai Yunxi Technology Co., Ltd
4 shared publications - Kankan Zhao
Shanghai Yunxi Technology Co., Ltd
4 shared publications
Latest Publications
- Open Access
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 3330-3341
Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap
- 8 August 2026
- Published by Association for Computing Machinery (ACM)
- p. 3330-3341
Open AccessGeneralized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap
- 14 June 2026
- Published by Elsevier in Applied Soft Computing
- Vol. 201
TSCAD: Temporality-spectrum collective transformer for multivariate time series anomaly detection
- 14 June 2026
- Published by Elsevier in Applied Soft Computing
- Vol. 201
TSCAD: Temporality-spectrum collective transformer for multivariate time series anomaly detection
- Open Access
- 20 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 2347-2356
KBest: Efficient Vector Search on Kunpeng CPU
- 20 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 2347-2356
Open AccessKBest: Efficient Vector Search on Kunpeng CPU
- Open Access
- 12 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 2014-2024
Breaking the Single-Reference-Vector Barrier in Approximate Nearest Neighbor Search
Approximate nearest neighbor (ANN) searches are commonly employed in various machine learning applications, such as recommendation systems, but traditional ANN searches typically involve only a single reference vector in a query. To broaden the capabilities of ANN search and support multi-reference-vector queries, thereby enabling a wider range of machine learning applications, we introduce all/any-k ANN search. They aim to find vectors that are similar to all or any of the multi-reference vectors in a query, respectively. To effectively and efficiently support all/any-k ANN search, we first propose distance metrics to evaluate the ranking of vectors among those in the dataset for exact all/any-k NN. Building on this, we introduce search algorithms and prove they can search according to the proposed distance metrics on graph indexes designed for traditional ANN. Additionally, we further introduce two-stage search algorithms for all/any-k ANN search to further enhance their search performance. We conduct extensive experiments on real-world datasets to validate the efficiency and effectiveness of our proposed algorithms compared to existing approaches.
- 12 April 2026
- Published by Association for Computing Machinery (ACM)
- p. 2014-2024
Open AccessBreaking the Single-Reference-Vector Barrier in Approximate Nearest Neighbor Search
Approximate nearest neighbor (ANN) searches are commonly employed in various machine learning applications, such as recommendation systems, but traditional ANN searches typically involve only a single reference vector in a query. To broaden the capabilities of ANN search and support multi-reference-vector queries, thereby enabling a wider range of machine learning applications, we introduce all/any-k ANN search. They aim to find vectors that are similar to all or any of the multi-reference vectors in a query, respectively. To effectively and efficiently support all/any-k ANN search, we first propose distance metrics to evaluate the ranking of vectors among those in the dataset for exact all/any-k NN. Building on this, we introduce search algorithms and prove they can search according to the proposed distance metrics on graph indexes designed for traditional ANN. Additionally, we further introduce two-stage search algorithms for all/any-k ANN search to further enhance their search performance. We conduct extensive experiments on real-world datasets to validate the efficiency and effectiveness of our proposed algorithms compared to existing approaches.
- Open Access
RISK: Efficiently processing rich spatial-keyword queries on encrypted geo-textual data
Symmetric searchable encryption (SSE) for geo-textual data has attracted significant attention. However, existing schemes rely on task-specific, incompatible indices for isolated specific secure queries (e.g., range or k-nearest neighbor spatial-keyword queries), limiting practicality due to prohibitive multi-index overhead. To address this, we propose RISK, a model for rich spatial-keyword queries on encrypted geo-textual data. In a textual-first-then-spatial manner, RISK is built on a novel k-nearest neighbor quadtree (kQ-tree) that embeds representative and regional nearest neighbors, with the kQ-tree further encrypted using standard cryptographic tools (e.g., keyed hash functions and symmetric encryption). Overall, RISK seamlessly supports both secure range and k-nearest neighbor queries, is provably secure under IND-CKA2 model, and extensible to multi-party scenarios and dynamic updates. Experiments on three real-world and one synthetic datasets show that RISK outperforms state-of-the-art methods by at least 0.5 and 4 orders of magnitude in response time for 1% range queries and 10-nearest neighbor queries, respectively.
Open AccessRISK: Efficiently processing rich spatial-keyword queries on encrypted geo-textual data
Symmetric searchable encryption (SSE) for geo-textual data has attracted significant attention. However, existing schemes rely on task-specific, incompatible indices for isolated specific secure queries (e.g., range or k-nearest neighbor spatial-keyword queries), limiting practicality due to prohibitive multi-index overhead. To address this, we propose RISK, a model for rich spatial-keyword queries on encrypted geo-textual data. In a textual-first-then-spatial manner, RISK is built on a novel k-nearest neighbor quadtree (kQ-tree) that embeds representative and regional nearest neighbors, with the kQ-tree further encrypted using standard cryptographic tools (e.g., keyed hash functions and symmetric encryption). Overall, RISK seamlessly supports both secure range and k-nearest neighbor queries, is provably secure under IND-CKA2 model, and extensible to multi-party scenarios and dynamic updates. Experiments on three real-world and one synthetic datasets show that RISK outperforms state-of-the-art methods by at least 0.5 and 4 orders of magnitude in response time for 1% range queries and 10-nearest neighbor queries, respectively.
- 2 January 2026
- Published by Springer Nature
- p. 67-83
RasterPIP: Answering Point-in-Polygon Query with GPU-Native Transformation and Rasterization
- 2 January 2026
- Published by Springer Nature
- p. 67-83
RasterPIP: Answering Point-in-Polygon Query with GPU-Native Transformation and Rasterization
- 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
Beyond Vector Search: Querying With and Without Predicates
k -ANN search has been extensively studied to find k approximate nearest neighbors for a given query vector in a high-dimensional dataset, where a data item is represented as a vector. As there are many new emerging real-world applications that have categorical/numerical attributes associated with vectors, it is highly needed to support k -ANN search with additional predicates on such attributes. In this paper, we study k -ANN queries, q = (v q , c q ), where v q is a query vector and c q is a predicate on categorical/numerical attributes. Note that the conventional k -ANN search is a k -ANN query when c q = ∅. In the literature, some can support the cases when c q = ∅, some can support the cases when c q is on categorical attributes, and some can support the cases when c q is on numerical attributes. But none of them can support all cases efficiently. In this paper, we propose an all-in-one approach. Our approach supports conventional k -ANN search in the same way as the state-of-the-art approaches, and supports the predicates in a similar or even better way compared to the approaches that are tailored to support either categorical attributes or numerical attributes. We conduct extensive performance studies and confirm the accuracy and the efficiency of our approach in comparison with the state-of-the-art approaches.
- 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 AccessBeyond Vector Search: Querying With and Without Predicates
k -ANN search has been extensively studied to find k approximate nearest neighbors for a given query vector in a high-dimensional dataset, where a data item is represented as a vector. As there are many new emerging real-world applications that have categorical/numerical attributes associated with vectors, it is highly needed to support k -ANN search with additional predicates on such attributes. In this paper, we study k -ANN queries, q = (v q , c q ), where v q is a query vector and c q is a predicate on categorical/numerical attributes. Note that the conventional k -ANN search is a k -ANN query when c q = ∅. In the literature, some can support the cases when c q = ∅, some can support the cases when c q is on categorical attributes, and some can support the cases when c q is on numerical attributes. But none of them can support all cases efficiently. In this paper, we propose an all-in-one approach. Our approach supports conventional k -ANN search in the same way as the state-of-the-art approaches, and supports the predicates in a similar or even better way compared to the approaches that are tailored to support either categorical attributes or numerical attributes. We conduct extensive performance studies and confirm the accuracy and the efficiency of our approach in comparison with the state-of-the-art approaches.
- Open Access
Privacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data
In the era of cloud computing and AI, data owners outsource ubiquitous vectors to the cloud, which furnish approximate $k$-nearest neighbors ($k$-ANNS) services to users. To protect data privacy against the untrusted server, privacy-preserving $k$-ANNS (PP-ANNS) on vectors has been a fundamental and urgent problem. However, existing PP-ANNS solutions fall short of meeting the requirements of data privacy, efficiency, accuracy, and minimal user involvement concurrently. To tackle this challenge, we introduce a novel solution that primarily executes PP-ANNS on a single cloud server to avoid the heavy communication overhead between the cloud and the user. To ensure data privacy, we introduce a novel encryption method named distance comparison encryption, facilitating secure, efficient, and exact distance comparisons. To optimize the trade-off between data privacy and search performance, we design a privacy-preserving index that combines the state-of-the-art $k$-ANNS method with an approximate distance computation method. Then, we devise a search method using a filter-and-refine strategy based on the index. Moreover, we provide the security analysis of our solution and conduct extensive experiments to demonstrate its superiority over existing solutions. Based on our experimental results, our method accelerates PP-ANNS by up to 3 orders of magnitude compared to state-of-the-art methods, while not compromising the accuracy.
Open AccessPrivacy-Preserving Approximate Nearest Neighbor Search on High-Dimensional Data
In the era of cloud computing and AI, data owners outsource ubiquitous vectors to the cloud, which furnish approximate $k$-nearest neighbors ($k$-ANNS) services to users. To protect data privacy against the untrusted server, privacy-preserving $k$-ANNS (PP-ANNS) on vectors has been a fundamental and urgent problem. However, existing PP-ANNS solutions fall short of meeting the requirements of data privacy, efficiency, accuracy, and minimal user involvement concurrently. To tackle this challenge, we introduce a novel solution that primarily executes PP-ANNS on a single cloud server to avoid the heavy communication overhead between the cloud and the user. To ensure data privacy, we introduce a novel encryption method named distance comparison encryption, facilitating secure, efficient, and exact distance comparisons. To optimize the trade-off between data privacy and search performance, we design a privacy-preserving index that combines the state-of-the-art $k$-ANNS method with an approximate distance computation method. Then, we devise a search method using a filter-and-refine strategy based on the index. Moreover, we provide the security analysis of our solution and conduct extensive experiments to demonstrate its superiority over existing solutions. Based on our experimental results, our method accelerates PP-ANNS by up to 3 orders of magnitude compared to state-of-the-art methods, while not compromising the accuracy.
- Open Access
- 30 June 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 50 (4) , 1-30
Graph Based K-Nearest Neighbor Search Revisited
The problem of k -nearest neighbor ( k -NN) search is a fundamental problem to find the exact k nearest neighbor points for a user-given query point q in a d -dimensional large dataset D with n points, and the approximate k -NN ( k -ANN) search problem is to find the approximate k -NN. Both are extensively studied to support real applications. Among all approaches, the graph-based approaches have been seen as the best to support k -NN/ANN in recent studies. The state-of-the-art graph-based approach, τ-MG, finds 1-NN, \(\bar{p}_1\) , over a graph index G τ constructed for D based on a predetermined parameter τ where the distance between \(\bar{p}_1\) and q is less than τ, and finds k -ANN based on the approach taken for 1-NN. There are some main issues in τ-MG and other graph-based approaches. One is that it is difficult to predetermine τ which can ensure to find 1-NN and can do it efficiently. This is because the accuracy/efficiency is related to the size of the graph index G τ constructed. To achieve high accuracy is at the expense of efficiency. In addition, like all the other existing graph-based approaches, it does not have a theoretical guarantee to ensure k -NN for the same reason to use the same graph index, G τ , for both 1-NN and k -NN ( k > 1). In this article, we propose a new graph-based approach for k -NN with a theoretical guarantee. We construct a labeled graph, \(\mathcal {G}\) , and we do not need to predetermine τ. Instead, we find 1-NN over a subgraph, \(\mathcal {G}_{\dot{\tau }}\) , of \(\mathcal {G}\) , virtually constructed in a dynamic manner. Here, \(\dot{\tau }\) we use is query-dependent and can be smaller than τ, and the subgraph \(\mathcal {G}_{\dot{\tau }}\) is smaller than G τ when \(\dot{\tau }= \tau\) . We find k -NN in two phases. In the navigation phase, we find 1-NN, \(\bar{p}_1\) , of q over \(\mathcal {G}_{\dot{\tau }}\) . In the second refinement phase, for k > 1, we explore the neighbors within the vicinity region of \(\bar{p}_1\) in \(\mathcal {G}\) . Based on our solution for k -NN in theory, we propose new algorithms to support k -ANN efficiently in practice. We conduct extensive performance studies and confirm the effectiveness and efficiency of our new approach.- 30 June 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 50 (4) , 1-30
Open AccessGraph Based K-Nearest Neighbor Search Revisited
The problem of k -nearest neighbor ( k -NN) search is a fundamental problem to find the exact k nearest neighbor points for a user-given query point q in a d -dimensional large dataset D with n points, and the approximate k -NN ( k -ANN) search problem is to find the approximate k -NN. Both are extensively studied to support real applications. Among all approaches, the graph-based approaches have been seen as the best to support k -NN/ANN in recent studies. The state-of-the-art graph-based approach, τ-MG, finds 1-NN, \(\bar{p}_1\) , over a graph index G τ constructed for D based on a predetermined parameter τ where the distance between \(\bar{p}_1\) and q is less than τ, and finds k -ANN based on the approach taken for 1-NN. There are some main issues in τ-MG and other graph-based approaches. One is that it is difficult to predetermine τ which can ensure to find 1-NN and can do it efficiently. This is because the accuracy/efficiency is related to the size of the graph index G τ constructed. To achieve high accuracy is at the expense of efficiency. In addition, like all the other existing graph-based approaches, it does not have a theoretical guarantee to ensure k -NN for the same reason to use the same graph index, G τ , for both 1-NN and k -NN ( k > 1). In this article, we propose a new graph-based approach for k -NN with a theoretical guarantee. We construct a labeled graph, \(\mathcal {G}\) , and we do not need to predetermine τ. Instead, we find 1-NN over a subgraph, \(\mathcal {G}_{\dot{\tau }}\) , of \(\mathcal {G}\) , virtually constructed in a dynamic manner. Here, \(\dot{\tau }\) we use is query-dependent and can be smaller than τ, and the subgraph \(\mathcal {G}_{\dot{\tau }}\) is smaller than G τ when \(\dot{\tau }= \tau\) . We find k -NN in two phases. In the navigation phase, we find 1-NN, \(\bar{p}_1\) , of q over \(\mathcal {G}_{\dot{\tau }}\) . In the second refinement phase, for k > 1, we explore the neighbors within the vicinity region of \(\bar{p}_1\) in \(\mathcal {G}\) . Based on our solution for k -NN in theory, we propose new algorithms to support k -ANN efficiently in practice. We conduct extensive performance studies and confirm the effectiveness and efficiency of our new approach. - Open Access
- 17 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-26
Fast Approximate Similarity Join in Vector Databases
Recent advancements in deep learning, particularly in embedding models, have enabled the effective representation of various data types such as text, images, and audio as vectors, thereby facilitating semantic analysis. A large number of massive vector datasets are maintained in vector databases. Approximate similarity join is a core operation in vector database systems that joins two datasets, and outputs all pairs of vectors from the two datasets, if the distance between such a pair of two vectors is no more than a specified value. Existing approaches for similarity join are selection-based such that they treat each data point in a dataset as an individual query point to search data points by an approximate range query in another dataset. Such methods do not fully capitalize on the inherent properties of the join operation itself. In this paper, we propose a new join algorithm, SimJoin. Our join algorithm aims at boosting join processing efficiency by leveraging relationships between partial join results (e.g., join windows). In brief, our join algorithm accelerates the join processing to process a join window by utilizing the join windows from the processed data points. Then, we discuss optimizing join window order to minimize join costs. In addition, we discuss how to support k -similarity join, and how to maintain proximity graph index based on k-similarity join. Extensive experiments on real-world and synthetic datasets demonstrate the significant performance superiority of our proposed algorithms over existing state-of-the-art methods.
- 17 June 2025
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Management of Data
- Vol. 3 (3) , 1-26
Open AccessFast Approximate Similarity Join in Vector Databases
Recent advancements in deep learning, particularly in embedding models, have enabled the effective representation of various data types such as text, images, and audio as vectors, thereby facilitating semantic analysis. A large number of massive vector datasets are maintained in vector databases. Approximate similarity join is a core operation in vector database systems that joins two datasets, and outputs all pairs of vectors from the two datasets, if the distance between such a pair of two vectors is no more than a specified value. Existing approaches for similarity join are selection-based such that they treat each data point in a dataset as an individual query point to search data points by an approximate range query in another dataset. Such methods do not fully capitalize on the inherent properties of the join operation itself. In this paper, we propose a new join algorithm, SimJoin. Our join algorithm aims at boosting join processing efficiency by leveraging relationships between partial join results (e.g., join windows). In brief, our join algorithm accelerates the join processing to process a join window by utilizing the join windows from the processed data points. Then, we discuss optimizing join window order to minimize join costs. In addition, we discuss how to support k -similarity join, and how to maintain proximity graph index based on k-similarity join. Extensive experiments on real-world and synthetic datasets demonstrate the significant performance superiority of our proposed algorithms over existing state-of-the-art methods.