2 Search Results for "Holub, Petr"


Document
Byte-Aligned Pattern Matching in Encoded Genomic Sequences

Authors: Petr Procházka and Jan Holub

Published in: LIPIcs, Volume 88, 17th International Workshop on Algorithms in Bioinformatics (WABI 2017)


Abstract
In this article, we propose a novel pattern matching algorithm, called BAPM, that performs searching in the encoded genomic sequences. The algorithm works at the level of single bytes and it achieves sublinear performance on average. The preprocessing phase of the algorithm is linear with respect to the size of the searched pattern m. A simple O(m)-space data structure is used to store all factors (with a defined length) of the searched pattern. These factors are later searched during the searching phase which ensures sublinear time on average. Our algorithm significantly overcomes the state-of-the-art pattern matching algorithms in the locate time on middle and long patterns. Furthermore, it is able to cooperate very easily with the block q-gram inverted index. The block q-gram inverted index together with our pattern matching algorithm achieve superior results in terms of locate time to the current index data structures for less frequent patterns. We present experimental results using real genomic data. These results prove efficiency of our algorithm.

Cite as

Petr Procházka and Jan Holub. Byte-Aligned Pattern Matching in Encoded Genomic Sequences. In 17th International Workshop on Algorithms in Bioinformatics (WABI 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 88, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{prochazka_et_al:LIPIcs.WABI.2017.20,
  author =	{Proch\'{a}zka, Petr and Holub, Jan},
  title =	{{Byte-Aligned Pattern Matching in Encoded Genomic Sequences}},
  booktitle =	{17th International Workshop on Algorithms in Bioinformatics (WABI 2017)},
  pages =	{20:1--20:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-050-7},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{88},
  editor =	{Schwartz, Russell and Reinert, Knut},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2017.20},
  URN =		{urn:nbn:de:0030-drops-76538},
  doi =		{10.4230/LIPIcs.WABI.2017.20},
  annote =	{Keywords: genomic sequences, pattern matching, q-gram inverted index}
}
Document
GPU-Based Sample-Parallel Context Modeling for EBCOT in JPEG2000

Authors: Jiri Matela, Vit Rusnak, and Petr Holub

Published in: OASIcs, Volume 16, Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers (2011)


Abstract
Embedded Block Coding with Optimal Truncation (EBCOT) is the fundamental and computationally very demanding part of the compression process of JPEG2000 image compression standard. EBCOT itself consists of two tiers. In Tier-1, image samples are compressed using context modeling and arithmetic coding. Resulting bit-stream is further formated and truncated in Tier-2. JPEG2000 has a number of applications in various fields where the processing speed and/or latency is a crucial attribute and the main limitation with state of the art implementations. In this paper we propose a new parallel approach to EBCOT context modeling that truly exploits massively parallel capabilities of modern GPUs and enables concurrent processing of individual image samples. Performance evaluation of our prototype shows speedup 12 times for the context modeller, and 1.4­5.3 times for the whole EBCOT Tier-1, which includes not yet optimized arithmetic coder.

Cite as

Jiri Matela, Vit Rusnak, and Petr Holub. GPU-Based Sample-Parallel Context Modeling for EBCOT in JPEG2000. In Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers. Open Access Series in Informatics (OASIcs), Volume 16, pp. 77-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{matela_et_al:OASIcs.MEMICS.2010.77,
  author =	{Matela, Jiri and Rusnak, Vit and Holub, Petr},
  title =	{{GPU-Based Sample-Parallel Context Modeling for EBCOT in JPEG2000}},
  booktitle =	{Sixth Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS'10) -- Selected Papers},
  pages =	{77--84},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-22-4},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{16},
  editor =	{Matyska, Ludek and Kozubek, Michal and Vojnar, Tomas and Zemcik, Pavel and Antos, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.MEMICS.2010.77},
  URN =		{urn:nbn:de:0030-drops-30681},
  doi =		{10.4230/OASIcs.MEMICS.2010.77},
  annote =	{Keywords: JPEG2000, EBCOT, Context Modeling, GPU, GPGPU, parallel}
}
  • Refine by Author
  • 1 Holub, Jan
  • 1 Holub, Petr
  • 1 Matela, Jiri
  • 1 Procházka, Petr
  • 1 Rusnak, Vit

  • Refine by Classification

  • Refine by Keyword
  • 1 Context Modeling
  • 1 EBCOT
  • 1 GPGPU
  • 1 GPU
  • 1 JPEG2000
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2011
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail