More Web Proxy on the site http://driver.im/

research-article

Open access

Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence

Authors:

Shang-En Huang,

Hsin-Hao SuAuthors Info & Claims

SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

Pages 249 - 259

https://doi.org/10.1145/3558481.3591078

Published: 17 June 2023 Publication History

Abstract

The paper presents parallel algorithms for multiplying implicit simple unit-Monge matrices (Krusche and Tiskin, PPAM 2009) of size n x n in the EREW PRAM model. We show implicit simple unit-Monge matrices multiplication of size n x n can be achieved by a deterministic EREW PRAM algorithm with O(n log n log log n) total work and O(log3 n) span. This implies that there is a deterministic EREW PRAM algorithm solving the longest increasing subsequence (LIS) problem in O(n log2 n log log n) work and O(log 4 n) span. Furthermore, with randomization and bitwise operations, implicitly multiplying two simple unit-Monge matrices can be improved to O(n log n) work and O(log3n) span, which leads to a randomized EREW PRAM algorithm obtaining LIS in O(nlog2n) work and O(log4n) span with high probability. In the regime where the LIS has length k = Ψ(log3n), our results improve the span from Õ(n2/3) (Krusche and Tiskin, SPAA 2010) and O(klog n) (Gu, Men, Shen, Sun, and Wan, SPAA 2023) to O(log4 n) while the total work remains near optimal Õ (n).

Supplemental Material

MP4 File

This video discusses a nearly optimal algorithm for the longest increasing subsequence(LIS) problem. We'll start by talking about the implicit sub-unit Monge matrix multiplication (ISMMM) problem and how it connects to LIS. Then, we'll explain the main idea behind our algorithm for ISMMM in simple terms. Finally, we'll touch upon some future work for LIS problems.

Download
226.17 MB

References

[1]

Alfred V. Aho, Daniel S. Hirschberg, and Jeffrey D. Ullman. 1976. Bounds on the Complexity of the Longest Common Subsequence Problem. J. ACM, Vol. 23, 1 (1976), 1--12. https://doi.org/10.1145/321921.321922

Digital Library

[2]

Mikló s Ajtai, Já nos Komlós, and Endre Szemerédi. 1983. An O(n log n) Sorting Network. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, and Joel I. Seiferas (Eds.). ACM, 1--9. https://doi.org/10.1145/800061.808726

Digital Library

[3]

Arne Andersson, Torben Hagerup, Stefan Nilsson, and Rajeev Raman. 1995. Sorting in linear time?. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, Frank Thomson Leighton and Allan Borodin (Eds.). ACM, 427--436. https://doi.org/10.1145/225058.225173

Digital Library

[4]

Jinho Baik, Percy Deift, and Kurt Johansson. 1999. On the distribution of the length of the longest increasing subsequence of random permutations. Journal of the American Mathematical Society, Vol. 12, 4 (1999), 1119--1178.

[5]

Laura Baxter, Aleksey Jironkin, Richard Hickman, Jonathan Moore, Christopher Barrington, Peter Krusche, Nigel Dyer, Vicky Buchanan-Wollaston, Alexander Tiskin, Jim Beynon, Katherine Denby, and Sascha Ott. 2012. Conserved Noncoding Sequences Highlight Shared Components of Regulatory Networks in Dicotyledonous Plants. The Plant cell, Vol. 24 (10 2012). https://doi.org/10.1105/tpc.112.103010

[6]

Timothy M Chan. 2007. More algorithms for all-pairs shortest paths in weighted graphs. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. 590--598.

Digital Library

[7]

Maxime Crochemore, Gad M. Landau, and Michal Ziv-Ukelson. 2003. A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices. SIAM J. Comput., Vol. 32, 6 (2003), 1654--1673. https://doi.org/10.1137/S0097539702402007

Digital Library

[8]

