Search results for "Algorithm"

showing 10 items of 4887 documents

Computing the original eBWT faster, simpler, and with less memory

2021

Mantaci et al. [TCS 2007] defined the eBWT to extend the definition of the BWT to a collection of strings, however, since this introduction, it has been used more generally to describe any BWT of a collection of strings and the fundamental property of the original definition (i.e., the independence from the input order) is frequently disregarded. In this paper, we propose a simple linear-time algorithm for the construction of the original eBWT, which does not require the preprocessing of Bannai et al. [CPM 2021]. As a byproduct, we obtain the first linear-time algorithm for computing the BWT of a single string that uses neither an end-of-string symbol nor Lyndon rotations. We combine our ne…

FOS: Computer and information sciencesComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)
researchProduct

Substring Complexity in Sublinear Space

2020

Shannon's entropy is a definitive lower bound for statistical compression. Unfortunately, no such clear measure exists for the compressibility of repetitive strings. Thus, ad-hoc measures are employed to estimate the repetitiveness of strings, e.g., the size $z$ of the Lempel-Ziv parse or the number $r$ of equal-letter runs of the Burrows-Wheeler transform. A more recent one is the size $\gamma$ of a smallest string attractor. Unfortunately, Kempa and Prezza [STOC 2018] showed that computing $\gamma$ is NP-hard. Kociumaka et al. [LATIN 2020] considered a new measure that is based on the function $S_T$ counting the cardinalities of the sets of substrings of each length of $T$, also known as …

FOS: Computer and information sciencesComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)
researchProduct

A Constructive Arboricity Approximation Scheme

2018

The arboricity $\Gamma$ of a graph is the minimum number of forests its edge set can be partitioned into. Previous approximation schemes were nonconstructive, i.e., they only approximated the arboricity as a value without computing a corresponding forest partition. This is because they operate on the related pseudoforest partitions or the dual problem of finding dense subgraphs. We propose an algorithm for converting a partition of $k$ pseudoforests into a partition of $k+1$ forests in $O(mk\log k + m \log n)$ time with a data structure by Brodal and Fagerberg that stores graphs of arboricity $k$. A slightly better bound can be given when perfect hashing is used. When applied to a pseudofor…

FOS: Computer and information sciencesComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)MathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

Burrows Wheeler Transform on a Large Scale: Algorithms Implemented in Apache Spark

2021

With the rapid growth of Next Generation Sequencing (NGS) technologies, large amounts of "omics" data are daily collected and need to be processed. Indexing and compressing large sequences datasets are some of the most important tasks in this context. Here we propose algorithms for the computation of Burrows Wheeler transform relying on Big Data technologies, i.e., Apache Spark and Hadoop. Our algorithms are the first ones that distribute the index computation and not only the input dataset, allowing to fully benefit of the available cloud resources.

FOS: Computer and information sciencesComputer Science - Distributed Parallel and Cluster ComputingComputer Science - Data Structures and AlgorithmsData_FILESData Structures and Algorithms (cs.DS)Distributed Parallel and Cluster Computing (cs.DC)
researchProduct

Self-stabilizing Balls & Bins in Batches

2016

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where $m$ balls (tasks) are to be distributed to $n$ bins (servers). In a seminal work, Azar et al. proposed the sequential strategy \greedy{d} for $n=m$. When thrown, a ball queries the load of $d$ random bins and is allocated to a least loaded of these. Azar et al. showed that $d=2$ yields an exponential improvement compared to $d=1$. Berenbrink et al. extended this to $m\gg n$, showing that the maximal load difference is independent of $m$ for $d=2$ (in contrast to $d=1$). W…

FOS: Computer and information sciencesComputer Science - Distributed Parallel and Cluster ComputingTheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITYDistributed Parallel and Cluster Computing (cs.DC)MathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

Disentangling Derivatives, Uncertainty and Error in Gaussian Process Models

2020

Gaussian Processes (GPs) are a class of kernel methods that have shown to be very useful in geoscience applications. They are widely used because they are simple, flexible and provide very accurate estimates for nonlinear problems, especially in parameter retrieval. An addition to a predictive mean function, GPs come equipped with a useful property: the predictive variance function which provides confidence intervals for the predictions. The GP formulation usually assumes that there is no input noise in the training and testing points, only in the observations. However, this is often not the case in Earth observation problems where an accurate assessment of the instrument error is usually a…

FOS: Computer and information sciencesComputer Science - Machine Learning010504 meteorology & atmospheric sciencesComputer science0211 other engineering and technologiesMachine Learning (stat.ML)02 engineering and technology01 natural sciencesMachine Learning (cs.LG)symbols.namesakeStatistics - Machine LearningGaussian process021101 geological & geomatics engineering0105 earth and related environmental sciencesVariance functionPropagation of uncertaintyVariance (accounting)Function (mathematics)Confidence intervalNonlinear systemNoiseKernel method13. Climate actionKernel (statistics)symbolsAlgorithmIGARSS 2018 - 2018 IEEE International Geoscience and Remote Sensing Symposium
researchProduct

Cloud detection machine learning algorithms for PROBA-V

2020

