Source author record

Oliver Serang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computation Machine Learning Numerical Analysis Computational Engineering, Finance, and Science Computational Geometry math.NA Mathematical Software Methodology

Catalog footprint

Research overview

8works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Fast exact computation of the $k$ most abundant isotope peaks with layer-ordered heaps

The theoretical computation of isotopic distribution of compounds is crucial in many important applications of mass spectrometry, especially as machine precision grows. A considerable amount of good tools have been created in the last decade for doing so. In this paper we present a novel algorithm for calculating the top $k$ peaks of a given compound. The algorithm takes advantage of layer-ordered heaps used in an optimal method of selection on $X+Y$ and is able to efficiently calculate the top $k$ peaks on very large molecules. Among its peers, this algorithm shows a significant speedup on molecules whose elements have many isotopes. The algorithm obtains a speedup of more than 31x when compared to $\textsc{IsoSpec}$ on \ch{Au2Ca10Ga10Pd76} when computing 47409787 peaks, which covers 0.999 of the total abundance.

preprint2020arXiv

Optimal construction of a layer-ordered heap

The layer-ordered heap (LOH) is a simple, recently proposed data structure used in optimal selection on $X+Y$ , thealgorithm with the best known runtime for selection on $X_1+X_2+\cdots+X_m$ , and the fastest method in practice for computing the most abundant isotope peaks in a chemical compound. Here, we introduce a few algorithms for constructing LOHs, analyze their complexity, and demonstrate that one algorithm is optimal for building a LOH of any rank $α$ . These results are shown to correspond with empirical experiments of runtimes when applying the LOH construction algorithms to a common task in machine learning.

preprint2020arXiv

Selection on $X_1 + X_1 + \cdots X_m$ via Cartesian product tree

Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on $X+Y$ , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of $X+Y$ selections was proposed to perform $k$ -selection on $X_1+X_2+\cdots+X_m$ in $o(n\cdot m + k\cdot m)$ , where $X_i$ have length $n$ . Here, that $o(n\cdot m + k\cdot m)$ algorithm is combined with a novel, optimal LOH-based algorithm for selection on $X+Y$ (without a soft heap). Performance of algorithms for selection on $X_1+X_2+\cdots+X_m$ are compared empirically, demonstrating the benefit of the algorithm proposed here.

preprint2020arXiv

Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps

Selection on $X_1+X_2+\cdots + X_m$ is an important problem with many applications in areas such as max-convolution, max-product Bayesian inference, calculating most probable isotopes, and computing non-parametric test statistics, among others. Faster-than-naïve approaches exist for $m=2$ : Frederickson (1993) published the optimal algorithm with runtime $O(k)$ and Kaplan \emph{et al.} (2018) has since published a much simpler algorithm which makes use of Chazelle's soft heaps (2003). No fast methods exist for $m>2$ . Johnson \& Mizoguchi (1978) introduced a method to compute the single $k^{th}$ value when $m>2$ , but that method runs in $O(m\cdot n^{\lceil\frac{m}{2}\rceil} \log(n))$ time and is inefficient when $m \gg 1$ and $k \ll n^{\lceil\frac{m}{2}\rceil}$ . In this paper, we introduce the first efficient methods, both in theory and practice, for problems with $m>2$ . We introduce the ``layer-ordered heap,'' a simple special class of heap with which we produce a new, fast selection algorithm on the Cartesian product. Using this new algorithm to perform $k$ -selection on the Cartesian product of $m$ arrays of length $n$ has runtime $\in o(k\cdot m)$ . We also provide implementations of the algorithms proposed and evaluate their performance in practice.

preprint2016arXiv

An exact, cache-localized algorithm for the sub-quadratic convolution of hypercubes

Fast multidimensional convolution can be performed naively in quadratic time and can often be performed more efficiently via the Fourier transform; however, when the dimensionality is large, these algorithms become more challenging. A method is proposed for performing exact hypercube convolution in sub-quadratic time. The method outperforms FFTPACK, called via numpy, and FFTW, called via pyfftw) for hypercube convolution. Embeddings in hypercubes can be paired with sub-quadratic hypercube convolution method to construct sub-quadratic algorithms for variants of vector convolution.

preprint2016arXiv

Fast Computation on Semirings Isomorphic to $(\times, \max)$ on $\mathbb{R}_+$

Important problems across multiple disciplines involve computations on the semiring $(\times, \max)$ (or its equivalents, the negated version $(\times, \min)$ ), the log-transformed version $(+, \max)$ , or the negated log-transformed version $(+, \min)$ ): max-convolution, all-pairs shortest paths in a weighted graph, and finding the largest $k$ values in $x_i+y_j$ for two lists $x$ and $y$ . However, fast algorithms such as those enabling FFT convolution, sub-cubic matrix multiplication, \emph{etc.}, require inverse operations, and thus cannot be computed on semirings. This manuscript generalizes recent advances on max-convolution: in this approach a small family of $p$ -norm rings are used to efficiently approximate results on a nonnegative semiring. The general approach can be used to easily compute sub-cubic estimates of the all-pairs shortest paths in a graph with nonnegative edge weights and sub-quadratic estimates of the top $k$ values in $x_i+y_j$ when $x$ and $y$ are nonnegative. These methods are fast in practice and can benefit from coarse-grained parallelization.

