Zobrazeno 1 - 10
of 227
pro vyhledávání: '"BILLE, PHILIP"'
Differential privacy is the gold standard for privacy in data analysis. In many data analysis applications, the data is a database of documents. For databases consisting of many documents, one of the most fundamental problems is that of pattern match
Externí odkaz:
http://arxiv.org/abs/2412.13813
We consider succinct data structures for representing a set of $n$ horizontal line segments in the plane given in rank space to support \emph{segment access}, \emph{segment selection}, and \emph{segment rank} queries. A segment access query finds the
Externí odkaz:
http://arxiv.org/abs/2412.04965
We consider the dynamic range minimum problem on the ultra-wide word RAM model of computation. This model extends the classic $w$-bit word RAM model with special ultrawords of length $w^2$ bits that support standard arithmetic and boolean operation a
Externí odkaz:
http://arxiv.org/abs/2411.16281
Autor:
Tosoni, Francesco, Bille, Philip, Brunacci, Valerio, De Angelis, Alessio, Ferragina, Paolo, Manzini, Giovanni
Sparse matrix-vector multiplication (SpMV) is a fundamental operation in machine learning, scientific computing, and graph algorithms. In this paper, we investigate the space, time, and energy efficiency of SpMV using various compressed formats for l
Externí odkaz:
http://arxiv.org/abs/2409.18620
The weighted ancestor problem on a rooted node-weighted tree $T$ is a generalization of the classic predecessor problem: construct a data structure for a set of integers that supports fast predecessor queries. Both problems are known to require $\Ome
Externí odkaz:
http://arxiv.org/abs/2311.15777
A 'degenerate string' is a sequence of subsets of some alphabet; it represents any string obtainable by selecting one character from each set from left to right. Recently, Alanko et al. generalized the rank-select problem to degenerate strings, where
Externí odkaz:
http://arxiv.org/abs/2310.19702
We revisit the popular \emph{delayed deterministic finite automaton} (\ddfa{}) compression algorithm introduced by Kumar~et~al.~[SIGCOMM 2006] for compressing deterministic finite automata (DFAs) used in intrusion detection systems. This compression
Externí odkaz:
http://arxiv.org/abs/2306.12771
Autor:
Bille, Philip, Fischer, Johannes, Gørtz, Inge Li, Pedersen, Max Rishøj, Stordalen, Tord Joakim
Given a string $S$ over an alphabet $\Sigma$, the 'string indexing problem' is to preprocess $S$ to subsequently support efficient pattern matching queries, i.e., given a pattern string $P$ report all the occurrences of $P$ in $S$. In this paper we s
Externí odkaz:
http://arxiv.org/abs/2301.09477
Autor:
Bille, Philip, Gørtz, Inge Li, Lewenstein, Moshe, Pissis, Solon P., Rotenberg, Eva, Steiner, Teresa Anna
In Gapped String Indexing, the goal is to compactly represent a string $S$ of length $n$ such that for any query consisting of two strings $P_1$ and $P_2$, called patterns, and an integer interval $[\alpha, \beta]$, called gap range, we can quickly f
Externí odkaz:
http://arxiv.org/abs/2211.16860
Relative Lempel-Ziv (RLZ) parsing is a dictionary compression method in which a string $S$ is compressed relative to a second string $R$ (called the reference) by parsing $S$ into a sequence of substrings that occur in $R$. RLZ is particularly effect
Externí odkaz:
http://arxiv.org/abs/2208.11371