TY - GEN
T1 - Parikh matching in the streaming model
AU - Lee, Lap Kei
AU - Lewenstein, Moshe
AU - Zhang, Qin
PY - 2012
Y1 - 2012
N2 - Let S be a string over an alphabet Σ∈=∈{σ 1, σ 2, A Parikh-mapping maps a substring S′ of S to a |Σ|-length vector that contains, in location i of the vector, the count of σ i in S′. Parikh matching refers to the problem of finding all substrings of a text T which match to a given input |Σ|-length count vector. In the streaming model one seeks space-efficient algorithms for problems in which there is one pass over the data. We consider Parikh matching in the streaming model. To make this viable we search for substrings whose Parikh-mappings approximately match the input vector. In this paper we present upper and lower bounds on the problem of approximate Parikh matching in the streaming model.
AB - Let S be a string over an alphabet Σ∈=∈{σ 1, σ 2, A Parikh-mapping maps a substring S′ of S to a |Σ|-length vector that contains, in location i of the vector, the count of σ i in S′. Parikh matching refers to the problem of finding all substrings of a text T which match to a given input |Σ|-length count vector. In the streaming model one seeks space-efficient algorithms for problems in which there is one pass over the data. We consider Parikh matching in the streaming model. To make this viable we search for substrings whose Parikh-mappings approximately match the input vector. In this paper we present upper and lower bounds on the problem of approximate Parikh matching in the streaming model.
UR - https://www.scopus.com/pages/publications/84867550298
U2 - 10.1007/978-3-642-34109-0_35
DO - 10.1007/978-3-642-34109-0_35
M3 - Conference contribution
AN - SCOPUS:84867550298
SN - 9783642341083
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 336
EP - 341
BT - String Processing and Information Retrieval - 19th International Symposium, SPIRE 2012, Proceedings
T2 - 19th International Symposium on String Processing and Information Retrieval, SPIRE 2012
Y2 - 21 October 2012 through 25 October 2012
ER -