EUVIMEDEUVIMED entdecken
Crossref

A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction

Julian Shun, Guy E. Blelloch

ACM Transactions on Parallel Computing · 2014

DOI: 10.1145/2661653 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Parallel Computing, 2014. Verfasst von Julian Shun und 1 weiteren Autor:innen. Die Arbeit wurde bisher 23-mal zitiert (Crossref) und nennt 51 Literaturangaben. Gefördert von: Microsoft, International Business Machines Corporation, Intel Corporation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We present a simple linear work and space, and polylogarithmic time parallel algorithm for generating multiway Cartesian trees. We show that bottom-up traversals of the multiway Cartesian tree on the interleaved suffix array and longest common prefix array of a string can be used to answer certain string queries. By adding downward pointers in the tree (e.g. using a hash table), we can also generate suffix trees from suffix arrays on arbitrary alphabets in the same bounds. In conjunction with parallel suffix array algorithms, such as the skew algorithm, this gives a rather simple linear work parallel, O ( n ε ) time (0< ε

Förderung

  • Microsoft
  • International Business Machines Corporation
  • Intel Corporation
  • Division of Computing and Communication Foundations
  • Facebook

Zitieren

APA

Shun, J., & Blelloch, G. E. (2014). A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction. ACM Transactions on Parallel Computing. https://doi.org/10.1145/2661653

Vancouver

Shun J, Blelloch GE. A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction. ACM Transactions on Parallel Computing. 2014. doi:10.1145/2661653

BibTeX
@article{Shun2014,
  author = {Shun, Julian and Blelloch, Guy E.},
  title = {A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction},
  journal = {ACM Transactions on Parallel Computing},
  year = {2014},
  doi = {10.1145/2661653}
}
Kostenlos starten →