Finding longest increasing and common subsequences in streaming data

DOI10.1007/S10878-006-7125-XMaRDI QIDQ2498982zbMATH OpenOpenAlexFDO

Authors David Liben-Nowell, Erik Vee, An Zhu

Publication date 14 August 2006

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-006-7125-x

zbMATH Keywords

AlgorithmsData-streaming modelLCSLISLower bounds

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Computing and Combinatorics
• 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

Cites work

• A fast algorithm for computing longest common subsequences
• Algorithms for the Longest Common Subsequence Problem
• An Approximate L¹ -Difference Algorithm for Massive Data Streams
• An approximate L^p difference algorithm for massive data streams
• An information statistics approach to data stream and communication complexity
• Approximate counting of inversions in a data stream
• Data-streams and histograms
• Enumerating longest increasing subsequences and patience sorting
• Fast, small-space algorithms for approximate histogram maintenance
• Finding frequent items in data streams
• scientific article; zbMATH DE number 1947388 (Why is no real title available?)
• scientific article; zbMATH DE number 1947405 (Why is no real title available?)
• scientific article; zbMATH DE number 1516705 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• Introduction to algorithms.
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Longest Increasing and Decreasing Subsequences
• On computing the length of longest increasing subsequences
• On the distributional complexity of disjointness
• Preserving order in a forest in less than logarithmic time and linear space
• Space lower bounds for distance approximation in the data stream model
• The longest common subsequence problem revisited
• The Probabilistic Communication Complexity of Set Intersection
• The space complexity of approximating the frequency moments

Cited in

(12)

• Efficient algorithms for the inverse sorting problem with bound constraints under the \(l_{\infty }\)-norm and the Hamming distance
• Fast computation of a longest increasing subsequence and application
• Space-efficient algorithms for longest increasing subsequence
• Longest increasing subsequences in windows based on canonical antichain partition
• The communication and streaming complexity of computing the longest common and increasing subsequences
• Space-efficient algorithms for longest increasing subsequence
• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Sketching, streaming, and fine-grained complexity of (weighted) LCS
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• Computing and Combinatorics
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• A central limit theorem for repeating patterns

Describes a project that uses

Uses Software

• MUMMER

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 Q2498982)