Improved Sketching Of Hamming Distance
Google Tech Talks
June 27, 2007
ABSTRACT
We address the problem of sketching the hamming distance of data streams. We develop Fixable Sketches which compare data streams or files and restore the differences between them. Our contribution: For two streams with Humming distance bounded by k we show a sketch of size O(klogn) with O(logn) processing time per new element in the stream and how to restore all locations where the two streams differ in time linear in the sketch size. Probability of error is less then 1/n.
Speaker: Ely Porat
At age 16 Ely Porat multithreaded being a junior in high school, a freshman in the computer science department of Bar Ilan university and hacking computers....
Watch video Improved Sketching Of Hamming Distance online without registration, duration hours minute second in high quality. This video was added by user Google TechTalks 08 October 2007, don't forget to share it with your friends and acquaintances, it has been viewed on our site 2,780 once and liked it 5 people.