Zobrazeno 1 - 10
of 70
pro vyhledávání: '"Benjamin Sach"'
Publikováno v:
Theory of Computing. 15:1-31
We give tight cell-probe bounds for the time to compute convolution, multiplication and Hamming distance in a stream. The cell probe model is a particularly strong computational model and subsumes, for example, the popular word RAM model. • We firs
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::cf21257c5f03921f1f2ebd46b8fc95e3
https://doi.org/10.4086/toc.2019.v015a002
https://doi.org/10.4086/toc.2019.v015a002
Autor:
Cédric Mesnage, Matt McVicar, Jefrey Lijffijt, Tijl De Bie, Eirini Spyropoulou, Benjamin Sach
Publikováno v:
McVicar, M, Sach, B, Mesnage, C, Lijffijt, J, Spyropoulou, E & De Bie, T 2016, ' SuMoTED : An intuitive edit distance between rooted unordered uniquely-labelled trees ', Pattern Recognition Letters, vol. 79, pp. 52-59 . https://doi.org/10.1016/j.patrec.2016.04.012
PATTERN RECOGNITION LETTERS
PATTERN RECOGNITION LETTERS
Defining and computing distances between tree structures is a classical area of study in theoretical computer science, with practical applications in the areas of computational biology, information retrieval, text analysis, and many others. In this p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bf6b7b21d629f9bd234495b0bcf20b88
https://doi.org/10.1016/j.patrec.2016.04.012
https://doi.org/10.1016/j.patrec.2016.04.012
Publikováno v:
Theoretical Computer Science. 483:68-74
We present space lower bounds for online pattern matching under a number of different distance measures. Given a pattern of length m and a text that arrives one character at a time, the online pattern matching problem is to report the distance betwee
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::93bf8d18c615285425eab3798517cfd5
https://doi.org/10.1016/j.tcs.2012.06.012
https://doi.org/10.1016/j.tcs.2012.06.012
Autor:
Raphaël Clifford, Benjamin Sach
Publikováno v:
Information Processing Letters. 110:1012-1015
We consider the combination of function and permuted matching, each of which has fast solutions in their own right. Given a pattern p of length m and a text t of length n, a function match at position i of the text is a mapping f from @S"p to @S"t wi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::99eeb626c0590dbddef1eda800f538a2
https://doi.org/10.1016/j.ipl.2010.08.017
https://doi.org/10.1016/j.ipl.2010.08.017
Autor:
Johannes Fischer, Benjamin Sach, Inge Li Gørtz, Tsvi Kopelowitz, Philip Bille, Hjalte Wedel Vildhøj
Publikováno v:
Bille, P, Fischer, J, Gørtz, I L, Kopelowitz, T, Sach, B & Vildhøj, H W 2016, ' Sparse Text Indexing in Small Space ', A C M Transactions on Algorithms, vol. 12, no. 3, 39, pp. 1-19 . https://doi.org/10.1145/2836166
In this work, we present efficient algorithms for constructing sparse suffix trees, sparse suffix arrays, and sparse position heaps for b arbitrary positions of a text T of length n while using only O ( b ) words of space during the construction. Att
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8848063a5106225c8dbe42490e62b3ca
https://orbit.dtu.dk/en/publications/820ab6bf-15a4-4dc7-984d-757deb3d37dd
https://orbit.dtu.dk/en/publications/820ab6bf-15a4-4dc7-984d-757deb3d37dd
Publikováno v:
Proc. of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), September 1-4, 2015, London, UK
Proc. of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), September 1-4, 2015, London, UK, Sep 2015, London, United Kingdom. pp.12, ⟨10.1007/978-3-319-23826-5_24⟩
Gawrychowski, P, Kucherov, G, Sach, B G & Starikovskaya, T 2015, Computing the Longest Unbordered Substring . in String Processing and Information Retrieval : 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings . Lecture Notes in Computer Science, vol. 9309, Springer International Publishing AG, pp. 246-257, International Symposium on String Processing and Information Retrieval, United Kingdom, 1/09/15 . https://doi.org/10.1007/978-3-319-23826-5_24
String Processing and Information Retrieval ISBN: 9783319238258
SPIRE
Proc. of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), September 1-4, 2015, London, UK, Sep 2015, London, United Kingdom. pp.12, ⟨10.1007/978-3-319-23826-5_24⟩
Gawrychowski, P, Kucherov, G, Sach, B G & Starikovskaya, T 2015, Computing the Longest Unbordered Substring . in String Processing and Information Retrieval : 22nd International Symposium, SPIRE 2015, London, UK, September 1-4, 2015, Proceedings . Lecture Notes in Computer Science, vol. 9309, Springer International Publishing AG, pp. 246-257, International Symposium on String Processing and Information Retrieval, United Kingdom, 1/09/15 . https://doi.org/10.1007/978-3-319-23826-5_24
String Processing and Information Retrieval ISBN: 9783319238258
SPIRE
A substring of a string is unbordered if its only border is the empty string. The study of unbordered substrings goes back to the paper of Ehrenfeucht and Silberger [Discr. Math 26 1979]. The main focus of their and subsequent papers was to elucidate
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e0a3109de3fa80eb68245fea8071126f
https://hal.archives-ouvertes.fr/hal-01250721
https://hal.archives-ouvertes.fr/hal-01250721
Publikováno v:
Clifford, R, Fontaine, A, Porat, E, Sach, B & Starikovskaia, T 2016, The k-mismatch problem revisited . in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms . vol. January 2016, Society for Industrial and Applied Mathematics, pp. 2039-2052 . https://doi.org/10.1137/1.9781611974331.ch142
We revisit the complexity of one of the most basic problems in pattern matching. In the k-mismatch problem we must compute the Hamming distance between a pattern of length m and every m-length substring of a text of length n, as long as that Hamming
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fe81c5274c83dd0b3e81f2855d1ba5f7
Publikováno v:
Algorithms-ESA 2015 ISBN: 9783662483497
ESA
ESA
We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our dictionary occurs in the stream. We prese
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ba2def788d8c0c2f3e0dbab9d43b8891
https://doi.org/10.1007/978-3-662-48350-3_31
https://doi.org/10.1007/978-3-662-48350-3_31
Publikováno v:
Bille, P, Gørtz, I L, Sach, B & Vildhøj, H W 2014, ' Time–space trade-offs for longest common extensions ', Journal of Discrete Algorithms, vol. 25, pp. 42-50 . https://doi.org/10.1016/j.jda.2013.06.003
We revisit the longest common extension (LCE) problem, that is, preprocess a string T into a compact data structure that supports fast LCE queries. An LCE query takes a pair (i,j) of indices in T and returns the length of the longest common prefix of
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::af537d05ba2285d0ef1705fca2f16627
https://orbit.dtu.dk/en/publications/376dbefe-b2c1-4ece-973b-cc33f266d293
https://orbit.dtu.dk/en/publications/376dbefe-b2c1-4ece-973b-cc33f266d293
Publikováno v:
Scopus-Elsevier
We give cell-probe bounds for the computation of edit distance, Hamming distance, convolution and longest common subsequence in a stream. In this model, a fixed string of $n$ symbols is given and one $\delta$-bit symbol arrives at a time in a stream.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2bd47cc467247a651ad63f60e526f3ea