Shangqi Lu

Department of Computer Science and Engineering
The Chinese University of Hong Kong
Shatin, N.T., Hong Kong, China

Email: sqlu@cse.cuhk.edu.hk

Biography

Shangqi Lu is a research engineer at Huawei. He was a PhD student in the Department of Computer Science and Engineering, the Chinese University of Hong Kong and under the supervision of Prof. Yufei Tao from 2018 to 2022. He will receive his PhD degree in 2022.

Research Interests

Algorithms on massive data sets with theoretical guarantees.

Publications

In publications marked with '**', authors are ordered alphabetically, as is a convention of theory papers. In the other publications, authors are ordered by contribution.

• Joint work with Shiyuan Deng and Yufei Tao.
  **On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms.
  To appear in Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2023.


• Joint work with Yufei Tao.
  **Indexing for Keyword Search with Structured Constraints.
  To appear in Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), 2023.


• Joint work with Shiyuan Deng and Yufei Tao.
  **Space-Query Tradeoffs in Range Subgraph Counting and Listing.
  To appear in Proceedings of the 26th International Conference on Database Theory (ICDT), 2023.


• Joint work with Yufei Tao.
  **Range Updates and Range Sum Queries on Multidimensional Points with Monoid Weights.
  To appear in Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC), 2022.


• Joint work with Wim Martens, Matthias Niewerth, and Yufei Tao.
  **Optimal Algorithms for Multiway Search on Partial Orders.
  Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 175-187, 2022.


• Joint work with Abolfazl Asudeh, Das Gautam, H.V. Jagadish, Azade Nazi, Yufei Tao, Nan Zhang, and Jianwen Zhao.
  **On Finding Rank Regret Representatives.
  ACM Transactions on Database Systems (TODS), 2022.


• Joint work with 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. [slides]


• 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.

Honors & Awards

CCF Outstanding Undergraduate Award, 2017
National Scholarship in China, 2017, 2016 and 2015

Teaching

Teaching Assistant of CMSC5724 Data Mining and Knowledge Discovery.
Teaching Assistant of ENGG1410 Linear Algebra and Vector Calculus.
Teaching Assistant of CSCI2100 Data Structures.
Teaching Assistant of CSCI3160 Design and Analysis of Algorithms.
Teaching Assistant of CSCI5010 Practical Computational Geometry Algorithms.