This paper presents the development and implementation of a cloud detection algorithm for Proba-V. Accurate and automatic detection of clouds in satellite scenes is a key issue for a wide range of remote sensing applications. With no accurate cloud masking, undetected clouds are one of the most significant sources of error in both sea and land cover biophysical parameter retrieval. The objective of the algorithms presented in this paper is to detect clouds accurately providing a cloud flag per pixel. For this purpose, the method exploits the information of Proba-V using statistical machine learning techniques to identify the clouds present in Proba-V products. The effectiveness of the propo…

FOS: Computer and information sciencesComputer Science - Machine Learning010504 meteorology & atmospheric sciencesComputer scienceRemote sensing applicationFeature extraction0211 other engineering and technologiesFOS: Physical sciencesCloud computing02 engineering and technologyLand coverMachine learningcomputer.software_genre01 natural sciencesMachine Learning (cs.LG)Astrophysics::Galaxy Astrophysics021101 geological & geomatics engineering0105 earth and related environmental sciencesPixelbusiness.industrySupport vector machinePhysics - Atmospheric and Oceanic PhysicsAtmospheric and Oceanic Physics (physics.ao-ph)Artificial intelligencebusinesscomputerAlgorithm2017 IEEE International Geoscience and Remote Sensing Symposium (IGARSS)
researchProduct

Emulation as an Accurate Alternative to Interpolation in Sampling Radiative Transfer Codes

2018

Computationally expensive radiative transfer models (RTMs) are widely used to realistically reproduce the light interaction with the earth surface and atmosphere. Because these models take long processing time, the common practice is to first generate a sparse look-up table (LUT) and then make use of interpolation methods to sample the multidimensional LUT input variable space. However, the question arise whether common interpolation methodsperform most accurate. As an alternative to interpolation, this paper proposes to use emulation, i.e., approximating the RTM output by means of the statistical learning. Two experiments were conducted to assess the accuracy in delivering spectral outputs…

FOS: Computer and information sciencesComputer Science - Machine LearningAtmospheric Science010504 meteorology & atmospheric sciencesComputer science0211 other engineering and technologiesFOS: Physical sciences02 engineering and technologyStatistics - Applications01 natural sciencesArticleMachine Learning (cs.LG)Sampling (signal processing)KrigingInverse distance weightingApplications (stat.AP)Computers in Earth Sciences021101 geological & geomatics engineering0105 earth and related environmental sciencesEmulationArtificial neural networkMODTRANComputational Physics (physics.comp-ph)Physics - Atmospheric and Oceanic PhysicsAtmospheric and Oceanic Physics (physics.ao-ph)Lookup tablePhysics - Computational PhysicsAlgorithmInterpolationIEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing
researchProduct

Efficient Nonlinear RX Anomaly Detectors

2020

Current anomaly detection algorithms are typically challenged by either accuracy or efficiency. More accurate nonlinear detectors are typically slow and not scalable. In this letter, we propose two families of techniques to improve the efficiency of the standard kernel Reed-Xiaoli (RX) method for anomaly detection by approximating the kernel function with either {\em data-independent} random Fourier features or {\em data-dependent} basis with the Nystr\"om approach. We compare all methods for both real multi- and hyperspectral images. We show that the proposed efficient methods have a lower computational cost and they perform similar (or outperform) the standard kernel RX algorithm thanks t…

FOS: Computer and information sciencesComputer Science - Machine LearningBasis (linear algebra)Computer scienceComputer Vision and Pattern Recognition (cs.CV)Image and Video Processing (eess.IV)Computer Science - Computer Vision and Pattern Recognition0211 other engineering and technologiesApproximation algorithmHyperspectral imaging02 engineering and technologyElectrical Engineering and Systems Science - Image and Video ProcessingGeotechnical Engineering and Engineering GeologyRegularization (mathematics)Machine Learning (cs.LG)Nonlinear systemKernel (linear algebra)Kernel (statistics)FOS: Electrical engineering electronic engineering information engineeringAnomaly detectionElectrical and Electronic EngineeringAnomaly (physics)Algorithm021101 geological & geomatics engineeringIEEE Geoscience and Remote Sensing Letters
researchProduct

Multi-label Methods for Prediction with Sequential Data

2017

The number of methods available for classification of multi-label data has increased rapidly over recent years, yet relatively few links have been made with the related task of classification of sequential data. If labels indices are considered as time indices, the problems can often be seen as equivalent. In this paper we detect and elaborate on connections between multi-label methods and Markovian models, and study the suitability of multi-label methods for prediction in sequential data. From this study we draw upon the most suitable techniques from the area and develop two novel competitive approaches which can be applied to either kind of data. We carry out an empirical evaluation inves…

FOS: Computer and information sciencesComputer Science - Machine LearningComputer scienceMarkov modelsMulti-label classificationMachine Learning (stat.ML)02 engineering and technologycomputer.software_genreMarkov modelMachine learningTask (project management)Machine Learning (cs.LG)Statistics - Machine LearningArtificial Intelligence020204 information systemsComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringSequential dataData Structures and Algorithms (cs.DS)Multi-label classificationta113business.industryProblem transformationSignal ProcessingSequence prediction020201 artificial intelligence & image processingSequential dataComputer Vision and Pattern RecognitionData miningArtificial intelligencebusinesscomputerSoftware
researchProduct