Improved Sketching of Hamming Distance with Error Correcting
作者： Ely Porat , Ohad Lipsky
DOI: 10.1007/978-3-540-73437-6_19
关键词:
摘要: We address the problemof sketching hamming distance of data streams. develop Fixable Sketches which compare streams or files and restore differences between them. Our contribution: For two with bounded by k we show a sketch size O(k log n) O(log processing time per new element in stream how to all locations where differ linear size. Probability error is less than 1/n.
springer.com
springerlink.com
biu.ac.il 参考文章(16)
Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin J. Strauss, Rebecca N. Wright, Secure Multiparty Computation of Approximations international colloquium on automata languages and programming. pp. 927- 938 ,(2001) , 10.1007/3-540-48224-5_75
Matthew Hennessy, Robin Milner, On Observing Nondeterminism and Concurrency international colloquium on automata, languages and programming. pp. 299- 309 ,(1980) , 10.1007/3-540-10003-2_79
S. Muthukrishnan, Data Streams: Algorithms and Applications ,(2005)
Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation Journal of the ACM. ,vol. 53, pp. 307- 323 ,(2006) , 10.1145/1147954.1147955
Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance symposium on the theory of computing. pp. 389- 398 ,(2002) , 10.1145/509907.509966
Eyal Kushilevitz, Rafail Ostrovsky, Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces SIAM Journal on Computing. ,vol. 30, pp. 457- 474 ,(2000) , 10.1137/S0097539798347177
G. Cormode, M. Datar, P. Indyk, S. Muthukrishnan, Comparing data streams using Hamming norms (how to zero in) IEEE Transactions on Knowledge and Data Engineering. ,vol. 15, pp. 529- 540 ,(2003) , 10.1109/TKDE.2003.1198388
D. Starobinski, A. Trachtenberg, S. Agarwal, Efficient PDA synchronization IEEE Transactions on Mobile Computing. ,vol. 2, pp. 40- 51 ,(2003) , 10.1109/TMC.2003.1195150
Sudipto Guha, Nick Koudas, Kyuseok Shim, Data-streams and histograms Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 471- 475 ,(2001) , 10.1145/380752.380841
Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami, A sublinear algorithm for weakly approximating edit distance symposium on the theory of computing. pp. 316- 324 ,(2003) , 10.1145/780542.780590