BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Aleksander Cisłak

Aleksander Cisłak contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Data Structures and Algorithms

Trust snapshot

Quick read

Trust 17 - UnverifiedVerification L1Unclaimed author
4works
0followers
1topics
1close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

4 published item(s)

preprint2020arXiv

SOPanG 2: online searching over a pan-genome without false positives

Motivation: The pan-genome can be stored as elastic-degenerate (ED) string, a recently introduced compact representation of multiple overlapping sequences. However, a search over the ED string does not indicate which individuals (if any) match the entire query. Results: We augment the ED string with sources (individuals' indexes) and propose an extension of the SOPanG (Shift-Or for Pan-Genome) tool to report only true positive matches, omitting those not occurring in any of the haplotypes. The additional stage for checking the matches yields a penalty of less than 3.5% relative speed in practice, which means that SOPanG 2 is able to report pattern matches in a pan-genome, mapping them onto individuals, at the single-thread throughput of above 430 MB/s on real data. Availability and implementation: SOPanG 2 can be downloaded here: github.com/MrAlexSee/sopang

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A practical index for approximate dictionary matching with few mismatches

Approximate dictionary matching is a classic string matching problem (checking if a query string occurs in a collection of strings) with applications in, e.g., spellchecking, online catalogs, geolocation, and web searchers. We present a surprisingly simple solution called a split index, which is based on the Dirichlet principle, for matching a keyword with few mismatches, and experimentally show that it offers competitive space-time tradeoffs. Our implementation in the C++ language is focused mostly on data compaction, which is beneficial for the search speed (e.g., by being cache friendly). We compare our solution with other algorithms and we show that it performs better for the Hamming distance. Query times in the order of 1 microsecond were reported for one mismatch for the dictionary size of a few megabytes on a medium-end PC. We also demonstrate that a basic compression technique consisting in $q$-gram substitution can significantly reduce the index size (up to 50% of the input text size for the DNA), while still keeping the query time relatively low.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A bloated FM-index reducing the number of cache misses during the search

The FM-index is a well-known compressed full-text index, based on the Burrows-Wheeler transform (BWT). During a pattern search, the BWT sequence is accessed at "random" locations, which is cache-unfriendly. In this paper, we are interested in speeding up the FM-index by working on $q$-grams rather than individual characters, at the cost of using more space. The first presented variant is related to an inverted index on $q$-grams, yet the occurrence lists in our solution are in the sorted suffix order rather than text order in a traditional inverted index. This variant obtains $O(m/|CL| + \log n \log m)$ cache misses in the worst case, where $n$ and $m$ are the text and pattern lengths, respectively, and $|CL|$ is the CPU cache line size, in symbols (typically 64 in modern hardware). This index is often several times faster than the fastest known FM-indexes (especially for long patterns), yet the space requirements are enormous, $O(n\log^2 n)$ bits in theory and about $80n$-$95n$ bytes in practice. For this reason, we dub our approach FM-bloated. The second presented variant requires $O(n\log n)$ bits of space.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Full-text and Keyword Indexes for String Searching

In this work, we present a literature review for full-text and keyword indexes as well as our contributions (which are mostly practice-oriented). The first contribution is the FM-bloated index, which is a modification of the well-known FM-index (a compressed, full-text index) that trades space for speed. In our approach, the count table and the occurrence lists store information about selected $q$-grams in addition to the individual characters. Two variants are described, namely one using $O(n \log^2 n)$ bits of space with $O(m + \log m \log \log n)$ average query time, and one with linear space and $O(m \log \log n)$ average query time, where $n$ is the input text length and $m$ is the pattern length. We experimentally show that a significant speedup can be achieved by operating on $q$-grams (albeit at the cost of very high space requirements, hence the name "bloated"). In the category of keyword indexes we present the so-called split index, which can efficiently solve the $k$-mismatches problem, especially for 1 error. Our implementation in the C++ language is focused mostly on data compaction, which is beneficial for the search speed (by being cache friendly). We compare our solution with other algorithms and we show that it is faster when the Hamming distance is used. Query times in the order of 1 microsecond were reported for one mismatch for a few-megabyte natural language dictionary on a medium-end PC. A minor contribution includes string sketches which aim to speed up approximate string comparison at the cost of additional space ($O(1)$ per string). They can be used in the context of keyword indexes in order to deduce that two strings differ by at least $k$ mismatches with the use of fast bitwise operations rather than an explicit verification.

0 citations0 reviewsNo code linkedOpen access