Jiadong Xie
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
Jiadong Xie has a total of 23 co-authors. Here are the top co-authors by number of shared publications:
- Jeffrey Xu Yu
The Chinese University of Hong Kong, Hong Kong, China
8 shared publications - Fan Zhang
Guangzhou University, Guangzhou, China
6 shared publications - Siyi Teng
The Chinese University of Hong Kong, Shatin, Hong Kong
6 shared publications - Yingfan Liu
Xidian University, Xian, China
6 shared publications - Kai Wang
Shanghai Jiao Tong University
5 shared publications - Wenjie Zhang
University of New South Wales
3 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
- 11 July 2026
- Published by Springer Nature in The VLDB Journal
- Vol. 35 (5) , 39
Efficient discovery of arbitrary cycles in large-scale networks
- 11 July 2026
- Published by Springer Nature in The VLDB Journal
- Vol. 35 (5) , 39
Efficient discovery of arbitrary cycles in large-scale networks
- 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
- 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.
- 1 November 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 37 (6) , 1587-1604
Influence Minimization via Blocking Strategies
We study the influence minimization problem: given a graph G and a seed set S, blocking at most b nodes or b edges such that the influence spread of seed set is minimized. This is a pivotal yet underexplored aspect of network analytics, which can limit the spread of undesirable phenomena in networks, such as misinformation and epidemics. Given the inherent NP-hardness of the problem under the independent cascade and linear threshold models, previous studies have employed greedy algorithms and Monte Carlo Simulations for its resolution. However, existing techniques become cost-prohibitive when applied to large networks due to the necessity of enumerating all the candidate blockers and computing the decrease in expected spread from blocking each of them. This significantly restricts the practicality and effectiveness of existing methods, especially when prompt decision making is crucial. In this paper, we propose the AdvancedGreedy algorithm, which utilizes a novel graph sampling technique that incorporates the dominator tree structure. We find that AdvancedGreedy can achieve a [ ]-approximation in the problem under the linear threshold model. For the problem under the independent cascade model, we further propose a novel heuristic algorithm GreedyReplace, based on identifying the relationships among candidate blockers. Experimental evaluations on real-life networks reveal that our proposed algorithms exhibit a significant enhancement in efficiency, surpassing the state-of-the-art algorithm by three orders of magnitude while achieving high effectiveness. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: K. Wang was supported by the National Natural Science Foundation of China [Grants 72221001 and 62302294]. J. Liu was supported by the National Natural Science Foundation of China [Grants 72221001 and 72402127] and Shanghai Pujiang Program [Grant 23PJC059]. F. Zhang was supported by the Guangdong Basic and Applied Basic Research Foundation [Grants 2023A1515012603 and 2024A1515011501]. W. Zhang was supported by the Australian Research Council [Grant FT210100303]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0591 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0591 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 1 November 2025
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 37 (6) , 1587-1604
Influence Minimization via Blocking Strategies
We study the influence minimization problem: given a graph G and a seed set S, blocking at most b nodes or b edges such that the influence spread of seed set is minimized. This is a pivotal yet underexplored aspect of network analytics, which can limit the spread of undesirable phenomena in networks, such as misinformation and epidemics. Given the inherent NP-hardness of the problem under the independent cascade and linear threshold models, previous studies have employed greedy algorithms and Monte Carlo Simulations for its resolution. However, existing techniques become cost-prohibitive when applied to large networks due to the necessity of enumerating all the candidate blockers and computing the decrease in expected spread from blocking each of them. This significantly restricts the practicality and effectiveness of existing methods, especially when prompt decision making is crucial. In this paper, we propose the AdvancedGreedy algorithm, which utilizes a novel graph sampling technique that incorporates the dominator tree structure. We find that AdvancedGreedy can achieve a [ ]-approximation in the problem under the linear threshold model. For the problem under the independent cascade model, we further propose a novel heuristic algorithm GreedyReplace, based on identifying the relationships among candidate blockers. Experimental evaluations on real-life networks reveal that our proposed algorithms exhibit a significant enhancement in efficiency, surpassing the state-of-the-art algorithm by three orders of magnitude while achieving high effectiveness. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: K. Wang was supported by the National Natural Science Foundation of China [Grants 72221001 and 62302294]. J. Liu was supported by the National Natural Science Foundation of China [Grants 72221001 and 72402127] and Shanghai Pujiang Program [Grant 23PJC059]. F. Zhang was supported by the Guangdong Basic and Applied Basic Research Foundation [Grants 2023A1515012603 and 2024A1515011501]. W. Zhang was supported by the Australian Research Council [Grant FT210100303]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0591 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0591 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
- 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.
- Open Access
- 30 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 803-817
Groot: Graph-Centric Row Reordering with Tree for Sparse Matrix Multiplications on Tensor Cores
- 30 March 2025
- Published by Association for Computing Machinery (ACM)
- p. 803-817
Open AccessGroot: Graph-Centric Row Reordering with Tree for Sparse Matrix Multiplications on Tensor Cores
- Open Access
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 606-617
Optimizing Network Resilience via Vertex Anchoring
Network resilience is a critical ability of a network to maintain its functionality against disturbances. A network is resilient/robust when a large portion of the nodes are to be better engaged in the network, i.e., they are less likely to leave given the changes on the network. Existing studies validate that the engagement of a node can be well captured by its coreness on network topology. Therefore, it is promising to maximize the number of nodes with increasing coreness values. In this paper, we propose and study thefollower maximization problem: maximizing the resilience gain (the number of coreness-increased vertices) via anchoring a set of vertices within a given budget. We prove that the problem is NP-hard and W[2]-hard, and it is NP-hard to approximate within an O(n^1-ε ) factor. We first propose an advanced greedy approach, followed by a time-dependent framework designed to quickly find high-quality results. The framework is initialized by the advanced greedy algorithm and incorporates novel techniques for optimizing the search space. The effectiveness and efficiency of our solution are verified with extensive experiments on 8 real-life datasets. Our source codes are available at https://github.com/Tsyxxxka/Follower-Maximization.
- 13 May 2024
- Published by Association for Computing Machinery (ACM)
- p. 606-617
Open AccessOptimizing Network Resilience via Vertex Anchoring
Network resilience is a critical ability of a network to maintain its functionality against disturbances. A network is resilient/robust when a large portion of the nodes are to be better engaged in the network, i.e., they are less likely to leave given the changes on the network. Existing studies validate that the engagement of a node can be well captured by its coreness on network topology. Therefore, it is promising to maximize the number of nodes with increasing coreness values. In this paper, we propose and study thefollower maximization problem: maximizing the resilience gain (the number of coreness-increased vertices) via anchoring a set of vertices within a given budget. We prove that the problem is NP-hard and W[2]-hard, and it is NP-hard to approximate within an O(n^1-ε ) factor. We first propose an advanced greedy approach, followed by a time-dependent framework designed to quickly find high-quality results. The framework is initialized by the advanced greedy algorithm and incorporates novel techniques for optimizing the search space. The effectiveness and efficiency of our solution are verified with extensive experiments on 8 real-life datasets. Our source codes are available at https://github.com/Tsyxxxka/Follower-Maximization.