Lodz University of Technology

output

19962026

most citedLow-Mass Dark Matter Search with the DarkSide-50 Experiment

443 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions

Showing cs.DSShow all

15 papers · 1 filter

cs.DS2016

Efficient and Compact Representations of Some Non-Canonical Prefix-Free Codes

Antonio Fariña, Travis Gagie, Szymon Grabowski +3

For many kinds of prefix-free codes there are efficient and compact alternatives to the traditional tree-based representation. Since these put the codes into canonical form, howeve…

cs.DS2015★ 1 cited

A Bloom filter based semi-index on $q$ -grams

Szymon Grabowski, Robert Susik, Marcin Raniszewski

We present a simple $q$ -gram based semi-index, which allows to look for a pattern typically only in a small fraction of text blocks. Several space-time tradeoffs are presented. Exp…

cs.DS2015

FM-index for dummies

Szymon Grabowski, Marcin Raniszewski, Sebastian Deorowicz

The FM-index is a celebrated compressed data structure for full-text pattern searching. After the first wave of interest in its theoretical developments, we can observe a surge of…

cs.DS2015★ 23 cited

Indexing arbitrary-length $k$ -mers in sequencing reads

Tomasz Kowalski, Szymon Grabowski, Sebastian Deorowicz

We propose a lightweight data structure for indexing and querying collections of NGS reads data in main memory. The data structure supports the interface proposed in the pioneering…

cs.DS2014★ 2 cited

A note on the longest common substring with $k$ -mismatches problem

Szymon Grabowski

The recently introduced longest common substring with $k$ -mismatches ( $k$ -LCF) problem is to find, given two sequences $S_{1}$ and $S_{2}$ of length $n$ each, a longest substring $A_{1}$ …

cs.DS2014★ 308 cited

KMC 2: Fast and resource-frugal $k$ -mer counting

Sebastian Deorowicz, Marek Kokot, Szymon Grabowski +1

Motivation: Building the histogram of occurrences of every $k$ -symbol long substring of nucleotide data is a standard step in many bioinformatics applications, known under the name…

cs.DS2014

Sampling the suffix array with minimizers

Szymon Grabowski, Marcin Raniszewski

Sampling (evenly) the suffixes from the suffix array is an old idea trading the pattern search time for reduced index space. A few years ago Claude et al. showed an alphabet sampli…

cs.DS2014★ 1 cited

Multiple pattern matching revisited

Robert Susik, Szymon Grabowski, Kimmo Fredriksson

We consider the classical exact multiple string matching problem. Our solution is based on $q$ -grams combined with pattern superimposition, bit-parallelism and alphabet size reduct…

cs.DS2014★ 3 cited

Two simple full-text indexes based on the suffix array

Szymon Grabowski, Marcin Raniszewski

We propose two suffix array inspired full-text indexes. One, called SA-hash, augments the suffix array with a hash table to speed up pattern searches due to significantly narrowed…

cs.DS2013★ 4 cited

New tabulation and sparse dynamic programming based techniques for sequence similarity problems

Szymon Grabowski

Calculating the length of a longest common subsequence (LCS) of two strings $A$ and $B$ of length $n$ and $m$ is a classic research topic, with many worst-case oriented results kno…

cs.DS2013

Efficient algorithms for the longest common subsequence in $k$ -length substrings

Sebastian Deorowicz, Szymon Grabowski

Finding the longest common subsequence in $k$ -length substrings (LCS $k$ ) is a recently proposed problem motivated by computational biology. This is a generalization of the well-kno…

cs.DS2013★ 5 cited

Motif matching using gapped patterns

Emanuele Giaquinta, Kimmo Fredriksson, Szymon Grabowski +2

We present new algorithms for the problem of multiple string matching of gapped patterns, where a gapped pattern is a sequence of strings such that there is a gap of fixed length b…

cs.DS2012

Approximate pattern matching with k-mismatches in packed text

Emanuele Giaquinta, Szymon Grabowski, Kimmo Fredriksson

Given strings $P$ of length $m$ and $T$ of length $n$ over an alphabet of size $σ$ , the string matching with $k$ -mismatches problem is to find the positions of all the substrings i…

cs.DS2012★ 27 cited

New algorithms for binary jumbled pattern matching

Emanuele Giaquinta, Szymon Grabowski

Given a pattern $P$ and a text $T$ , both strings over a binary alphabet, the binary jumbled string matching problem consists in telling whether any permutation of $P$ occurs in $T$ …

cs.DS2010★ 19 cited

String Matching with Inversions and Translocations in Linear Average Time (Most of the Time)

Szymon Grabowski, Simone Faro, Emanuele Giaquinta

We present an efficient algorithm for finding all approximate occurrences of a given pattern $p$ of length $m$ in a text $t$ of length $n$ allowing for translocations of equal leng…