Finding longest increasing and common subsequences in streaming data

DOI10.1007/11533719_28MaRDI QIDQ5716944zbMATH OpenOpenAlexFDO

Authors David Liben-Nowell, Erik Vee, An Zhu

Publication date 11 January 2006

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11533719

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Analysis of algorithms (68W40)

Recommendations

• Finding longest increasing and common subsequences in streaming data
• The communication and streaming complexity of computing the longest common and increasing subsequences
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• Faster algorithms for computing longest common increasing subsequences
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance

Cited in

(11)

• On the monotonicity of a data stream
• Longest increasing subsequences in sliding windows
• Computing the longest common almost-increasing subsequence
• Finding longest increasing and common subsequences in streaming data
• Estimating the sortedness of a data stream
• The communication and streaming complexity of computing the longest common and increasing subsequences
• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Algorithms and Computation
• Streaming and small space approximation algorithms for edit distance and longest common subsequence

This page was built for publication: Finding longest increasing and common subsequences in streaming data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5716944)