Maxime Crochemore and Ely Porat. 2010. Fast computation of a longest increasing subsequence and application. Inf. Comput., Vol. 208, 9 (2010), 1054--1059. https://doi.org/10.1016/j.ic.2010.04.003

Digital Library

[9]

A.L. Delcher, S. Kasif, R.D. Fleischmann, J. Peterson, O. White, and S.L. Salzberg. 1999. Alignment of whole genomes. Nucleic Acids Res., Vol. 27, 11 (1999), 2369--2376. https://doi.org/10.1093/nar/27.11.2369

[10]

Arthur L Delcher, Steven L Salzberg, and Adam M Phillippy. 2003. Using MUMmer to identify similar regions in large sequence sets. Current protocols in bioinformatics 1 (2003), 10--3.

[11]

Michael L. Fredman. 1975. On computing the length of longest increasing subsequences. Discret. Math., Vol. 11, 1 (1975), 29--35. https://doi.org/10.1016/0012-365X(75)90103-X

Digital Library

[12]

James C Fu and Yu-Fei Hsieh. 2015. On the distribution of the length of the longest increasing subsequence in a random permutation. Methodology and Computing in Applied Probability, Vol. 17, 2 (2015), 489--496.

Digital Library

[13]

Z. Galil and K. Park. 1994. Parallel Algorithms for Dynamic Programming Recurrences with More Than O(1) Dependency. J. Parallel and Distrib. Comput., Vol. 21, 2 (1994), 213--222. https://doi.org/10.1006/jpdc.1994.1053

Digital Library

[14]

Thierry Garcia, Jean Fré déric Myoupo, and David Semé. 2001. A work-optimal CGM algorithm for the LIS problem. In Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA 2001, Heraklion, Crete Island, Greece, July 4-6, 2001, Arnold L. Rosenberg (Ed.). ACM, 330--331. https://doi.org/10.1145/378580.378756

Digital Library

[15]

Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan. 2023. Parallel Longest Increasing Subsequence and van Emde Boas Trees. In Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '23), June 17-19, 2023, Orlando, FL, USA. https://doi.org/10.48550/arXiv.2208.09809

Digital Library

[16]

Yijie Han. 2004. Deterministic sorting in O(n log log n) time and linear space. J. Algorithms, Vol. 50, 1 (2004), 96--105. https://doi.org/10.1016/j.jalgor.2003.09.001

Digital Library

[17]

Yijie Han and Tadao Takaoka. 2016. An O(n 3 log log n / log 2 n) time algorithm for all pairs shortest paths. J. Discrete Algorithms, Vol. 38--41 (2016), 9--19. https://doi.org/10.1016/j.jda.2016.09.001

Digital Library

[18]

Sungjin Im, Benjamin Moseley, and Xiaorui Sun. 2017. Efficient massively parallel methods for dynamic programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.). ACM, 798--811. https://doi.org/10.1145/3055399.3055460

Digital Library

[19]

Joseph F. Já Já, Christian Worm Mortensen, and Qingmin Shi. 2004. Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting. In Algorithms and Computation, 15th International Symposium, ISAAC 2004, Hong Kong, China, December 20-22, 2004, Proceedings (Lecture Notes in Computer Science, Vol. 3341), Rudolf Fleischer and Gerhard Trippen (Eds.). Springer, 558--568. https://doi.org/10.1007/978-3-540-30551-4_49

Digital Library

[20]

Peter Krusche and Alexander Tiskin. 2009. Parallel Longest Increasing Subsequences in Scalable Time and Memory. In Parallel Processing and Applied Mathematics, 8th International Conference, PPAM 2009, Wroclaw, Poland, September 13-16, 2009. Revised Selected Papers, Part I (Lecture Notes in Computer Science, Vol. 6067), Roman Wyrzykowski, Jack J. Dongarra, Konrad Karczewski, and Jerzy Wasniewski (Eds.). Springer, 176--185. https://doi.org/10.1007/978--3--642--14390--8_19

