Ziyang Men

Ziyang Men

Auto-generated profile, based on publicly available information

Ziyang Men

University of California, Riverside, Riverside, USA

Research Focus & Metrics

Academic Career Length

4Years (2023-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
10 February 2025 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
ZMZiyang Men
Ziyang Men
ZSZheqi Shen
Zheqi Shen
YGYan Gu
Yan Gu
YSYihan Sun
Yihan Sun
The kd-tree is one of the most widely used data structures to manage multi-dimensional data. Due to the ever-growing data volume, it is imperative to consider parallelism in kd-trees. However, we observed challenges in existing parallel kd-tree implementations, for both constructions and updates. The goal of this paper is to develop efficient in-memory kd-trees by supporting high parallelism and cache-efficiency. We propose the Pkd-tree (Parallel kd-tree), a parallel kd-tree that is efficient both in theory and in practice. The Pkd-tree supports parallel tree construction, batch update (insertion and deletion), and various queries including k -nearest neighbor search, range query, and range count. We proved that our algorithms have strong theoretical bounds in work (sequential time complexity), span (parallelism), and cache complexity. Our key techniques include 1) an efficient construction algorithm that optimizes work, span, and cache complexity simultaneously, and 2) reconstruction-based update algorithms that guarantee the tree to be weight-balanced. With the new algorithmic insights and careful engineering effort, we achieved a highly optimized implementation of the Pkd-tree. We tested Pkd-tree with various synthetic and real-world datasets, including both uniform and highly skewed data. We compare the Pkd-tree with state-of-the-art parallel kd-tree implementations. In all tests, with better or competitive query performance, Pkd-tree is much faster in construction and updates consistently than all baselines. We released our code.

17 June 2023
Verified
Conference Paper
Open access
YGYan Gu
Yan Gu
ZMZiyang Men
Ziyang Men
ZSZheqi Shen
Zheqi Shen
YSYihan Sun
Yihan Sun
ZWZijin Wan
Zijin Wan
This paper studies parallel algorithms for the longest increasing subsequence (LIS) problem. Let n be the input size and k be the LIS length of the input. Sequentially, LIS is a simple problem that can be solved using dynamic programming (DP) in O(n log n) work. However, parallelizing LIS is a long-standing challenge. We are unaware of any parallel LIS algorithm that has optimal O(n log n) work and non-trivial parallelism (i.e., Õ(k) or o(n) span). This paper proposes a parallel LIS algorithm that costs O(n log k) work, Õ(k) span, and O(n) space, and is much simpler than the previous parallel LIS algorithms. We also generalize the algorithm to a weighted version of LIS, which maximizes the weighted sum for all objects in an increasing subsequence. To achieve a better work bound for the weighted LIS algorithm, we designed parallel algorithms for the van Emde Boas (vEB tree, which has the same structure as the sequential vEB tree, and supports work-efficient parallel batch insertion, deletion, and range queries. We also implemented our parallel LIS algorithms. Our implementation is light-weighted, efficient, and scalable. On input size 109, our LIS algorithm outperforms a highly-optimized sequential algorithm (with O(n log k)cost) on inputs with k ≤ 3 x 105. Our algorithm is also much faster than the best existing parallel implementation by Shen et al. (2022) on all input instances.

24 January 2023 in Computers & Operations Research
Verified
Journal Article
Closed access
MMMengfan Ma
Mengfan Ma
ZMZiyang Men
Ziyang Men
ARAndré Rossi
André Rossi
YZYi Zhou
Yi Zhou
MXMingyu Xiao
Mingyu Xiao

28 January 2026
Verified
Conference Paper
Open access
ZMZiyang Men
Ziyang Men
BHBo Huang
Bo Huang
YGYan Gu
Yan Gu
YSYihan Sun
Yihan Sun

28 January 2026
Verified
Conference Paper
Open access
YZYiwei Zhao
Yiwei Zhao
HKHongbo Kang
Hongbo Kang
ZMZiyang Men
Ziyang Men
YGYan Gu
Yan Gu
GBGuy E. Blelloch
Guy E. Blelloch
PGPhillip B. Gibbons
Phillip B. Gibbons