Improved Sketching of Hamming Distance with Error Correcting

DOI10.1007/978-3-540-73437-6_19MaRDI QIDQ3506920zbMATH OpenOpenAlexFDO

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

Recommendations

• Approximate Hamming distance in a stream
• Homomorphic fingerprints under misalignments
• LATIN 2004: Theoretical Informatics
• An improved data stream summary: the count-min sketch and its applications
• Tight Cell-Probe Bounds for Online Hamming Distance Computation

Cited in

(15)

• On string matching with mismatches
• Streaming pattern matching with \(d\) wildcards
• Streaming \(k\)-mismatch with error correcting and applications
• Efficient sampling of non-strict turnstile data streams
• On pattern matching with \(k\) mismatches and few don't cares
• Fingerprints for highly similar streams
• Streaming periodicity with mismatches
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Streaming for aibohphobes: longest palindrome with mismatches
• A simple algorithm for approximating the text-to-pattern Hamming distance
• Count-Min Sketches for Estimating Password Frequency within Hamming Distance Two
• Optimal Las Vegas reduction from one-way set reconciliation to error correction
• scientific article; zbMATH DE number 7758348 (Why is no real title available?)
• Locally consistent decomposition of strings with applications to edit distance sketching
• Matching with don't-cares and a small number of mismatches

This page was built for publication: Improved Sketching of Hamming Distance with Error Correcting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3506920)