[21]

Peter Krusche and Alexander Tiskin. 2010. New algorithms for efficient parallel string comparison. In SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, Thira, Santorini, Greece, June 13-15, 2010, Friedhelm Meyer auf der Heide and Cynthia A. Phillips (Eds.). ACM, 209--216. https://doi.org/10.1145/1810479.1810521

Digital Library

[22]

Mi Lu and Hua Lin. 1994. Parallel Algorithms for the Longest Common Subsequence Problem. IEEE Trans. Parallel Distributed Syst., Vol. 5, 8 (1994), 835--848. https://doi.org/10.1109/71.298210

Digital Library

[23]

Amgad Madkour, Walid G. Aref, Faizan Ur Rehman, Mohamed Abdur Rahman, and Saleh M. Basalamah. 2017. A Survey of Shortest-Path Algorithms. CoRR, Vol. abs/1705.02044 (2017). [arXiv]1705.02044 http://arxiv.org/abs/1705.02044

[24]

Takaaki Nakashima and Akihiro Fujiwara. 2006. A Cost Optimal Parallel Algorithm for Patience Sorting. Parallel Process. Lett., Vol. 16, 1 (2006), 39--52. https://doi.org/10.1142/S0129626406002459

[25]

Ryan O'Donnell and John Wright. 2017. Guest Column: A Primer on the Statistics of Longest Increasing Subsequences and Quantum States (Shortened Version). SIGACT News, Vol. 48, 3 (2017), 37--59. https://doi.org/10.1145/3138860.3138869

Digital Library

[26]

Emma Picot, Peter Krusche, Alexander Tiskin, Isabelle Carré, and Sascha Ott. 2010. Evolutionary analysis of regulatory sequences (EARS) in plants. The Plant Journal, Vol. 64, 1 (2010), 165--176.

[27]

Prakash Ramanan. 1997. Tight (Ω)(n lg n) lower bound for finding a longest increasing subsequence. Int. J. Comput. Math., Vol. 65, 3--4 (1997), 161--164. https://doi.org/10.1080/00207169708804607

[28]

Yoshifumi Sakai and Shunsuke Inenaga. 2022. A Faster Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length. Algorithmica, Vol. 84, 9 (2022), 2581--2596. https://doi.org/10.1007/s00453-022-00968--2

Digital Library

[29]

David Sankoff. 1983. Time warps, string edits, and macromolecules. The Theory and Practice of Sequence Comparison, Reading (1983).

[30]

David Semé. 2006. A CGM Algorithm Solving the Longest Increasing Subsequence Problem. In Computational Science and Its Applications - ICCSA 2006, International Conference, Glasgow, UK, May 8-11, 2006, Proceedings, Part V (Lecture Notes in Computer Science, Vol. 3984), Marina L. Gavrilova, Osvaldo Gervasi, Vipin Kumar, Chih Jeng Kenneth Tan, David Taniar, Antonio Laganà, Youngsong Mun, and Hyunseung Choo (Eds.). Springer, 10--21. https://doi.org/10.1007/11751649_2

Digital Library

[31]

Zheqi Shen, Zijin Wan, Yan Gu, and Yihan Sun. 2022. Many Sequential Iterative Algorithms Can Be Parallel and (Nearly) Work-efficient. In SPAA '22: 34th ACM Symposium on Parallelism in Algorithms and Architectures, Philadelphia, PA, USA, July 11 - 14, 2022, Kunal Agrawal and I-Ting Angelina Lee (Eds.). ACM, 273--286. https://doi.org/10.1145/3490148.3538574

Digital Library

[32]

Yihan Sun and Guy E. Blelloch. 2019. Parallel Range, Segment and Rectangle Queries with Augmented Maps. In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019, Stephen G. Kobourov and Henning Meyerhenke (Eds.). SIAM, 159--173. https://doi.org/10.1137/1.9781611975499.13

[33]

