Improved Sketching of Hamming Distance with Error Correcting

DOI10.1007/978-3-540-73437-6_19zbMath1138.68421OpenAlexW1483799883MaRDI QIDQ3506920

Ely Porat, Ohad Lipsky

Publication date: 17 June 2008

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73437-6_19

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items

On pattern matching with \(k\) mismatches and few don't cares ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance ⋮ On string matching with mismatches ⋮ Towards Optimal Approximate Streaming Pattern Matching by Matching Multiple Patterns in Multiple Streams ⋮ Fingerprints for highly similar streams ⋮ Streaming pattern matching with \(d\) wildcards ⋮ Matching with don't-cares and a small number of mismatches ⋮ Periodicity in data streams with wildcards ⋮ Optimal Las Vegas reduction from one-way set reconciliation to error correction ⋮ Streaming \(k\)-mismatch with error correcting and applications ⋮ Unnamed Item ⋮ Efficient sampling of non-strict turnstile data streams