Deep learning has become a primary choice in medical image analysis due to its powerful representation capability. However, most existing deep learning models designed for medical image classification can only perform well on a specific disease. The performance drops dramatically when it comes to other diseases. Generalizability remains a challenging problem. In this paper, we propose an evolutionary attention-based network (EDCA-Net), which is an effective and robust network for medical image classification tasks. To extract task-related features from a given medical dataset, we first propose the densely connected attentional network (DCA-Net) where feature maps are automatically channel-wise weighted, and the dense connectivity pattern is introduced to improve the efficiency of information flow. To improve the model capability and generalizability, we introduce two types of evolution: intra- and inter-evolution. The intra-evolution optimizes the weights of DCA-Net, while the inter-evolution allows two instances of DCA-Net to exchange training experience during training. The evolutionary DCA-Net is referred to as EDCA-Net. The EDCA-Net is evaluated on four publicly accessible medical datasets of different diseases. Experiments showed that the EDCA-Net outperforms the state-of-the-art methods on three datasets and achieves comparable performance on the last dataset, demonstrating good generalizability for medical image classification.

Bitvectors that support rank and select queries are the workhorses of succinct data structures, implementations of which are now widespread, for example, in bioinformatics software. To date, however, most bitvector implementations are static, thus forcing more complex data structures built from them to be static too. In this paper we explore dynamic bitvectors, which, in addition to rank and select queries, also support update operations, specifically: insert, remove, and modify. We first provide several practical optimizations to the recent B-tree based bitvectors of Prezza (Proc. SEA 2017), including the use of buffers at leaves to speed update operations at the cost of a small overhead to query times. We then consider a common use case of succinct data structures, where queries and updates come in separate batches, and examine the efficacy of query support data structures that are fast to construct and speed rank and select queries, but become out of date when update operations are made. Finally, we explore several methods for leaf compression.

Abstract Compact hash tables store a set S of n key-value pairs, where the keys are from the universe $$U = \{0,\ldots ,u-1\}$$ U = { 0 , … , u - 1 } , and the values are $$v$$ v -bit integers, in close to $${{\mathcal {B}}(u, n)} + nv$$ B ( u , n ) + n v bits of space, where $${{\mathcal {B}}(u, n)} = \log _2 {{u} \atopwithdelims (){n}}$$ B ( u , n ) = log 2 u n is the information-theoretic lower bound for representing the set of keys in S , and support operations insert, delete and lookup on S . Compact hash tables have received significant attention in recent years, and approaches dating back to Cleary [IEEE T. Comput, 1984], as well as more recent ones have been implemented and used in a number of applications. However, the wins on space usage of these approaches are outweighed by their slowness relative to conventional hash tables. In this paper, we demonstrate that compact hash tables based upon a simple idea of bucketing practically outperform existing compact hash table implementations in terms of memory usage and construction time, and existing fast hash table implementations in terms of memory usage (and sometimes also in terms of construction time), while having competitive query times. A related notion is that of a compact hash ID map , which stores a set $${\hat{S}}$$ S ^ of n keys from U , and implicitly associates each key in $${\hat{S}}$$ S ^ with a unique value (its ID), chosen by the data structure itself, which is an integer of magnitude O ( n ), and supports inserts and lookups on $${\hat{S}}$$ S ^ , while using space close to $${{\mathcal {B}}(u,n)}$$ B ( u , n ) bits. One of our approaches is suitable for use as a compact hash ID map.

The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known to require O(log log n) time for queries provided O(n polylog n) space is available and weights are from [0..n], where n is the number of tree nodes. However, when applied to suffix trees, the problem, surprisingly, admits an O(n)-space solution with constant query time, as was shown by Gawrychowski, Lewenstein, and Nicholson (Proc. ESA 2014). This variant of the problem can be reformulated as follows: given the suffix tree of a string s, we need a data structure that can locate in the tree any substring s[p..q] of s in O(1) time (as if one descended from the root reading s[p..q] along the way). Unfortunately, the data structure of Gawrychowski et al. has no efficient construction algorithm, limiting its wider usage as an algorithmic tool. In this paper we resolve this issue, describing a data structure for weighted ancestors in suffix trees with constant query time and a linear construction algorithm. Our solution is based on a novel approach using so-called irreducible LCP values.