Alexander Tiskin. 2007. Semi-local string comparison: algorithmic techniques and applications. (2007). https://doi.org/10.48550/ARXIV.0707.3619

[34]

Alexander Tiskin. 2008. Semi-local longest common subsequences in subquadratic time. J. Discrete Algorithms, Vol. 6, 4 (2008), 570--581. https://doi.org/10.1016/j.jda.2008.07.001

Digital Library

[35]

Alexander Tiskin. 2010. Fast Distance Multiplication of Unit-Monge Matrices. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, Moses Charikar (Ed.). SIAM, 1287--1296. https://doi.org/10.1137/1.9781611973075.103

[36]

Alexander Tiskin. 2015. Fast Distance Multiplication of Unit-Monge Matrices. Algorithmica, Vol. 71, 4 (2015), 859--888. https://doi.org/10.1007/s00453-013-9830-z

Digital Library

[37]

Peter van Emde Boas. 1977. Preserving Order in a Forest in Less Than Logarithmic Time and Linear Space. Inf. Process. Lett., Vol. 6, 3 (1977), 80--82. https://doi.org/10.1016/0020-0190(77)90031-X

[38]

Peter van Emde Boas, R. Kaas, and E. Zijlstra. 1977. Design and Implementation of an Efficient Priority Queue. Math. Syst. Theory, Vol. 10 (1977), 99--127. https://doi.org/10.1007/BF01683268 io

Cited By

Koo JAgrawal KPetrank E(2024)An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LISProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659974(145-154)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659974
Ding XGu YSun YAgrawal KPetrank E(2024)Parallel and (Nearly) Work-Efficient Dynamic ProgrammingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659958(219-232)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659958

Index Terms

Nearly Optimal Parallel Algorithms for Longest Increasing Subsequence
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Parallel Longest Increasing Subsequence and van Emde Boas Trees
SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

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 ...
Parallel Algorithms for the Longest Common Subsequence Problem

A subsequence of a given string is any string obtained by deleting none or some symbolsfrom the given string. A longest common subsequence (LCS) of two strings is a commonsubsequence of both that is as long as any other common subsequences. The problem ...
Improved dynamic algorithms for longest increasing subsequence
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

We study dynamic algorithms for the longest increasing subsequence (LIS) problem. A dynamic LIS algorithm maintains a sequence subject to operations of the following form arriving one by one: insert an element, delete an element, or substitute an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures

June 2023

504 pages

ISBN:9781450395458

DOI:10.1145/3558481

General Chair:
Kunal Agrawal
Washington University in St. Louis, USA
,
Program Chair:
Julian Shun
MIT, USA

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGARCH: ACM Special Interest Group on Computer Architecture
EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2023

Check for updates

Badges

Honorable Mention

Author Tags

Qualifiers

Research-article

Data Availability

This video discusses a nearly optimal algorithm for the longest increasing subsequence(LIS) problem. We'll start by talking about the implicit sub-unit Monge matrix multiplication (ISMMM) problem and how it connects to LIS. Then, we'll explain the main idea behind our algorithm for ISMMM in simple terms. Finally, we'll touch upon some future work for LIS problems. https://dl.acm.org/doi/10.1145/3558481.3591078#SPAA23-spaafp051.mp4

Funding Sources

NSF

Conference

SPAA '23

Sponsor:

SPAA '23: 35th ACM Symposium on Parallelism in Algorithms and Architectures

June 17 - 19, 2023

FL, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
389
Total Downloads

Downloads (Last 12 months)230
Downloads (Last 6 weeks)21

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Koo JAgrawal KPetrank E(2024)An Optimal MPC Algorithm for Subunit-Monge Matrix Multiplication, with Applications to LISProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659974(145-154)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659974
Ding XGu YSun YAgrawal KPetrank E(2024)Parallel and (Nearly) Work-Efficient Dynamic ProgrammingProceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659958(219-232)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659958

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents