Publications

My DBLP Computer Science Bibliography entry and Google Scholar Citations entry are also available.

Note: Authors names are usually in alphabetical order, following the convention in theoretical computer science. There are two exceptions when researchers in a differen research area were involved.

Referred Journal Publications

  1. Meng He and Serikzhan Kazi, Path and Ancestor Queries over Trees with Multidimensional Weight Vectors, accepted to Computing in Geometry and Topology subject to revision.
  2. Jingbang Chen, Meng He, Ian Munro, Richard Peng, Kaiyu Wu and Daniel Zhang, Distance Queries over Dynamic Interval Graphs, accepted to Computational Geometry - Theory and Applications (special issue for the 33rd International Symposium on Algorithms and Computation) upon minor revision.
  3. Meng He and Serikzhan Kazi, Data Structures for Categorical Path Counting Queries, Theoretical Computer Science, Volume 938, pages 97-111, November 2022.
  4. Travis Gagie, Meng He, Gonzalo Navarro and Carlos Ochoa, Tree Path Majority Data Structures, Theoretical Computer Science, Volume 833, pages 107-119, September 2020.
  5. Leo Ferres, José Fuentes Sepúlveda, Travis Gagie, Meng He and Gonzalo Navarro, Fast and Compact Planar Embeddings, Computational Geometry - Theory and Applications, Volume 89 (special issue for the 15th Algorithms and Data Structures Symposium), Article No. 101630, 21 pages, August 2020.
  6. Travis Gagie, Meng He and Gonzalo Navarro, Compressed Dynamic Range Majority and Minority Data Structures, Algorithmica, Volume 82, Issue 7, pages 2063-2086, February 2020.
  7. Travis Gagie, Meng He and Gonzalo Navarro, Path Queries on Functions, Theoretical Computer Science, Volume 770 (special issue for the 28th Annual Symposium on Combinatorial Pattern Matching), pages 34-50, May 2019.
  8. Meng He, J. Ian Munro and Gelin Zhou, Dynamic Path Queries in Linear Space, Algorithmica, Volume 80, Issue 12, pages 3728-3765, December 2018.
  9. José Fuentes Sepúlveda, Leo Ferres, Meng He and Norbert Zeh, Parallel Construction of Succinct Trees, Theoretical Computer Science, Volume 700, pages 1-22, November 2017.
  10. Timothy M. Chan, Meng He, J. Ian Munro and Gelin Zhou, Succinct Indices for Path Minimum, with Applications, Algorithmica, Volume 78, Issue 2, pages 453-491, June 2017.
  11. Craig Dillabaugh, Meng He, Anil Maheshwari and Norbert Zeh, I/O and Space-Efficient Path Traversal in Planar Graphs, Algorithmica, Volume 77, Issue 3, pages 714-755, March 2017.
  12. Amr Elmasry, Meng He, J. Ian Munro and Patrick K. Nicholson, Dynamic Range Majority Data Structures, Theoretical Computer Science, Volume 647, pages 59-73, September 2016.
  13. Meng He, J. Ian Munro and Gelin Zhou, Data Structures for Path Queries, ACM Transactions on Algorithms, Volume 12, Issue 4, pages 53:1-53:32, September 2016.
  14. Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz and Diego Seco, On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods, Theory of Computing Systems, Volume 56, Issue 1 (special issue for the 10th Workshop on Approximation and Online Algorithms), pages 220-250, January 2015.
  15. Meng He, J. Ian Munro and Gelin Zhou, A Framework for Succinct Labeled Ordinal Trees over Large Alphabets, Algorithmica, Volume 70, Issue 4 (special issue for the 23rd International Symposium on Algorithms and Computation), pages 696-717, December 2014.
  16. Meng He and J. Ian Munro, Space Efficient Data Structures for Dynamic Orthogonal Range Counting, Computational Geometry - Theory and Applications, Volume 47, Issue 2, Part B (special issue for the 12th Algorithms and Data Structures Symposium), pages 268-281, February 2014.
  17. Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson and Matthew Skala, Range Majority in Constant Time and Linear Space, Information and Computation, Volume 222 (special issue for the 38th International Colloquium on Automata, Language, and Programming), Pages 169–179, January 2013.
  18. Meng He, J. Ian Munro and S. Srinivasa Rao, Succinct Ordinal Trees Based on Tree Covering, ACM Transactions on Algorithms, Volume 8, Issue 4, pages 42:1-42:34, September 2012.
  19. Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari and Pat Morin, Succinct Geometric Indexes Supporting Point Location Queries, ACM Transactions on Algorithms, Volume 8, Issue 2, pages 10:1-10:26, April 2012.
  20. Craig Dillabaugh, Meng He, Anil Maheshwari, Succinct and I/O Efficient Data Structures for Traversal in Trees, in Algorithmica, Volume 63, Numbers 1-2, pages 201-223, January 2012.
  21. Jérémy Barbay, Luca Castelli Aleardi, Meng He, J. Ian Munro, Succinct Representation of Labeled Graphs, in Algorithmica, Volume 62, Numbers 1-2, pages 224-257, January 2012.
  22. Jérémy Barbay, Meng He, J. Ian Munro and S. Srinivasa Rao, Succinct Indexes for Strings, Binary Relations and Multilabeled Trees, ACM Transactions on Algorithms, Volume 7, Issue 4, pages 52:1-52:27, September 2011.
  23. Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger and Matthew Skala, Untangled Monotonic Chains and Adaptive Range Search, in Theoretical Computer Science, Volume 412, Issue 32 (special issue for the 20th International Symposium on Algorithms and Computation), pages 4200-4211, July 2011.

