About Me

Shangqi Lu is currently an Assistant Professor at the Hong Kong University of Science and Technology (Guangzhou) in the Data Science and Analytics Thrust. Prior to this, he was a Research Engineer at Huawei. He obtained his doctoral degree in 2022 at the Chinese University of Hong Kong, honorably advised by Prof. Yufei Tao. He obtained his bachelor’s degree from the Northwestern Polytechnical University in 2018.

Email: shangqilu@hkust-gz.edu.cn

Research Interests. Designing algorithms with non-trivial theoretical guarantees and applying them to practical database systems. My focus lies in exploring topics such as database query processing, high-dimensional computational geometry, information retrieval, and machine learning.

I am looking for PhD students and Research Assistants. Please send me your CV and detailed transcript if you are interested. The accepted student is expected to research on both practical and theoretical algorithms on large-scale data.

Publications

In publications marked with `**’, authors are ordered alphabetically, as is a convention of theory papers.

• Shangqi Lu and Yufei Tao. **Proximity Graphs for Similarity Search: Fast Construction, Lower Bounds, and Euclidean Separation. To appear in the Proceedings of ACM Symposium on Principles of Database Systems (PODS), 2026.
• Shangqi Lu, Ru Wang, and Yufei Tao. Interactive Graph Search Made Simple. Proceedings of ACM Conference on Management of Data (SIGMOD), 2025.
• Ru Wang, Shangqi Lu, and Yufei Tao. An Index for Set Intersection with Post-Filtering. IEEE Transactions on Knowledge and Data Engineering (TKDE), 2024.
• Shangqi Lu, Wim Martens, Matthias Niewerth, and Yufei Tao. **Partial Order Multiway Search. ACM Transactions on Database Systems (TODS), 48(4): 10:1-10:31, 2023. (Special issue of PODS’22).
• Shangqi Lu and Yufei Tao. **Indexing for Keyword Search with Structured Constraints. Proceedings of the 42nd ACM Symposium on Principles of Database Systems (PODS), pages 263-275, 2023.
• Shiyuan Deng, Shangqi Lu, and Yufei Tao. **On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms. Proceedings of the 42nd ACM Symposium on Principles of Database Systems (PODS), pages 99-111, 2023.
• Shiyuan Deng, Shangqi Lu, and Yufei Tao. **Space-Query Tradeoffs in Range Subgraph Counting and Listing. Proceedings of the 26th International Conference on Database Theory (ICDT), pages 6:1-6:25, 2023.
• Shangqi Lu and Yufei Tao. **Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights. Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC), pages 57:1-57:16, 2022. Computational Geometry: Theory and Applications, 115:102030, 2023.
• Abolfazl Asudeh, Das Gautam, HV Jagadish, Shangqi Lu, Azade Nazi, and Yufei Tao, et al. **On Finding Rank Regret Representatives. ACM Transactions on Database Systems (TODS), 47(3): 10:1-10:37, 2022.
• Shangqi Lu, Wim Martens, Matthias Niewerth, and Yufei Tao. **Optimal Algorithms for Multiway Search on Partial Orders. Proceedings of the 41st ACM Symposium on Principles of Database Systems (PODS), pages 175-187, 2022 (ACM SIGMOD Research Highlight Award 2023).
• Shangqi Lu and Yufei Tao. **Towards Optimal Dynamic Indexes for Approximate (and Exact) Triangle Counting. Proceedings of the 24th International Conference on Database Theory (ICDT), pages 6:1-6:23, 2021.
• Yufei Tao and Shangqi Lu. From Online to Non-i.i.d. Batch Learning. Proceedings of the 26th ACM International Conference On Knowledge Discovery and Data Mining (SIGKDD), pages 328-337, 2020.

Awards

• SIGMOD Research Highlight Award 2023
• CCF Outstanding Undergraduate Award 2017
• National Scholarship in China, 2015, 2016, 2017

Teaching

• Instructor: UFUG2602 Data Structure and Algorithm Design, Spring 2024-25
• Teaching Assistant: CSCI5010 Practical Computational Geometry Algorithms, Spring 2021
• Teaching Assistant: CMSC5724 Data Mining and Knowledge Discovery, Fall 2018, Fall 2019, Fall 2020
• Teaching Assistant: CSCI2100 Data Structures, Fall 2018, Fall 2020
• Teaching Assistant: CSCI3160: Design and Analysis of Algorithms, Fall 2019

Services

• ACM TODS Reviewers Board Member
• ICDE 2026 PC member