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

AlgorithmsLCSLower boundsLISData-streaming model

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

• 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?)
• 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
• 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 Probabilistic Communication Complexity of Set Intersection
• The longest common subsequence problem revisited
• The space complexity of approximating the frequency moments

Cited in

(11)

• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Computing and Combinatorics
• scientific article; zbMATH DE number 7561345 (Why is no real title available?)
• Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
• Space-efficient algorithms for longest increasing subsequence
• Space-efficient algorithms for longest increasing subsequence
• Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence
• Longest increasing subsequences in windows based on canonical antichain partition
• 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
• The communication and streaming complexity of computing the longest common and increasing subsequences

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)