Referred Conference Publications

  1. Meng He and Kaiyu Wu, Optimal Distance Labeling Scheme for Interval Graphs, to appear in Proceedings of the 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024), June 2024.
  2. Meng He, J. Ian Munro and Kaiyu Wu, Succinct Data Structures for Bounded Degree/Chromatic Number Interval Graphs, in Proceedings of the 34th Data Compression Conference (DCC 2024), 10 pages, March 2024.
  3. Meng He, J. Ian Munro and Kaiyu Wu, Succinct Data Structures for Path Graphs and Chordal Graphs Revisited, in Proceedings of the 34th Data Compression Conference (DCC 2024), 10 pages, March 2024.
  4. Younan Gao and Meng He, On Approximate Colored Path Counting, in Proceedings of the 16th Latin American Theoretical Informatics Symposium (LATIN 2024), pages 209-224, March 2024.
  5. Jingbang Chen, Meng He, Ian Munro, Richard Peng, Kaiyu Wu and Daniel Zhang, Distance Queries over Dynamic Interval Graphs, in Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2023), pages 18:1-18:19, December 2023.
  6. Xing Lyu, Travis Gagie, Meng He, Yakov Nekrich and Norbert Zeh, Sum-of-Local-Effects Data Structures for Separable Graphs, in Proceedings of the 29th International Computing and Combinatorics Conference (COCOON 2023), pages 195-206, December 2023.
  7. Travis Gagie, Meng He and Michael St Denis, Dynamic Compact Planar Embeddings, in Proceedings of the 30th International Symposium on String Processing and Information Retrieval (SPIRE 2023), pages 233-245, September 2023.
  8. Meng He and Zhen Liu, Exact and Approximate Range Mode Query Data Structures in Practice, in Proceedings of the 21st Symposium on Experimental Algorithms (SEA 2023), pages 19:1-19:22, July 2023.
  9. Rathish Das, Meng He, Eitan Kondratovsky, Ian Munro, Anurag Murty Naredla and Kaiyu Wu, Shortest Beer Path Queries in Interval Graphs, in Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC 2022), pages 59:1-59:17, December 2022.
  10. Rathish Das, Meng He, Eitan Kondratovsky, J. Ian Munro, Kaiyu Wu, Internal Masked Prefix Sums and Its Connection to Fully Internal Measurement Queries, in Proceedings of the 29th International Symposium on String Processing and Information Retrieval (SPIRE 2022), pages 217-232, November 2022.
  11. Younan Gao and Meng He, Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product, in Proceedings of the 30th Annual European Symposium on Algorithms (ESA 2022), pages 59:1-59:15, September 2022.
  12. Younan Gao and Meng He, Space Efficient Two-Dimensional Orthogonal Colored Range Counting, in Proceedings of the 29th Annual European Symposium on Algorithms (ESA 2021), pages 46:1-46:17, September 2021.
  13. Meng He and Serikzhan Kazi, Data Structures for Categorical Path Counting Queries, in Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), pages 15:1-15:17, July 2021.
  14. Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild and Kaiyu Wu, Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees, in Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), pages 25:1-25:18, December 2020.
  15. Younan Gao, Meng He and Yakov Nekritch, Fast Preprocessing for Optimal Orthogonal Range Reporting and Range Successor with Applications to Text Indexing, in Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020), pages 54:1-54:18, September 2020.
  16. Meng He and Serikzhan Kazi, Path Query Data Structures in Practice, in Proceedings of the 18th International Symposium on Experimental Algorithms (SEA 2020), pages 27:1-27:16, June 2020.
  17. Hicham El-Zein, Meng He, J. Ian Munro, Yakov Nekrich and Bryce Sandlund, On Approximate Range Mode and Range Selection, in Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), pages 57:1-57:14, December 2019.
  18. Meng He and Serikzhan Kazi, Path and Ancestor Queries on Trees with Multidimensional Weight Vectors, in Proceedings of the 30th International Symposium on Algorithms and Computation (ISAAC 2019), pages 45:1-45:17, December 2019.
  19. Travis Gagie, Meng He and Gonzalo Navarro, Tree Path Majority Data Structures, in Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), pages 68:1-68:12, December 2018.
  20. Hicham El-Zein, Meng He, J. Ian Munro and Bryce Sandlund, Improved Time and Space Bounds for Dynamic Range Mode and Least Frequent Element, in Proceedings of the 26th Annual European Symposium on Algorithms (ESA 2018), pages 25:1-25:13, August 2018.
  21. Meng He, Cuong Nguyen and Norbert Zeh, Maximal and Convex Layers of Random Point Sets, in Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN 2018), pages 597-610, April 2018.
  22. Meng He, Richard Peng and Yinzhan Xu, Parameterizing the Hardness of Binary Search Tree Access Sequences by Inversion Counts, in Proceedings of the 15th Workshop on Analytic Algorithmics and Combinatorics (ANALCO 2018), pages 32-39, January 2018.
  23. Zichu Ai, Jie Mei, Abidalrahaman Mohammed, Meng He, Norbert Zeh and Evangelos Milios, A High Performance Computational Framework for Phrase Relatedness, in Proceedings of the 17th ACM Symposium on Document Engineering (DocEng 2017), pages 145-148, September 2017.
  24. Leo Ferres, José Fuentes Sepúlveda, Travis Gagie, Meng He and Gonzalo Navarro, Fast and Compact Planar Embeddings, in Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017), pages 385-396, August 2017.
  25. Travis Gagie, Meng He and Gonzalo Navarro, Path Queries on Functions, in Proceedings of the 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017), pages 5:1-5:15, July 2017. Note: This paper won the Alberto Apostolico Best Paper Award of CPM 2017.
  26. Travis Gagie, Meng He and Gonzalo Navarro, Compressed Dynamic Range Majority Data Structures, in Proceedings of the 27th Data Compression Conference (DCC 2017), pages 260-269, April 2017.
  27. Meng He and Mengdu Li, Deletion without Rebalancing in Non-Blocking Binary Search Trees, in Proceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016), pages 34：1-34：17, December 2016.
  28. Meng He and Chen Miao, Engineering Wavelet Trees Implementations for Compressed Web Graph Representations, in Proceedings of the 26th Data Compression Conference (DCC 2016), page 603, April 2016.
  29. Leo Ferres, José Fuentes Sepúlveda, Meng He and Norbert Zeh, Parallel Construction of Succinct Trees, in Proceedings of the 14th International Symposium on Experimental Algorithms (SEA 2015), pages 3-14, June 2015.
  30. Meng He, J. Ian Munro and Gelin Zhou, Dynamic Path Counting and Reporting in Linear Space, in Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), pages 565-577, December 2014.
  31. Meng He, Ganggui Tang and Norbert Zeh, Orienting Dynamic Graphs, with Applications to Maximal Matchings and Adjacency Queries, in Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), pages 128-140, December 2014.
  32. Timothy M. Chan, Meng He, J. Ian Munro and Gelin Zhou, Succinct Indices for Path Minimum, with Applications to Path Reporting, in Proceedings of the 22nd European Symposium on Algorithms (ESA 2014), pages 247-259, September 2014.
  33. Robert Fraser, Meng He, Akitoshi Kawamura, Alejandro López-Ortiz, J. Ian Munro and Patrick K. Nicholson, The Distance 4-Sector of Two Points is Unique, in Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC 2013), pages 612-622, December 2013.
  34. Meng He, Succinct and Implicit Data Structures for Computational Geometry, in Proceedings of the Conference on Space Efficient Data Structures, Streams and Algorithms, pages 216-235, August 2013.
  35. Meng He, J. Ian Munro and Gelin Zhou, A Framework for Succinct Labeled Ordinal Trees over Large Alphabets, in Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), pages 537-547, December 2012.
  36. Meng He, Patrick K. Nicholson and Norbert Zeh, A Space-Efficient Framework for Dynamic Point Location, in Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), pages 548-557, December 2012.
  37. Reza Dorrigiv, Meng He and Norbert Zeh, On the Advice Complexity of Buffer Management, in Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), pages 136-145, December 2012.
  38. Reza Dorrigiv, Robert Fraser, Meng He, Shahin Kamali, Akitoshi Kawamura, Alejandro López-Ortiz and Diego Seco, On Minimum- and Maximum-Weight Minimum Spanning Trees with Neighborhoods, in Proceedings of the 10th Workshop on Approximation and Online Algorithms (WAOA 2012), pages 93-106, September 2012.
  39. Meng He, J. Ian Munro and Gelin Zhou, Succinct Data Structures for Path Queries, in Proceedings of the 20th European Symposium on Algorithms (ESA 2012), pages 575-586, September 2012.
  40. Meng He, J. Ian Munro and Gelin Zhou, Path Queries in Weighted Trees, in Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), pages 140-149, December 2011.
  41. Meng He, J. Ian Munro and Patrick K. Nicholson, Dynamic Range Selection in Linear Space, in Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), pages 160-169, December 2011.
  42. Amr Elmasry, Meng He, J. Ian Munro and Patrick K. Nicholson, Dynamic Range Majority Data Structures, in Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), pages 150-159, December 2011.
  43. Travis Gagie, Meng He, J. Ian Munro and Patrick K. Nicholson, Finding Frequent Elements in Compressed 2D Arrays and Strings, in Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011), pages 295-300, October 2011.
  44. Meng He and J. Ian Munro, Space Efficient Data Structures for Dynamic Orthogonal Range Counting, in Proceedings of the 12th Algorithms and Data Structures Symposium (WADS 2011), pages 500-511, August 2011. (slides)
  45. Stephane Durocher, Meng He, J. Ian Munro, Patrick K. Nicholson and Matthew Skala1a, Range Majority in Constant Time and Linear Space, in Proceedings of the 38th International Colloquium on Automata, Language, and Programming (ICALP 2011), pages 244-255, July 2011.
  46. Meng He and J. Ian Munro, Succinct Representations of Dynamic Strings, in Proceedings of the 17th International Symposium on String Processing and Information Retrieval (SPIRE 2010), pages 334-346, October 2010. (slides)
  47. Craig Dillabaugh, Meng He, Anil Maheshwari and Norbert Zeh, I/O and Space-Efficient Path Traversal in Planar Graphs, in Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), pages 1175-1184, December 2009. (slides)
  48. Diego Arroyuelo, Francisco Claude, Reza Dorrigiv, Stephane Durocher, Meng He, Alejandro López-Ortiz, J. Ian Munro, Patrick K. Nicholson, Alejandro Salinger and Matthew Skala, Untangled Monotonic Chains and Adaptive Range Search, in Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), pages 203-212, December 2009.
  49. Prosenjit Bose, Meng He, Anil Maheshwari and Pat Morin, Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing, in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009), pages 98-109, August 2009. (slides)
  50. Prosenjit Bose, Eric Y. Chen, Meng He, Anil Maheshwari and Pat Morin, Succinct Geometric Indexes Supporting Point Location Queries, in Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 635-644, January 2009. (slides)
  51. Craig Dillabaugh, Meng He and Anil Maheshwari, Succinct and I/O Efficient Data Structures for Traversal in Trees, Proceedings of the 19th International Symposium on Algorithms and Computation (ISAAC 2008), pages 112-123, December 2008.
  52. Jérémy Barbay, Luca Castelli Aleardi, Meng He and J. Ian Munro, Succinct Representation of Labeled Graphs, in Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007), pages 316-328, December 2007. (slides)
  53. Meng He, J. Ian Munro and S. Srinivasa Rao, Succinct Ordinal Trees Based on Tree Covering, in Proceedings of the 34th International Colloquium on Automata, Language, and Programming (ICALP 2007), pages 509-520, July 2007. (slides)
  54. Jérémy Barbay, Meng He, J. Ian Munro and S. Srinivasa Rao, Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees, in Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pages 680-689, January 2007. (slides)
  55. Meng He, J. Ian Munro and S. Srinivasa Rao, A Categorization Theorem on Suffix Arrays with Applications to Space Efficient Text Indexes, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), pages 23-32, January 2005. (slides)

