Browse
Recent Submissions
Now showing 1 - 5 of 123
- ItemRange Majorities and Minorities in Arrays(Springer Nature, 2021-03-19) Belazzougui, Djamal; Gagie, Travis; Munro, J. Ian; Navarro, Gonzalo; Nekrich, YakovThe problem of parameterized range majority asks us to preprocess a string of length n such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold τ. This is a more tractable version of the classical problem of finding the range mode, which is unlikely to be solvable in polylogarithmic time and linear space. In this paper we give the first linear-space solution with optimal 𝓞(1/τ ) query time, even when τ can be specified with the query. We then consider data structures whose space is bounded by the entropy of the distribution of the symbols in the sequence. For the case when the alphabet size is polynomial on the computer word size, we retain the optimal time within optimally compressed space (i.e., with sublinear redundancy). Otherwise, either the compressed space is increased by an arbitrarily small constant factor or the time rises to any function in (1/τ ) · ω(1). We obtain the same results on the complementary problem of parameterized range minority.
- ItemBlock Trees(ELSEVIER, 2021-05) Belazzougui, Djamal; Cáceres, Manuel; Gagie, Travis; Gawrychowski, Paweł; Kärkkäinen, Juha; Navarro, Gonzalo; Ordóñez, Alberto; Puglisi, Simon J.; Tabei, YasuoLet string S[1..n] be parsed into z phrases by the Lempel-Ziv algorithm. The corresponding compression algorithm encodes S in 𝒪(z) space, but it does not support random access to S. We introduce a data structure, the block tree, that represents S in 𝒪(z log(n/z)) space and extracts any symbol of T in time 𝒪(log(n/z)), among other space-time tradeoffs. By multiplying the space by the alphabet size, we also support rank and select queries, which are useful for building compressed data structures on top of S. Further, block trees can be built in a scalable manner. Our experiments show that block trees offer relevant space-time tradeoffs compared to other compressed string representations for highly repetitive strings.
- ItemLinear-time string indexing and analysis in small space(Association for Computing Machinery, 2020-03-09) Belazzougui, Djamal; Cunial, Fabio; Kärkkäinen, Juha; Mäkinen, VeliThe field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. For example, one can compare two genomes by building a common index for their concatenation, and by detecting common substructures by querying the index. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string T ∈ {1, . . . ,σ }^n can be built in deterministic O (n) time using just O (n log σ ) bits of space, where σ ≤ n. Deterministic linear time is achieved by exploiting a new partial rank data structure that supports queries in constant time, and that might have independent interest. Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of T . Many fundamental string analysis problems, such as maximal repeats, maximal unique matches, and string kernels, can be mapped to such enumeration, and can thus be solved in deterministic O (n) time and in O (n log σ ) bits of space from the input string, by tailoring the enumeration algorithm to some problem-specific computations. We also show how to build many of the existing indexes based on the BWT, such as the compressed suffix array, the compressed suffix tree, and the bidirectional BWT index, in randomized O (n) time and in O (n log σ ) bits of space. The previously fastest construction algorithms for BWT, compressed suffix array and compressed suffix tree, which used O (n log σ ) bits of space, took O (n log log σ ) time for the first two structures, and O (n log^ϵ n) time for the third, where ϵ is any positive constant smaller than one. Alternatively, the BWT could be previously built in linear time if one was willing to spend O (n log σ log log_σ n) bits of space. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output.
- ItemA critical review of quality of service models in mobile ad hoc networks(Inderscience Enterprises Ltd, 2019) Bouchama, Nadir; Aïssani, Djamil; Djellab, Natalia; Nouali-Taboudjemat, NadiaQuality of service (QoS) provisioning in mobile ad hoc networks (MANETs) consists of providing a complex functionality in a harsh environment where resources are scarce. Thus, it is very challenging to build an efficient solution to address this issue. The proposed solutions in the literature are broadly classified into four categories, namely: QoS routing protocols, QoS signalling, QoS-aware MAC protocols and QoS models, which are the main concern of our study. The contribution of this paper is threefold: Firstly, we propose a set of guidelines to deal with the challenges facing QoS models design in ad hoc networks. Secondly, we propose a new taxonomy for QoS models in ad hoc networks. Finally, we provide an in-depth survey and discussion of the most relevant proposed frameworks.
- ItemDFIOT: Data Fusion for Internet of Things(Springer Science, 2020) Boulkaboul, Sahar; Djenouri, DjamelIn Internet of Things (IoT) ubiquitous environments, a high volume of heterogeneous data is produced from different devices in a quick span of time. In all IoT applications, the quality of information plays an important role in decision making. Data fusion is one of the current research trends in this arena that is considered in this paper. We particularly consider typical IoT scenarios where the sources measurements highly conflict, which makes intuitive fusions prone to wrong and misleading results. This paper proposes a taxonomy of decision fusion methods that rely on the theory of belief. It proposes a data fusion method for the Internet of Things (DFIOT) based on Dempster–Shafer (D–S) theory and an adaptive weighted fusion algorithm. It considers the reliability of each device in the network and the conflicts between devices when fusing data. This is while considering the information lifetime, the distance separating sensors and entities, and reducing computation. The proposed method uses a combination of rules based on the Basic Probability Assignment (BPA) to represent uncertain information or to quantify the similarity between two bodies of evidence. To investigate the effectiveness of the proposed method in comparison with D–S, Murphy, Deng and Yuan, a comprehensive analysis is provided using both benchmark data simulation and real dataset from a smart building testbed. Results show that DFIOT outperforms all the above mentioned methods in terms of reliability, accuracy and conflict management. The accuracy of the system reached up to 99.18% on benchmark artificial datasets and 98.87% on real datasets with a conflict of 0.58%. We also examine the impact of this improvement from the application perspective (energy saving), and the results show a gain of up to 90% when using DFIOT.