Finding longest increasing and common subsequences in streaming data

DOI10.1007/S10878-006-7125-XzbMATH Open1130.90040OpenAlexW2065937173MaRDI QIDQ2498982FDOQ2498982

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

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

zbMATH Keywords

AlgorithmsLCSLower boundsLISData-streaming model

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

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

Cited In (11)

• A note on randomized streaming space bounds for the longest increasing subsequence problem
• Computing and Combinatorics
• Title not available (Why is that?)
• 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
• The communication and streaming complexity of computing the longest common and increasing subsequences
• Fast computation of a longest increasing subsequence and application

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)