8 papers
Dynamic Range Minimum Queries on the Ultra-Wide Word RAM
Philip Bille, Inge Li Gørtz, Tord Stordalen +1
We consider the dynamic range minimum problem on the ultra-wide word RAM model of computation. This model extends the classic -bit word RAM model with special ultrawords of leng…
Tighter Bounds for Wheeler Determinization
Philip Bille, Inge Li Gørtz, Inge Li Gørtz +3
Given a Wheeler NFA , the Wheeler determinization problem is to construct a Wheeler DFA that accepts the same language as . We use the notat…
Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille +2
Computing a minimum - cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, w…
Differentially Private Substring and Document Counting with Near-Optimal Error
Giulia Bernardini, Philip Bille, Inge Li Gørtz +1
For databases consisting of many text documents, one of the most fundamental data analysis tasks is counting (i) how often a pattern appears as a substring in the database (substri…
Improved Extended Regular Expression Matching
Philip Bille, Inge Li Gørtz, Inge Li Gørtz +1
An extended regular expression specifies a set of strings formed by characters from an alphabet combined with concatenation, union, intersection, complement, and star operators…
Compressed Dictionary Matching on Run-Length Encoded Strings
Philip Bille, Inge Li Gørtz, Simon J. Puglisi +1
Given a set of pattern strings and a text string , the classic dictionary matching problem is to report all occurrences of each pattern in…