We describe methods to support fast rank queries on the Burrows-Wheeler transform (BWT) string$S$of an input string$T$on alphabet$\Sigma$, in order to support pattern counting queries. Our starting point is an approach previously adopted by several authors, which is to represent$S$as$\vert \Sigma\vert$bitvectors, where the bitvector for symbol$c$has a 1 at position$c$if and only if$S[i]=c$, with the bitvec-tors stored in Elias-Fano (EF) encodings, to enable binary rank queries. We first show that the clustering of symbols induced by the BWT makes standard implementations of EF unattractive. We then engineer several improvements to EF that go some way to alleviating this problem, and go on to describe two new EF-inspired bitvectors that have superior practical performance.

In this paper we consider the problem of storing sequences of symbols in a compressed format, while supporting random access to the symbols without decompression. Although this is a well-studied problem when the data is textual, the kind of sequences we look at are not textual, and we argue that traditional compression methods used in the text algorithms community (such as compressors targeting k-th order empirical entropy) do not perform as well on these sequential data, and simpler methods such as Huffman-coding the deltas between sequence elements give better compression performance. We discuss data structures that allow random access to sequence elements that target such measures.

Compact hash tables store a set S of n key-value pairs, where the keys are from the universe U = {0,…,u-1}, and the values are v-bit integers, in close to B(u, n) + nv bits of space, where {b(u, n)} = log₂ binom(u,n) is the information-theoretic lower bound for representing the set of keys in S, and support operations insert, delete and lookup on S. Compact hash tables have received significant attention in recent years, and approaches dating back to Cleary [IEEE T. Comput, 1984], as well as more recent ones have been implemented and used in a number of applications. However, the wins on space usage of these approaches are outweighed by their slowness relative to conventional hash tables. In this paper, we demonstrate that compact hash tables based upon a simple idea of bucketing practically outperform existing compact hash table implementations in terms of memory usage and construction time, and existing fast hash table implementations in terms of memory usage (and sometimes also in terms of construction time). A related notion is that of a compact Hash ID map, which stores a set Ŝ of n keys from U, and implicitly associates each key in Ŝ with a unique value (its ID), chosen by the data structure itself, which is an integer of magnitude O(n), and supports inserts and lookups on Ŝ, while using close to B(u,n) bits. One of our approaches is suitable for use as a compact Hash ID map.

In recent years, the field of succinct data structures (SDS) has grown rapidly. SDS store data in main memory space that approaches an information-theoretic minimum, and support operations on the data with little or no slow-down compared to their conventional counterparts. In practice, an SDS uses one to two orders of magnitude less main memory than a conventional data structure. For this reason, SDS are becoming a popular approach for storing data that is only somewhat bigger than main memory. This tutorial explores the fundamentals of SDS and their applications to a variety of database problems.

In this paper we consider the problem of compactly representing a rewritable array of bit-strings. The operations supported are: create(N, k), which creates a new array of size N, where each entry is of size at most k bits and equal to 0; set(i, v), which sets A[i] to v, provided that v is at most k bits long and get(i) which returns the value of A[i]. Our aim is to approach the minimum possible space bound of , where |A[i]| ≥ 1 is the length in bits of the number in A[i], while simultaneously supporting operations in O(1) time. We call such a data structure a Compact Dynamic Rewriteable Array (CDRW) array. On the word RAM model with word size w, for n < 2w and k ≤ w, we give practical solutions based on compact hashing that achieve O(1/∊) expected time for get and set and use (1 + ∊)S + O(N) bits, for any constant ∊ > 0. Experimental evaluation of our (preliminary, only somewhat optimized) implementations shows excellent performance in terms of both space and time, particularly when heuristics are added to our base algorithms.

We consider practical implementations of compressed bitvectors, which support rank and select operations on a given bit-string, while storing the bit-string in compressed form. Our approach relies on variable-to-fixed encodings of the bit-string, an approach that has not yet been considered systematically for practical encodings of bitvectors. We show that this approach leads to fast practical implementations with low redundancy (i.e. the space used by the bitvector in addition to the compressed representation of the bit-string), and is a flexible and promising solution to the problem of supporting rank and select on moderately compressible bit-strings, such as those encountered in real-world applications.

Given an array A [1, n ] of elements with a total order, we consider the problem of building a data structure that solves two queries: ( a ) selection queries receive a range [ i , j ] and an integer k and return the position of the k th largest element in A [ i , j ]; ( b ) top- k queries receive [ i , j ] and k and return the positions of the k largest elements in A [ i , j ]. These problems can be solved in optimal time, O (1+lg k /lg lg n ) and O ( k ), respectively, using linear-space data structures. We provide the first study of the encoding data structures for the above problems, where A cannot be accessed at query time. Several applications are interested in the relative order of the entries of A , and their positions, rather their actual values, and thus we do not need to keep A at query time. In those cases, encodings save storage space: we first show that any encoding answering such queries requires n lg k - O ( n + k lg k ) bits of space; then, we design encodings using O ( n lg k ) bits, that is, asymptotically optimal up to constant factors, while preserving optimal query time.

Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel--Ziv family, run-length encoding, byte-pair encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$ achieving $O(\log N)$ random access time, and either $O(n\cdot\alpha_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $\alpha_k(n)$ is the inverse of the $k$th row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k,k^4+|P|\}+\log N)+\mathrm{occ})$, where $\mathrm{occ}$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy paths in grammars.

We consider practical implementations of compressed bit vectors, which support rank and select operations on a given bit-string, while storing thebit-string in compressed form. Our approach relies on variable-to-fixed (V2F) encodings of the bit-string, an approach that has not yet been considered systematically for practical encodings of bit-vectors. This approach leadsto fast practical implementations with low redundancy (i.e., the space used by the bit vector in addition to the compressed representation of the bit-string),and is a flexible and promising solution to the problem of supporting rank and select on moderately compressible bit-strings, such as those frequently found in real-world applications.

We consider the problem of preprocessing an array A[1..n] to answer range selection and range top-k queries. Given a query interval [i..j] and a value k, the former query asks for the position of the k-th largest value in A[i..j], whereas the latter asks for the positions of all the k largest values in A[i..j]. We consider the encoding} version of the problem, where A is not available at query time, and an upper bound kappa on k, the rank that is to be selected, is given at construction time. We obtain data structures with asymptotically optimal size and query time on a RAM model with word size Theta(lg(n)): our structures use O(n*lg(kappa)) bits and answer range selection queries in time O(1+lg(k) / lg(lg(n))) and range top-k queries in time O(k), for any k <= kappa.

Let S be a string of length N compressed into a context-free grammar S of size n. We present two representations of S achieving O(log N) random access time, and either O(n · αk(n)) construction time and space on the pointer machine model, or O(n) construction time and space on the RAM. Here, αk(n) is the inverse of the kth row of Ackermann's function. Our representations also efficiently support decompression of any substring in S: we can decompress any substring of length m in the same complexity as a single random access query and additional O(m) time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern P with at most k errors in time O(n(min{|P|k, k +|P|} +log N) + occ), where occ is the number of occurrences of P in S. Finally, we are able to generalize our results to navigation and other operations on grammar-compressed trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy-paths in grammars.

We consider the problem of representing, in a compressed format, a bit-vector~$S$ of $m$ bits with $n$ $\mathbf{1}$s, supporting the following operations, where $b \in \{ \mathbf{0}, \mathbf{1} \}$: \begin{itemize} \item $\mathtt{rank}_b(S,i)$ returns the number of occurrences of bit $b$ in the prefix $S\left[1..i\right]$; \item $\mathtt{select}_b(S,i)$ returns the position of the $i$th occurrence of bit $b$ in $S$. \end{itemize} Such a data structure is called \emph{fully indexable dictionary (\textsc{fid})} [Raman, Raman, and Rao, 2007], and is at least as powerful as predecessor data structures. Viewing $S$ as a set $X = \{ x_1, x_2, \ldots, x_n \}$ of $n$ distinct integers drawn from a universe $[m] = \{1, \ldots, m\}$, the predecessor of integer $y \in [m]$ in $X$ is given by $\ensuremath{\mathtt{select}^{}_1}(S, \ensuremath{\mathtt{rank}_1}(S,y-1))$. {\textsc{fid}}s have many applications in succinct and compressed data structures, as they are often involved in the construction of succinct representation for a variety of abstract data types. Our focus is on space-efficient {\textsc{fid}}s on the \textsc{ram} model with word size $\Theta(\lg m)$ and constant time for all operations, so that the time cost is independent of the input size. Given the bitstring $S$ to be encoded, having length $m$ and containing $n$ ones, the minimal amount of information that needs to be stored is $B(n,m) = \lceil \log {{m}\choose{n}} \rceil$. The state of the art in building a \textsc{fid}\ for~$S$ is given in~\mbox{}[P\v{a}tra\c{s}cu, 2008] using $B(m,n)+O( m / ( (\log m/ t) ^t) ) + O(m^{3/4}) $ bits, to support the operations in $O(t)$ time. Here, we propose a parametric data structure exhibiting a time/space trade-off such that, for any real constants $0 < \delta \leq 1/2$, $0 < \varepsilon \leq 1$, and integer $s > 0$, it uses \[ B(n,m) + O\left(n^{1+\delta} + n \left(\frac{m}{n^s}\right)^\varepsilon\right) \] bits and performs all the operations in time $O(s\delta^{-1} + \varepsilon^{-1})$. The improvement is twofold: our redundancy can be lowered parametrically and, fixing $s = O(1)$, we get a constant-time \textsc{fid}\ whose space is $B(n,m) + O(m^\varepsilon/\mathrm{poly}(n))$ bits, for sufficiently large $m$. This is a significant improvement compared to the previous bounds for the general case.

We describe the engineering of Succinct DOM (SDOM), a DOM implementation, written in C++, which is suitable for in-memory representation of large static XML documents. SDOM avoids the use of pointers, and is based upon succinct data structures, which use an information-theoretically minimum amount of space to represent an object.SDOM gives a space-efficient in-memory representation, with stable and predictable memory usage. The space used by SDOM is an order of magnitude less than that used by a standard C++ DOM representation such as Xerces, but SDOM is extremely fast: navigation is in some cases faster than for a pointer-based representation such as Xerces (even for moderate-sized documents which can comfortably be loaded into main memory by Xerces).A variant, SDOM-CT, applies bzip-based compression to textual and attribute data, and its space usage is comparable with XML compressors. Some of these compressors support navigation and/or querying (e.g. subpath queries) of the compressed file. SDOM-CT does not support querying directly, but remains extremely fast: it is several orders of magnitude faster for navigation than queryable XML compressors that support navigation (and only a few times slower than say Xerces).

Dilated integers form an ordered group of the Cartesian indices into a d-dimensional array represented in the Morton order. Efficient implementations of its operations can be found elsewhere. This paper offers efficient casting (type)conversions to and from an ordinary integer representation. As the Morton order representation for 2D and 3D arrays attracts more users because of its excellent block locality, the efficiency of these conversions becomes important. They are essential for programmers who would use Cartesian indexing there. Two algorithms for each casting conversion are presented here, including to-and-from dilated integers for both d = 2 and d = 3. They fall into two families. One family uses newly compact table lookup, so the cache capacity is better preserved. The other generalizes better to all d, using processor-local arithmetic that is newly presented as abstract d-ary and (d - 1)-ary recurrences. Test results for two and three dimensions generally favor the former.

We consider the indexable dictionary problem, which consists of storing a set S ⊆ {0,…, m − 1} for some integer m while supporting the operations of rank( x ), which returns the number of elements in S that are less than x if x ∈ S , and −1 otherwise; and select( i ), which returns the i th smallest element in S . We give a data structure that supports both operations in O (1) time on the RAM model and requires B( n, m ) + o ( n ) + O (lg lg m ) bits to store a set of size n , where B( n, m ) = ⌊lg ( m / n )⌋ is the minimum number of bits required to store any n -element subset from a universe of size m . Previous dictionaries taking this space only supported (yes/no) membership queries in O (1) time. In the cell probe model we can remove the O (lg lg m ) additive term in the space bound, answering a question raised by Fich and Miltersen [1995] and Pagh [2001]. We present extensions and applications of our indexable dictionary data structure, including: —an information-theoretically optimal representation of a k -ary cardinal tree that supports standard operations in constant time; —a representation of a multiset of size n from {0,…, m − 1} in B( n, m + n ) + o ( n ) bits that supports (appropriate generalizations of) rank and select operations in constant time; and + O (lg lg m ) —a representation of a sequence of n nonnegative integers summing up to m in B( n, m + n ) + o ( n ) bits that supports prefix sum queries in constant time.

We consider succinct or space-efficient representations of trees that efficiently support a variety of navigation operations. We focus on static ordinal trees, that is, arbitrary static rooted trees where the children of each node are ordered. The set of operations is essentially the union of the sets of operations supported by previous succinct representations [Jacobson 1989; Munro and Raman 2001; Benoit et al. 1999] to which we add the level-ancestor operation.Our representation takes 2 n + o ( n ) bits to represent an n -node tree, which is within o ( n ) bits of the information-theoretic minimum, and supports all operations in O (1) time on the RAM model. These operations also provide a mapping from the n nodes of the tree onto the integers {1, …, n }. In addition to the existing motivations for studying such data structures, we are motivated by the problem of representing XML documents compactly so that XPath queries can be supported efficiently.

We show that a unit-cost RAM with a word length of w bits can sort n integers in the range O. .2W -1 in O (n log log n) time, for arbitrary w z log n, a significant improvement over the bound of O (n-) achieved by the fusion trees of Fredman and Willard.Provided that w 2 (log n)z+', for some fixed e > 0, the sorting can even be accomplished in linear expected time with a randomized algorithm.Both of our algorithms parallelize without loss on a unitcost PRAM with a word length of w bits.The first one yields an algorithm that uses O (log n) time and O (n log log n) operations on a deterministic CRCW PRAM.The second one yields an algorithm that uses O(log n) expected time and O(n) expected operations on a randomized EREW PRAM, provided that w 2 (log n)2+' for some fixed c >0.Our deterministic and randomized sequential and parallel algorithms generalize to the lexicographic sorting problem of sorting multiple-precision integers represented in several words.

We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D > 1. The data structure can be modified to run in O(log 2 n) expected time per update in the algebraic computation tree model. Even this version is more efficient than the best currently known deterministic algorithm for D > 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.

Padded sorting requires n input keys to be output in sorted order in an array with slightly more than n locations, unused locations being filled with a special null value.We show that a deterministic CRCW PRAM with h processors can padded-sort n keys in ~(log log k)s .2°(*0g" '-lOg* '+1) time, for any k with 4 s k s n, which is close to a known lower bound of Q(log n/log k).As a consequence, we are able to improve the best previous result on deterministic sublogarithmic standard sorting.Other results include deterministic algorithms with optimal speedup for approximate prefix summation and for padded-sorting independent uniformly distributed random variables.In the first case the running time is O((log log n)4/log log log n), and in the second case the average running time is O((log log log n)4 /log(4) n).

Conventional parallel sorting requires the n input keys to be output in an array of size n, and is known to take Omega (log n/log log n) time using any polynomial number of processors. The lower bound does not apply to the more 'wasteful' convention of padded sorting, which requires the keys to be output in sorted order in an array of size (1+o(1))n. The authors give very fast randomised CRCW PRAM algorithms for several padded-sorting problems. Applying only pairwise comparisons to the input and using kn processors, where 2>