\(L_{1}\) pattern matching lower bound

DOI10.1016/j.ipl.2007.08.011zbMath1184.68210OpenAlexW2055497872MaRDI QIDQ2380062

Ohad Lipsky, Ely Porat

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.08.011

zbMATH Keywords

analysis of algorithmslower boundtime series analysispattern matching

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Searching and sorting (68P10)

Related Items (8)

The Closest Pair Problem under the Hamming Metric ⋮ One-dimensional approximate point set pattern matching with \(L_p\)-norm ⋮ Unnamed Item ⋮ Brief Announcement: Hamming Distance Completeness and Sparse Matrix Multiplication. ⋮ Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance ⋮ Hamming Distance Completeness ⋮ Approximating Approximate Pattern Matching ⋮ Recent advances in text-to-pattern distance algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Entropy and predictability of stock market returns.
• Efficient 2-dimensional approximate matching of half-rectangular figures
• Combinatorial pattern matching. 16th annual symposium, CPM 2005, Jeju Island, Korea, June 19--22, 2005. Proceedings.
• Generalized String Matching
• Faster algorithms for string matching with k mismatches
• Automata, Languages and Programming
• Combinatorial Pattern Matching
• Combinatorial Pattern Matching

This page was built for publication: \(L_{1}\) pattern matching lower bound