Referred Book Chapters

  1. Meng He, Succinct Data Structures for Parentheses Matching, refereed book chapter in Encyclopedia of Algorithms, Ming-Yang Kao et al. (editors), pages 912-915, July 2008.

Books and Journals Edited

  1. Special issue on the 33rd Canadian Conference on Computational Geometry (CCCG), Computational Geometry - Theory and Applications, Meng He and Don Sheehy, editors, January 2024.
  2. Special issue for selected papers of WADS 2021, Computational Geometry - Theory and Applications, Anna Lubiw, Mohammad Salavatipour and Meng He, editors, March 2023.
  3. Special issue on Algorithms and Data Structures (WADS 2021), Algorithmica, Anna Lubiw, Mohammad Salavatipour and Meng He, editors, March 2023.
  4. Proceedings of the 17th International Symposium on Data Structures and Algorithms, Anna Lubiw, Mohammad Salavatipour, Meng He, editors, August 2021.
  5. Proceedings of the 33rd Canadian Conference on Computational Geometry, Meng He and Don Sheehy, editors, August 2021.
  6. Special issue on the 26th Canadian Conference on Computational Geometry (CCCG), Computational Geometry - Theory and Applications, volume 77, March 2019.
  7. Proceedings of the 26th Canadian Conference on Computational Geometry, Meng He and Norbert Zeh, editors, August 2014.

PhD Thesis