preprint2015arXiv

A Bounded $p$ -norm Approximation of Max-Convolution for Sub-Quadratic Bayesian Inference on Additive Factors

Max-convolution is an important problem closely resembling standard convolution; as such, max-convolution occurs frequently across many fields. Here we extend the method with fastest known worst-case runtime, which can be applied to nonnegative vectors by numerically approximating the Chebyshev norm $\| \cdot \|_\infty$ , and use this approach to derive two numerically stable methods based on the idea of computing $p$ -norms via fast convolution: The first method proposed, with runtime in $O( k \log(k) \log(\log(k)) )$ (which is less than $18 k \log(k)$ for any vectors that can be practically realized), uses the $p$ -norm as a direct approximation of the Chebyshev norm. The second approach proposed, with runtime in $O( k \log(k) )$ (although in practice both perform similarly), uses a novel null space projection method, which extracts information from a sequence of $p$ -norms to estimate the maximum value in the vector (this is equivalent to querying a small number of moments from a distribution of bounded support in order to estimate the maximum). The $p$ -norm approaches are compared to one another and are shown to compute an approximation of the Viterbi path in a hidden Markov model where the transition matrix is a Toeplitz matrix; the runtime of approximating the Viterbi path is thus reduced from $O( n k^2 )$ steps to $O( n$ k \log(k))$ steps in practice, and is demonstrated by inferring the U.S. unemployment rate from the S&P 500 stock index.

preprint2015arXiv

A fast numerical method for max-convolution and the application to efficient max-product inference in Bayesian networks

Observations depending on sums of random variables are common throughout many fields; however, no efficient solution is currently known for performing max-product inference on these sums of general discrete distributions (max-product inference can be used to obtain maximum a posteriori estimates). The limiting step to max-product inference is the max-convolution problem (sometimes presented in log-transformed form and denoted as "infimal convolution", "min-convolution", or "convolution on the tropical semiring"), for which no O(k log(k)) method is currently known. Here I present a O(k log(k)) numerical method for estimating the max-convolution of two nonnegative vectors (e.g., two probability mass functions), where k is the length of the larger vector. This numerical max-convolution method is then demonstrated by performing fast max-product inference on a convolution tree, a data structure for performing fast inference given information on the sum of n discrete random variables in O(n k log(n k) log(n) ) steps (where each random variable has an arbitrary prior distribution on k contiguous possible states). The numerical max-convolution method can be applied to specialized classes of hidden Markov models to reduce the runtime of computing the Viterbi path from n k^2 to n k log(k), and has potential application to the all-pairs shortest paths problem.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Oliver Serang

Research overview

Is this your work?

8 publications

Fast exact computation of the $k$ most abundant isotope peaks with layer-ordered heaps

Optimal construction of a layer-ordered heap

Selection on $X_1 + X_1 + \cdots X_m$ via Cartesian product tree

Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps

An exact, cache-localized algorithm for the sub-quadratic convolution of hypercubes

Fast Computation on Semirings Isomorphic to $(\times, \max)$ on $\mathbb{R}_+$

A Bounded $p$ -norm Approximation of Max-Convolution for Sub-Quadratic Bayesian Inference on Additive Factors

A fast numerical method for max-convolution and the application to efficient max-product inference in Bayesian networks

See the researcher in context

Building this map preview

Oliver Serang

Research overview

Is this your work?

8 publications

Fast exact computation of the kkk most abundant isotope peaks with layer-ordered heaps

Optimal construction of a layer-ordered heap

Selection on X1+X1+⋯XmX_1 + X_1 + \cdots X_mX1​+X1​+⋯Xm​ via Cartesian product tree

Selection on X1+X2+⋯+XmX_1+X_2+\cdots + X_mX1​+X2​+⋯+Xm​ with layer-ordered heaps

An exact, cache-localized algorithm for the sub-quadratic convolution of hypercubes

Fast Computation on Semirings Isomorphic to (×,max⁡)(\times, \max)(×,max) on R+\mathbb{R}_+R+​

A Bounded ppp-norm Approximation of Max-Convolution for Sub-Quadratic Bayesian Inference on Additive Factors

A fast numerical method for max-convolution and the application to efficient max-product inference in Bayesian networks

See the researcher in context

Building this map preview

Fast exact computation of the $k$ most abundant isotope peaks with layer-ordered heaps

Selection on $X_1 + X_1 + \cdots X_m$ via Cartesian product tree

Selection on $X_1+X_2+\cdots + X_m$ with layer-ordered heaps

Fast Computation on Semirings Isomorphic to $(\times, \max)$ on $\mathbb{R}_+$

A Bounded $p$ -norm Approximation of Max-Convolution for Sub-Quadratic Bayesian Inference on Additive Factors