Browsing by Author "0b299f8a-96ef-4215-819d-9ba77fe8f9d1"
Now showing items 1-15 of 15
-
(Taylor & Francis, 2020)As the number of vehicles and devices equipped with GPS technology has grown explosively, an urgent need has arisen for time- and space-efficient data structures to represent their trajectories. The most commonly desired ...
-
(Springer, 2020)In the range alpha-majority query problem, we are given a sequence S[1 horizontal ellipsis n] and a fixed threshold alpha is an element of(0,1), and are asked to preprocess S such that, given a query range [i horizontal ...
-
(Institute of Electrical and Electronics Engineers Inc., 2017)In the range α-majority query problem, we preprocess a given sequence S[1.n] for a fixed threshold α ϵ (0, 1], such that given a query range [i.j], the symbols that occur more than α (j-i+1) times in S[i.j] can be reported ...
-
(Springer, 2017-06)Most of the fastest-growing string collections today are repetitive, that is, most of the constituent documents are similar to many others. As these collections keep growing, a key approach to handling them is to exploit ...
-
(Springer, 2017)We present a new compressed representation of free trajectories of moving objects. It combines a partial-sums-based structure that retrieves in constant time the position of the object at any instant, with a hierarchical ...
-
(Institute of Electrical and Electronics Engineers Inc., 2018)Computing the product of the (binary) adjacency matrix of a large graph with a real-valued vector is an important operation that lies at the heart of various graph analysis tasks, such as computing PageRank. In this paper ...
-
(Elsevier, 2020)There are many representations of planar graphs, but few are as elegant as Turan's (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multiedges, and can store any specified embedding. ...
-
(Springer, 2017)There are many representations of planar graphs but few are as elegant as Turán’s (1984): it is simple and practical, uses only four bits per edge, can handle multi-edges and can store any specified embedding. Its main ...
-
(Assoc Computing Machinery, USA, 2020)Indexing highly repetitive texts-such as genomic databases, software repositories and versioned text collections-has become an important problem since the turn of the millennium. A relevant compressibility measure for ...
-
(Springer, 2018)
-
(Springer Verlag, 2018)Shannon’s entropy is a clear lower bound for statistical compression. The situation is not so well understood for dictionary-based compression. A plausible lower bound is b, the least number of phrases of a general ...
-
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2017)Let f: [1.n] → [1.n] be a function, and i: [1.n] → [1.σ] indicate a label assigned to each element of the domain. We design several compact data structures that answer various queries on the labels of paths in f. For ...
-
(The British Computer Society, 2018-05)Suffix trees are one of the most versatile data structures in stringology, with many applications in bioinformatics. Their main drawback is their size, which can be tens of times larger than the input sequence. Much effort ...
-
(Elsevier, 2020)We present the first solution to finding tau-majorities on tree paths. Given a tree of nnodes, each with a label from [1..sigma], and a fixed threshold 0 < tau 1, such a query gives two nodes u nd v nd asks for all the ...
-
(Institute of Electrical and Electronics Engineers Inc., 2018)The Block Tree (BT) is a novel compact data structure designed to compress sequence collections. It obtains compression ratios close to Lempel-Ziv and supports efficient direct access to any substring. The BT divides the ...
