Ordered Sets and Maps

[Back to full publication list]

Algorithms and data structures to support ordered sets and maps with a wide range of functions on the interface, such as construction, point and batch insertion/deletion, set-union, set-intersection, set-difference, filter, range queries, etc.

2022:
[5] PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections
Laxman Dhulipala, Guy E. Blelloch, Yan Gu*, and Yihan Sun*
PLDI
ACM Conference on Programming Language Design and Implementation (PLDI), 2022    [BibTeX]

@inproceedings{ Dhulipala2022PaC-trees:,
title = { PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections },
author = { Dhulipala, Laxman and Blelloch, Guy E. and Gu, Yan and Sun, Yihan},
booktitle = {ACM Conference on Programming Language Design and Implementation (PLDI)},
year = { 2022 }
}

  DOI:
10.1145/3519939.3523733
  Software Library:
CPAM: Compressed Parallel Augmented Maps  [Github]
Paper   ArXiV  Code  Slides
[4] Joinable Parallel Balanced Binary Trees
Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun*
TOPC
ACM Transactions on Parallel Computing (TOPC), 2022    [BibTeX]

@inproceedings{ Blelloch2022Joinable,
title = { Joinable Parallel Balanced Binary Trees },
author = { Blelloch, Guy E. and Ferizovic, Daniel and Sun, Yihan},
booktitle = {ACM Transactions on Parallel Computing (TOPC)},
year = { 2022 }
}

  DOI:
10.1145/3512769
  Software Library:
PAM: Parallel Augmented Maps  [Github]
Paper   Code
2021:
[3] Parallel In-Place Algorithms: Theory and Practice
Yan Gu*, , and Julian Shun
APOCS
ACM-SIAM Algorithmic Principles of Computer Systems (APOCS), 2021    [BibTeX]

@inproceedings{ Gu2021Parallel,
title = { Parallel In-Place Algorithms: Theory and Practice },
author = { Gu, Yan and , and Shun, Julian},
booktitle = {ACM-SIAM Algorithmic Principles of Computer Systems (APOCS)},
year = { 2021 }
}

  Software Library:
Parallel In-Place (PIP) Algorithms  [Github]
Paper   Video  ArXiV  Code
2020:
[2] Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model
Guy E. Blelloch, Jeremy T. Fineman, Yan Gu*, and Yihan Sun*
🏆 Best Paper Candidate!
SPAA
ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2020    [BibTeX]

@inproceedings{ Blelloch2020Optimal,
title = { Optimal (Randomized) Parallel Algorithms in the Binary-Forking Model },
author = { Blelloch, Guy E. and Fineman, Jeremy T. and Gu, Yan and Sun, Yihan},
booktitle = {ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)},
year = { 2020 }
}

  DOI:
10.1145/3350755.3400227
Paper   Video  Slides
[1] On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes
Yihan Sun*, Guy E. Blelloch, Wan Shen Lim, and Andrew Pavlo
VLDB
International Conference on Very Large Data Bases (VLDB), 2020    [BibTeX]

@inproceedings{ Sun2020On,
title = { On Supporting Efficient Snapshot Isolation for Hybrid Workloads with Multi-Versioned Indexes },
author = { Sun, Yihan and Blelloch, Guy E. and Lim, Wan Shen and Pavlo, Andrew},
booktitle = {International Conference on Very Large Data Bases (VLDB)},
year = { 2020 }
}

  DOI:
10.14778/3364324.3364334
  Software Library:
Part of the PAM library: Parallel Augmented Maps  [Github]
Paper   Video  Code  Slides