Name
Abstract | ||
|---|---|---|
We address the problems of pattern matching and approximate pattern matching in the sketching model. We show that it is impossible to compress the text into a small sketch and use only the sketch to decide whether a given pattern occurs in the text. We also prove a sketch size lower bound for approximate pattern matching, and show it is tight up to a logarithmic factor. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-27821-4_24 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
pattern matching,lower bound | Approximation algorithm,Computer science,Upper and lower bounds,Algorithm,Theoretical computer science,Combinatorial optimization,Logarithm,3-dimensional matching,Data compression,Pattern matching,Sketch | Conference |
Volume | ISSN | Citations |
3122 | 0302-9743 | 13 |
PageRank | References | Authors |
1.02 | 26 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ziv Bar-Yossef | 1 | 1776 | 118.00 |
| T. S. Jayram | 2 | 1373 | 75.87 |
| Robert Krauthgamer | 3 | 1417 | 103.80 |
| Ravi Kumar | 4 | 13932 | 1642.48 |