Search

In a recent paper, the question of determining the fraction of binary trees that contain a fixed pattern known as the snowflake was posed. We show that this fraction goes to 1, providing two very different proofs: a purely combinatorial one that is quantitative and specific to this problem; and a proof using branching process techniques that is less explicit, but also much more general, as it applies to any fixed patterns and can be extended to other trees and networks. In particular, it follows immediately from our second proof that the fraction of d-ary trees (resp. level-k networks) that contain a fixed d-ary tree (resp. level-k network) tends to 1 as the number of leaves grows. [ABSTRACT FROM AUTHOR]

The main objective of this article is to establish a central limit theorem for additive three-variable functionals of bifurcating Markov chains. We thus extend the central limit theorem under point-wise ergodic conditions studied in S.V. Bitseki Penda and J.-F. Delmas [Central limit theorem for bifurcating Markov chains under pointwise ergodic conditions, Ann. Appl. Probab. 32(5) (2022), pp. 3817–3849] and to a lesser extent, the results of S.V. Bitseki Penda and J.-F. Delmas [Central limit theorem for bifurcating Markov chains under $ L^2 $ L 2 -ergodic conditions, Adv. Appl. Probab. 54(4) (2022), pp. 999–1031] on central limit theorem under $ L^{2} $ L 2 ergodic conditions. Our results also extend and complement those of J. Guyon [Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging, Ann. Appl. Probab. 17(5–6) (2007), pp. 1538–1569] and J.-F. Delmas and L. Marsalle [Detection of cellular aging in a Galton-Watson process, Stochastic Process. Appl. 120(12) (2010), pp. 2495–2519]. In particular, when the ergodic rate of convergence is greater than $ 1/\sqrt {2} $ 1 / 2 , we have, for certain class of functions, that the asymptotic variance is non-zero at a speed faster than the usual central limit theorem studied by Guyon and Delmas-Marsalle. [ABSTRACT FROM AUTHOR]

The Catalan numbers are ubiquitous in counting problems which is one of the primary reasons for its popularity. From various sources like books and Wikipedia we see that in combinatorial mathematics. The Catalan numbers form is a sequence of natural numbers that occur in various counting problems, often involving recursively-defined objects such as polygon triangulation, balanced parentheses, mountain ranges, diagonal avoiding paths and binary tree. Belgian mathematician Eugene Charles Catalan discovered Catalan numbers in 1838, while studying well-formed sequences of parentheses. They are named after the Belgian mathematician Eugene Charles Catalan. Although they are named after Catalan, they were not first discovered by him. These numbers appear in a variety of disguises, we are so used to having them around, it is perhaps hard to imagine a time when they were either unknown, or known but obscure and underappreciated. The organization of this paper is as follows. The first we encountered a number of occurrences of the CBC and Catalan numbers. Then, we study to understand the connections between these numbers and well-known structures of Catalan numbers like dyck paths, binary trees, permutations, partitions and etc. We also discuss some algebraic interpretations and additional aspects of Catalan numbers. 1- IntroductionFor positive integers $n\geq k$, the \textit{Binomial coefficient} ${n\choose k}=\frac{n!}{k!(n-k)!}$ appears in Khayyam Triangle which is one of the most important object to solving and proposing combinatorics problems. Using properties of binomial coefficients, we can write\begin{eqnarray*}{2n\choose n}&=&{2n-1\choose n-1}+{2n-1\choose n}\\&=&{2n-1\choose n}+{2n-1\choose n}\\&=&2{2n-1\choose n},\end{eqnarray*}where show these numbers are even. The \textit{CBC}s $\binom{2n}{n}$ are centrally located in even numbered rows in Pascal’s triangle, as Figure 1 shows. It was conjectured by \textit{Paul Erd\H{o}s} that the CBC numbers are squarefree for all $n>4$. This conjecturewas proved for every sufficiently large $n$ [4,16]. These numbers appears in several importance sequences like \textit{Catalan, Narayana, Motzikin and etc.} This is one of the reasons for researchers to having special attention to these numbers. The $n$-Catalan numbers defined as $C_n=\frac{1}{n+1}{2n\choose n}$, with initial value $C_0=1$. To date, nearly 400 articles and problems have appeared on Catalan numbers. \textit{Richard P. Stanley} of Massachusetts Institute of Technology has listed over $270$ occurrences of Catalan numbers in his EnumerativeCombinatorics, vol. 2, and another seventy on his Web site Catalan Addendum [17,18]. The CBC numbers are given as sequence $A000108 $ in the On-Line Encyclopedia of Integer Sequences [20]. Using generating functions, It can be employed to derive the following explicit formula . To this end, consider the generating function $C(x)=\sum_{n=0}^{\infty} C_nx^n=C_0+C_1x+C_2x^2+\cdots$. Using some initial values of Catalan numbers, we can write\begin{align*}\label{GF}xC^2(x)&=(1+x+2x^2+5x^3+14x^4+42x^5+\cdots)^2\\&=1+2x+5x^2+14x^3+\cdots =C(x)-1.\end{align*}Then\begin{eqnarray}4x^2C^2(x)=4xC(x)-4x+1-1\end{eqnarray}Solving for $C(x)=\frac{1-\sqrt{1-4x}}{2x}$. In this paper, we introduce and prove some structures of Catalan numbers. The set family like $\{\S_i\}_{n=1}^{\infty}$ is called structures of Catalan numbers if it can define the bijection $F: \S_n\longrightarrow C_n$ between these family and Catalan numbers. In the Section 1, we shall only study Dyck paths, and provide several bijective proofs like polygon triangulation, balanced parentheses, mountain ranges, that they are counted by Catalan numbers. We first introduce Dyck and binary paths, and then state our main theorem in Section 2.In Section 3, we states structures of Catalan numbers and Nonintersecting Chords. Let we have $2n$ persons with labaled $v_1; v_2;\ldots;v_{2n}$ such that located at the boundary of a circle with equal distancebetween every two adjacent persons. Let $R_n$ be the set of different ways to pair the $2n$persons with edges (as straight lines) that do no intersect. Then, $|R_n| = |C_n|$. In Section 4, we find structures of Catalan numbers and triangulated polygons. Section 5 devoted to structures of Catalan numbers and words. A \textit{plane tree} is a rooted tree with an ordering specified for the children of eachvertex. In the Section 6, we proved $C_n$ counts the number of plane trees with $n+1$ vertices and also, states several new structures of Catalan numbers and trees. Sections 7 and 8 devoted to structures of Catalan numbers between permutations and partitions., respectability. 2- Main ResultsThere are many equivalent ways to define Catalan numbers. The main results of this paper,focus on combinatorial interpretations of Catalannumbers. Some of these structures of Catalan numbers which is discuss in this paper are1) Dyck paths of length $n$ with two steps $(0,1)$ and $(1,0)$.2) binary parenthesizations of a string of $n+1$ letters.3) The set of binary trees with n nodes.4) Plane trees with n internal nodes, all of degree 2.5) Paths from $(0,0)$ to $(2n,0)$ with steps $(1,−1)$ and $(1, 1)$, never falling below the $x$-axis.6) Noncrossing pairs of sequences of $n+1$ steps $(1, 0)$ and $(0, 1)$, which only intersect at start and end.7) In Stanley, this is described as non-intersecting arcs joining $n$ pairs of points in the plane. Our preferred version of this representation is to think of it as partitions of $2n$ into blocks of size 2.8) $n$ nonintersecting chords joining $2n$ points on a circle.9) Ways of drawing $n +1$ points on a line with arcs connecting them such that the arcs do not pass below the line, the arcs are noncrossing, all the arcs at a given node exit in the same direction (left or right), and the graph thus formed is a tree.10) Partitions of an $(n + 2)$-gon into triangles.11) Noncrossing partitions of $[n]$.12) Noncrossing Murasaki diagrams with $n$ vertical bars.13) Nonnesting partitions of $[n]$.14) Permutations of the multiset $\{1^2, 2^2,\ldots,n^2\}$ such that the first occurrences of each number appear in increasing order, and there is no subsequenceof the form $abab$.15) $321$-avoiding permutations of $[n]$.16) Permutations w of $[2n]$ with $n$ cycles of length two such that the product $(1, 2,\ldots,2n)w$ has $n$ cycles.17) Permutations of $[n]$ that can be stack sorted.18) Binary parenthesizations of a string of $n + 1$ letters.19) The numbers of the sequences $(a_1,\ldots,a_n)$ such that $1\leq a_1\leq \cdots \leq a_n$ and $a_i\leq i$.20) Standard Young Tableux of shape $(n, n)$.3- ConclusionsWe have studied some nice structures of the Catalan numbers in this paper. We make frequent references to Stanley’s list of Catalan representations [19]. These can be found in exercise 6.19, where each of the representations discussed is given as a part of the exercise. So, the first, we encountered a number of occurrences of the CBC $\binom{2n}{n}$ and Catalan numbers. Then, we study to understand the connections between these numbers and well-known structures of Catalan numbers like dyck paths, binary trees, permutations, partitions and etc. We also discuss some algebraic interpretations and additional aspects of Catalan numbers. It would be interesting for readers to considering results on divisibility of CBC and Catalan numbers. It would be interesting to explore similar techniques for Structures of Motzkin numbers, Delannoy numbers, Narayana Numbers and etc.

The least squares (LS) estimator of the autoregressive coefficient in the bifurcating autoregressive (BAR) model was recently shown to suffer from substantial bias, especially for small to moderate samples. This study investigates the impact of the bias in the LS estimator on the behavior of various types of bootstrap confidence intervals for the autoregressive coefficient and introduces methods for constructing bias-corrected bootstrap confidence intervals. We first describe several bootstrap confidence interval procedures for the autoregressive coefficient of the BAR model and present their bias-corrected versions. The behavior of uncorrected and corrected confidence interval procedures is studied empirically through extensive Monte Carlo simulations and two real cell lineage data applications. The empirical results show that the bias in the LS estimator can have a significant negative impact on the behavior of bootstrap confidence intervals and that bias correction can significantly improve the performance of bootstrap confidence intervals in terms of coverage, width, and symmetry. [ABSTRACT FROM AUTHOR]

Bifurcating Markov chains are Markov chains indexed by a full binary tree representing the evolution of a trait along a population where each individual has two children. Motivated by the functional estimation of the density of the invariant probability measure which appears as the asymptotic distribution of the trait, we prove the consistency and the Gaussian fluctuations for a kernel estimator of this density based on late generations. In this setting, it is interesting to note that the distinction of the three regimes on the ergodic rate identified in a previous work (for fluctuations of average over large generations) disappears. This result is a first step to go beyond the threshold condition on the ergodic rate given in previous statistical papers on functional estimation. [ABSTRACT FROM AUTHOR]

Quantum computers provide an opportunity to efficiently sample from probability distributions that include non-trivial interference effects between amplitudes. Using a simple process wherein all possible state histories can be specified by a binary tree, we construct an explicit quantum algorithm for an important three-dimensional subspace of the parameter space that runs in polynomial time to sample from the process once. The corresponding naive Markov chain algorithm does not produce the correct probability distribution and an explicit classical calculation of the full distribution requires exponentially many operations. However, the problem can be reduced to a system of two qubits with repeated measurements, shedding light on a quantum-inspired efficient classical algorithm.

We continue study of some algebraic varieties (called resultantal varieties) started in a paper of authors "L-functions of Carlitz modules, resultantal varieties and rooted binary trees, I", cited as [4]. These varieties are related with the Sylvester matrix for the resultant of two polynomials, from one side, and with the L-functions of twisted Carlitz modules, from another side. They are described in terms of weighted rooted binary trees. We give some proofs that lack in [4], some examples and tables that confirm conjectures from [4], and some ideas of development of this theory. [ABSTRACT FROM AUTHOR]

Bitseki and Delmas (2022) have studied recently the central limit theorem for kernel estimator of invariant density in bifurcating Markov chains. We complete their work by proving a moderate deviation principle for this estimator. Unlike the work of Bitseki and Gorgui (2022), it is interesting to see that the distinction of the two regimes disappears and that we are able to get moderate deviation principle for large values of the ergodic rate. It is also interesting and surprising to see that for moderate deviation principle, the ergodic rate begins to have an impact on the choice of the bandwidth for values smaller than in the context of central limit theorem studied by Bitseki and Delmas (2022). [ABSTRACT FROM AUTHOR]

Simple Summary: This article proposes a comparative study between two models that can be used by researchers for the analysis of survival data: Weibull regression and random survival forest. The models are compared considering the error rate, the performance of the model through the Harrell C-index, and the identification of the relevant variables for survival prediction. A statistical analysis of a data set from the Heart Institute of the University of São Paulo, Brazil, has been carried out. The proposal has many applications in biology and medicine. In this article, we propose a comparative study between two models that can be used by researchers for the analysis of survival data: (i) the Weibull regression model and (ii) the random survival forest (RSF) model. The models are compared considering the error rate, the performance of the model through the Harrell C-index, and the identification of the relevant variables for survival prediction. A statistical analysis of a data set from the Heart Institute of the University of São Paulo, Brazil, has been carried out. In the study, the length of stay of patients undergoing cardiac surgery, within the operating room, was used as the response variable. The obtained results show that the RSF model has less error rate for the training and testing data sets, at 23.55% and 20.31%, respectively, than the Weibull model, which has an error rate of 23.82%. Regarding the Harrell C-index, we obtain the values 0.76, 0.79, and 0.76, for the RSF and Weibull models, respectively. After the selection procedure, the Weibull model contains variables associated with the type of protocol and type of patient being statistically significant at 5%. The RSF model chooses age, type of patient, and type of protocol as relevant variables for prediction. We employ the randomForestSRC package of the R software to perform our data analysis and computational experiments. The proposal that we present has many applications in biology and medicine, which are discussed in the conclusions of this work. [ABSTRACT FROM AUTHOR]

We discuss a notion of convergence for binary trees that is based on subtree sizes. In analogy to recent developments in the theory of graphs, posets and permutations we investigate some general aspects of the topology, such as a characterization of the set of possible limits and its structure as a metric space. For random trees the subtree size topology arises in the context of algorithms for searching and sorting when applied to random input, resulting in a sequence of nested trees. For these we obtain a structural result based on a local version of exchangeability. This in turn leads to a central limit theorem, with possibly mixed asymptotic normality. [ABSTRACT FROM AUTHOR]

Let G be a simple graph with vertex set V(G) and edge set E(G). The atom-bond connectivity and Randić index of graph G are defined as and , respectively, where du denotes the degree of vertex u in G. Let ABC – R denotes the difference between ABC index and R index. In this paper, we present a further ordering for the ABC – R indices, and determine the fourth, the fifth, the sixth, the seventh and the eighth maximum binary trees with respect to the ABC – R values. [ABSTRACT FROM AUTHOR]

Bifurcating Markov chains (BMCs) are Markov chains indexed by a full binary tree representing the evolution of a trait along a population where each individual has two children. We provide a central limit theorem for additive functionals of BMCs under $L^2$ -ergodic conditions with three different regimes. This completes the pointwise approach developed in a previous work. As an application, we study the elementary case of a symmetric bifurcating autoregressive process, which justifies the nontrivial hypothesis considered on the kernel transition of the BMCs. We illustrate in this example the phase transition observed in the fluctuations. [ABSTRACT FROM AUTHOR]

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called “non-FIFO steams”. This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called $CPiX$ C P i X , for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner per checkpoint. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory. [ABSTRACT FROM AUTHOR]

Semantic network is a network of concepts connected by semantic relations. It contains two forms of binary semantic network and multiplex semantic network. The associated fact prediction is a link prediction task that aims to infer the implicitly connected facts by mining the high-level representation of the network. Previous methods for associated fact prediction put much emphasis on the topological feature of network but not utilize the information of semantic expression. This paper proposes a Semantic Network Encoder (SemNE), which learns a feature mapping function from the binary semantic networks and can be applied to the multiplex semantic networks in a pre-training manner. SemNE is a two-stage framework that contains an embedding encoder and a prediction decoder. It jointly models the semantic information and network topology to enrich the network representation. A word self-organization method based on the factual boundary is proposed to unify the topological feature and the semantic feature representations. Experimental results on binary semantic networks show that SemNE achieves the state-of-the-art results in associated fact prediction and experimental results on multiplex semantic networks show that SemNE is scalable and can effectively improve the performance of existing models. [ABSTRACT FROM AUTHOR]

We study compact straight-line embeddings of trees. We show that perfect binary trees can be embedded optimally: a tree with n nodes can be drawn on a n by n grid. We also show that testing whether a given rooted binary tree has an upward embedding with a given combinatorial embedding in a given grid is NP-hard. [ABSTRACT FROM AUTHOR]

We continue study of some algebraic varieties (called resultantal varieties) started in a paper of A. Grishkov, D. Logachev "Resultantal varieties related to zeroes of L-functions of Carlitz modules". These varieties are related with the Sylvester matrix for the resultant of two polynomials, from one side, and with the L-functions of twisted Carlitz modules, from another side. Surprisingly, these varieties are described in terms of finite weighted rooted binary trees. We give a (conjecturally) complete description of them, we find parametrizations of their irreducible components and their invariants: degrees, multiplicities, Jordan forms, Galois actions. Proof of the fact that this description is really complete is a subject of future research. Maybe a generalization of these results will give us a solution of the problem of boundedness of the analytic rank of twists of Carlitz modules. [ABSTRACT FROM AUTHOR]

In this article, a new method of option pricing in the form of fuzzy number is established based on fuzzy number binary tree model. Firstly,by using the operation rules of fuzzy number addition and number multiplication in cut set form, the fuzzy number binary tree model is equivalently transformed into two families of classical binary tree models which change with the level value, and some properties of the two binary tree model families are obtained, which are related to solve the problem of fuzzy option pricing. Then, based on the results obtained by us, the concepts of fuzzy set option price and fuzzy number option price are defined, and a sufficient condition is obtained for fuzzy set option price to be fuzzy number option price in the fuzzy number binary tree model. And then, for the convenience of practical application, the concepts of fold line fuzzy set and fuzzy number option price are introduced, a sufficient condition for fold line fuzzy set option price to be fold line fuzzy number option price is obtained, and a specific solution method of the fold line set and the fold line fuzzy number option pricing are set up. At last, two specific examples are given to show how to solve the fold line set and the fold line fuzzy number option price. [ABSTRACT FROM AUTHOR]

Cloud-based VANETs are designed to enable communication between high-speed vehicles. In such a highly dynamic environment, how to provide secure and anonymous communication service is a challenge. In this article, we affirmatively address the challenge by proposing a traitor-resistant and dynamic anonymous communication framework (TD-ACF) for cloud-based VANETs, which supports several advantageous features. In TD-ACF, each vehicle is represented by a set of attributes instead of its real identity, and the driving data is transmitted in encrypted form. Therefore, the anonymous authentication and the confidentiality of driving data are achieved in this way. Meanwhile, TD-ACF supports two practical requirements in cloud-based VANETs: the revocation and the traceability of traitor. For the former, TD-ACF can force a vehicle to exit the communication network at any moment. We employ an efficient binary tree algorithm to reduce the size of key updates for revocation from the traditional linear to the logarithmic level. For the latter, we overcome the barrier of the one-to-many relationship between a vehicle and the shared set of attributes to support traitor tracing. In TD-ACF, unlike most existing schemes, the Semi-Trusted Cloud (STC) can directly capture and punish a traitor instead of querying all the records in the list of unrevoked vehicles. In addition, we solve the key escrow problem that plagues most existing attribute-based schemes. The theoretical analysis and experimental simulation show that the proposed scheme is feasible and effective. [ABSTRACT FROM AUTHOR]

Most of the organizations using the cloud-based data sharing platforms are multi-group in nature. The existing directly revocable attribute-based encryption (ABE) schemes though seem to be a good fit, but they fail to provide any effective solution for secure multi-group data sharing scenarios. To bridge this gap, we first propose Revocable ABE with Verifiable Outsourced decryption (ReVO-ABE)- a directly revocable collusion-resistant ABE scheme that allows any number of user revocation and joining without affecting the secret membership keys of the nonrevoked users. Based on ReVO-ABE, we build a Dynamic Multi-Group Secure Data Sharing scheme called DMG-SDS. For operations that are exclusive to multi-groups like group merge and split can be performed without affecting the attribute secret keys or membership keys of the nonrevoked users, which is not possible with any of the existing schemes. Our proposed scheme meets the necessary security requirements, and the performance assessment shows that it has much better performance benefits when compared with most the recent competitive schemes. [ABSTRACT FROM AUTHOR]

We consider a class of non-convex complex modulus constrained problems (CMCPs), which has many important applications in signal processing for wireless communications, including multicast beamforming and multi-input multi-output detection. Due to the non-convex constraints, traditional optimization-based algorithms either obtain sub-optimal solutions or take exponential complexity to reach the optimum. In this paper, we propose a learning based branch-and-bound (LBB) algorithm for solving the considered CMCPs. LBB regards the search procedure of the global optimal argument-cut based branch-and-bound (AC-BB) algorithm as a sequential decision problem in a binary tree and learns the optimal pruning policy via supervised learning. We first propose to apply ensemble learning to train multiple classifiers and then combine them to achieve better performance. To tackle the imbalanced issue, we propose an undersampling-supervised learning method to sample several balanced subsets and train a classifier on each of them. We also show that the computational complexity of LBB is determined by the depth of the binary tree and give its expression in the worst case. Finally, we validate the proposed LBB with two classic problems in wireless communications, i.e., multicast beamforming and MIMO detection. Numerical results show that LBB runs significantly faster than AC-BB while achieving nearly the same optimal performance. [ABSTRACT FROM AUTHOR]

Diabetic retinopathy (DR) is a primary cause of blindness in which damage occurs to the retina due to an accretion of sugar levels in the blood. Therefore, prior detection, classification, and diagnosis of DR can prevent vision loss in diabetic patients. We proposed a novel and hybrid approach for prior DR detection and classification. We combined distinctive models to make the DR detection process robust or less error-prone while determining the classification based on the majority voting method. The proposed work follows preprocessing feature extraction and classification steps. The preprocessing step enhances abnormality presence as well as segmentation; the extraction step acquires merely relevant features; and the classification step uses classifiers such as support vector machine (SVM), K-nearest neighbor (KNN), and binary trees (BT). To accomplish this work, multiple severities of disease grading databases were used and achieved an accuracy of 98.06%, sensitivity of 83.67%, and 100% specificity.

Due to the flammability, explosiveness and toxicity of continuous objects (e.g., chemical gas, oil spill, radioactive waste) in the petrochemical and nuclear industries, boundary tracking of continuous objects is a critical issue for industrial wireless sensor networks (IWSNs). In this article, we propose a continuous object boundary tracking algorithm for IWSNs – which fully exploits the collective intelligence and machine learning capability within the sensor nodes. The proposed algorithm first determines an upper bound of the event region covered by the continuous objects. A binary tree-based partition is performed within the event region, obtaining a coarse-grained boundary area mapping. To study the irregularity of continuous objects in detail, the boundary tracking problem is then transformed into a binary classification problem; a hierarchical soft margin support vector machine training strategy is designed to address the binary classification problem in a distributed fashion. Simulation results demonstrate that the proposed algorithm shows a reduction in the number of nodes required for boundary tracking by at least 50 percent. Without additional fault-tolerant mechanisms, the proposed algorithm is inherently robust to false sensor readings, even for high ratios of faulty nodes ($\approx 9\%$ ≈ 9 % ). [ABSTRACT FROM AUTHOR]

For accommodating rapidly increasing power demands, power systems are transitioning from analog systems to systems with increasing digital control and communications. Although this modernization brings many far-reaching benefits, the hardware and software newly incorporated into the power systems also incur many vulnerabilities. By taking advantage of these vulnerabilities, adversaries can launch various cyber/physical attacks to tamper with electricity meter readings, i.e., to steal electricity. It is reported that total worldwide annual economic losses caused by electricity theft reached up to almost one hundred billion dollars in recent years. With methods to tamper with meter readings becoming more versatile, secret, and flexible, electricity theft tends to get even more serious in modernized power systems. For preventing adversaries from stealing electricity, researchers have done a lot of works. Although some related surveys on these works exist, they are not updated or just discuss electricity theft in a specific region. This survey aims to gain a comprehensive and in-depth understanding of the electricity theft issue. After investigating how adversaries tamper with meter readings, we systematically survey all existing detection methods up to date, which is classified into machine learning- and measurement mismatch-based methods. Adverse effects and political and socioeconomic factors of electricity theft are also provided. This survey can help relevant researchers to shape future research directions, especially in the area of developing new effective electricity theft detection methods. [ABSTRACT FROM AUTHOR]

Consider the computations at a node in a message passing algorithm. Assume that the node has incoming and outgoing messages $\mathbf {x} = (x_{1}, x_{2}, \ldots, x_{n})$ and $\mathbf {y} = (y_{1}, y_{2}, \ldots, y_{n})$ , respectively. In this paper, we investigate a class of structures that can be adopted by the node for computing $\mathbf {y}$ from $\mathbf {x}$ , where each $y_{j}, j = 1, 2, \ldots, n$ is computed via a binary tree with leaves $\mathbf {x}$ excluding $x_{j}$. We make three main contributions regarding this class of structures. First, we prove that the minimum complexity of such a structure is $3n - 6$ , and if a structure has such complexity, its minimum latency is $\delta + \lceil \log (n-2^{\delta }) \rceil $ with $\delta = \lfloor \log (n/2) \rfloor $ , where the logarithm always takes base two. Second, we prove that the minimum latency of such a structure is $\lceil \log (n-1) \rceil $ , and if a structure has such latency, its minimum complexity is $n \log (n-1)$ when $n-1$ is a power of two. Third, given $(n, \tau)$ with $\tau \geq \lceil \log (n-1) \rceil $ , we propose a construction for a structure which we conjecture to have the minimum complexity among structures with latencies at most $\tau $. Our construction method runs in $O(n^{3} \log ^{2}(n))$ time, and the obtained structure has complexity at most (generally much smaller than) $n \lceil \log (n) \rceil - 2$. [ABSTRACT FROM AUTHOR]

The main purpose of this article is to establish moderate deviation principles for additive functionals of bifurcating Markov chains. Bifurcating Markov chains are a class of processes which are indexed by a regular binary tree. They can be seen as the models which represent the evolution of a trait along a population where each individual has two offsprings. Unlike the previous results of Bitseki, Djellout & Guillin (2014), we consider here the case of functions which depend only on one variable. So, mainly inspired by the recent works of Bitseki & Delmas (2020) about the central limit theorem for general additive functionals of bifurcating Markov chains, we give here a moderate deviation principle for additive functionals of bifurcating Markov chains when the functions depend on one variable. This work is done under the uniform geometric ergodicity and the uniform ergodic property based on the second spectral gap assumptions. The proofs of our results are based on martingale decomposition recently developed by Bitseki & Delmas (2020) and on results of Dembo (1996), Djellout (2001) and Puhalski (1997). [ABSTRACT FROM AUTHOR]

In thisletter, we propose a new generic multispectral image demosaicking algorithm using adaptive spectral correlation. Our proposed algorithm defines the spectrally localized average image (SLAI) corresponding to each spectral band, which has a strong spectral correlation with the pixel values of the corresponding spectral band in the raw image captured using a single sensor. The proposed algorithm uses the SLAI to estimate the missing pixel values of the spectral bands. Experimental results reveal that our algorithm outperforms other state-of-the-art generic multispectral image demosaicking algorithms in terms of objective and subjective evaluations. [ABSTRACT FROM AUTHOR]

The ocean has been investigated for centuries across the world, and planning the travel path for vessels in the ocean has become a hot topic in recent decades as the increasing development of worldwide business trading. Planning such suitable paths is often based on big data processing in cybernetics, while not many investigations have been done. We attempt to find the optimal path for vessels in the ocean by proposing an online learning dispatch approach on studying the mission–executing–feedback (MEF) model. The proposed approach explores the ocean subdomain (OS) to achieve the largest average traveling feedback for different vessels. It balances the ocean path by a deep and wide search, and considers adaptation for these vessels. Further, we propose a contextual multiarmed bandit-based algorithm, which provides accurate exploration results with sublinear regret and significantly improves the learning speed. The experimental results show that the proposed MEF approach possesses 90% accuracy gain over random exploration and achieves about 25% accuracy improvement over other contextual bandit models on supporting big data online learning pre-eminently. [ABSTRACT FROM AUTHOR]

The object of research is indexing methods in non-relational databases. The article reviews the most common hashing algorithms and the proposed hashing algorithm based on prime numbers and binary number system. This work is based on the basic theorem of arithmetic, which states the possibility of factorizing any natural number with a unique set of prime numbers. This approach makes it possible to use a mathematical apparatus to justify the properties of the algorithm. The algorithms considered in the article are based on the execution of a sequence of bit operations and thus cannot be resistant to collisions. This characteristic is the most important for the use of extended hashing instead of a balanced binary tree when indexing in non-relational databases. This will not only increase the speed of queries, but also allow you to use the hardware as efficiently as possible. Since the main goal of the work is to adapt the combined algorithm for non-relational databases, to achieve this goal it is necessary to have a hash function that has high resistance to collisions. The proposed algorithm was implemented using a high-level programming language C ++, as it allows you to create abstractions with low "cost" and be able to work at a low level with information. In the context of work, the most useful option is to perform operations at the bit level. As a practical part, two experiments were performed to identify different input data sets that would yield the same hashes. The main idea of the experiments was to generate random data and obtain hashes using the proposed algorithm. The result of testing is the absence of such input data sets. The results of the experiment showed that it is advisable to continue to investigate the proposed algorithm using a mathematical apparatus to analyze its properties. Ref. 4, tabl. 1.

The definition of $\text {k}^{th}$ -order empirical entropy of strings is extended to node-labelled binary trees: A notion of $\text {k}^{th}$ -order empirical entropy for node-labelled binary trees is proposed that is able to capture regularities in both labels and structure of a tree. A suitable binary encoding of tree straight-line programs (that have been used for grammar-based tree compression before) is shown to yield binary tree encodings of size bounded by the $\text {k}^{th}$ -order empirical entropy plus some lower order terms. This result is then extended from node-labelled binary trees to node-labelled unranked trees. This generalizes recent results for grammar-based string compression to grammar-based tree compression. Additionally, experimental results with real XML document trees are presented, in which the proposed notion of $\text {k}^{th}$ -order empirical tree entropy is computed and compared to the performance of grammar-based tree compressors for those XML document trees. [ABSTRACT FROM AUTHOR]

We review the notion of a Dyck m -algebra , an algebraic structure introduced recently by López, Préville-Ratelle and Ronco during their work on the splitting of associativity via m -Dyck paths, and we also introduce Rota m -algebras: both structures can be considered as generalizations of dendriform structures. We obtain examples of Dyck m -algebras in terms of planar rooted binary trees equipped with a particular type of Rota–Baxter operator, and we present examples of Rotam-algebras using left averaging morphisms. As an application, we observe that the structures presented here allow us to introduce quite naturally a "non-associative version" of the Kadomtsev–Petviashvili hierarchy. [ABSTRACT FROM AUTHOR]

In this paper, we study arithmetic properties of weighted Catalan numbers. Previously, Postnikov and Sagan found conditions under which the 2-adic valuations of the weighted Catalan numbers are equal to the 2-adic valuations of the Catalan numbers. We obtain the same result under weaker conditions by considering a map from a class of functions to 2-adic integers. These methods are also extended to q -weighted Catalan numbers, strengthening a previous result by Konvalinka. Finally, we prove some results on the periodicity of weighted Catalan numbers modulo an integer and apply them to the specific case of the number of combinatorial types of Morse links. Many open questions are mentioned. [ABSTRACT FROM AUTHOR]

We study the kernel estimators of the transition density of bifurcating Markov chains. Under some ergodic and regularity properties, we prove that these estimators are consistent and asymptotically normal. Next, in the numerical studies, we propose two data-driven methods to choose the bandwidth parameters. These methods, based on the so-called two bandwidths approach, are adaptation for bifurcating Markov chains of the least squares Cross-Validation and the rule of thumb method. Finally, we provide an example with real data. [ABSTRACT FROM AUTHOR]

Recently, a new trend has emerged in the field of parallel and high performance computing, the hybrid implementation using CPU-GPU modules. In such implementations, the computational load is shared between the CPU and GPU, in order to improve the computational efficiency. However, the task of sharing the computational load between the two modules is a rather difficult one, with a number of limitations being imposed. This paper extends our recent work on community detection, which is based on transforming a network of nodes into a set of threaded binary trees. In this work, we share the computational load between the two units: the CPU takes specific samples of the network communities and organizes them in the form of threaded binary trees. The GPU takes over the heavy load of reading this data and transforming it into a path-matrix. Finally, this matrix is sent back to the CPU for analysis, community detection and overlaps, as well as network information upgrades. Our simulation results show significant improvement over our previous strategy and other known community detection strategies found in the literature.

In the 5G-envisioned Internet of vehicles (IoV), a significant volume of data is exchanged through networks between intelligent transport systems (ITS) and clouds or fogs. With the introduction of Software-Defined Networking (SDN), the problems mentioned above are resolved by high-speed flow-based processing of data in network systems. To classify flows of packets in the SDN network, high throughput packet classification systems are needed. Although software packet classifiers are cheaper and more flexible than hardware classifiers, they could only deliver limited performance. A key idea to resolve this problem is parallelizing packet classification on graphical processing units (GPUs). In this paper, we study parallel forms of Tuple Space Search and Pruned Tuple Space Search algorithms for the flow classification suitable for GPUs using CUDA (Compute Unified Device Architecture). The key idea behind the offered methodology is to transfer the stream of packets from host memory to the global memory of the CUDA device, then assigning each of them to a classifier thread. To evaluate the proposed method, the GPU-based versions of the algorithms were implemented on two different CUDA devices, and two different CPU-based implementations of the algorithms were used as references. Experimental results showed that GPU computing enhances the performance of Pruned Tuple Space Search remarkably more than Tuple Space Search. Moreover, results evinced the computational efficiency of the proposed method for parallelizing packet classification algorithms. [ABSTRACT FROM AUTHOR]

Arithmetic operations over binary extension fields $GF(2^{m})$ have many important applications in domains such as cryptography, code theory and digital signal processing. These applications must be fast, so low-delay implementations of arithmetic circuits are required. Among $GF(2^{m})$ arithmetic operations, field multiplication is considered the most important one. For hardware implementation of multiplication over binary finite fields, irreducible trinomials and pentanomials are normally used. In this brief, low-delay FPGA-based implementations of bit-parallel $GF(2^{m})$ polynomial basis multipliers are presented, where a new multiplier based on irreducible trinomials is given. Several post-place and route implementation results in Xilinx Artix-7 FPGA for different $GF(2^{m})$ finite fields are reported. Experimental results show that the proposed multiplier exhibits the best $delay$ , with a delay improvement of up to 4.7%, and the second best $Area\times Time$ complexities when compared with similar multipliers found in the literature. [ABSTRACT FROM AUTHOR]

Resonance demodulation is a commonly used method to obtain fault information, whose main challenge is to seek a suitable frequency band for demodulation. Autogram is a recently proposed method for optimal demodulation frequency band (ODFB) selection, in which the frequency domain is divided by a binary tree structure. However, the frequency band information obtained by Autogram is easily missed. To solve this issue, a 1/3 binary tree structure is employed to segment the frequency domain and improve the segmentation accuracy of Autogram. Despite this, the frequency bands with different position information cannot be fully obtained through the above-mentioned structure yet. In this article, the traverse symplectic correlation-gram (TSCgram) is proposed to overcome the shortcomings existing in Autogram and based on that, a novel fault diagnosis method for rolling bearing is proposed. First, the frequency domain of the raw vibration signal of rolling bearing is accurately divided through the traversal segmentation structure. Then, the concept of symplectic correlation is introduced to reduce the interference of noise, as well as other unrelated components on the traditional kurtosis, thus further improving the accuracy of ODFB detection. Finally, the band position corresponding to the maximum symplectic correlation kurtosis (SCK) value is chosen as the ODFB for fault diagnostics of rolling bearing. Also, the proposed method is applied to the simulated and measured data analysis by comparing it with fast kurtogram and Autogram methods. The comparison and analysis results indicate that the fault diagnostic effect of the proposed TSCgram method is better than the comparing methods. [ABSTRACT FROM AUTHOR]

This paper presents a new erasure code called Treeplication designed for distributed recovery of the full information word, while most prior work in coding for distributed storage only supports distributed repair of individual symbols. A Treeplication code for k information symbols is defined on a binary tree with 2k-1 vertices, along with a distribution for selecting code symbols from the tree layers. We analyze and optimize the code under a random-multiset model, which captures the system property that the nodes available for recovery are drawn randomly from the nodes storing the code symbols. Treeplication codes are shown to have full-recovery communication-cost comparable to replication, while offering much better recoverability. [ABSTRACT FROM AUTHOR]

Target detection aims to locate targets of interest within a specific scene. The traditional model-driven detectors based on signal processing have proved to be very effective. However, the detection performance of such traditional methods relies heavily on the model assumption, which is limited by the discrepancy with real hyperspectral images (HSIs) data. In this article, a target detection method through tree-structured encoding (TD-TSE) for HSIs is proposed. Instead of modeling the target and the background to extract valid features, we construct a binary tree based on the features of the data itself and segment the HSI to improve the separability of the target and the background. For the purpose of highlighting the target and suppressing the background, a novel measurement of separation, distance on tree, is calculated via binary encoding based on the constructed tree structure, and the detection output can be obtained according to such distance. To further reduce the generalization error resulting from random subsampling, the statistical average of the distances on multiple independent trees is estimated to improve the robustness of TD-TSE. The proposed method is not constrained by any model assumptions, which is fundamentally different from the most widely used hyperspectral target detectors in the field of signal processing. Moreover, the construction of binary trees without any labeled samples and the linear complexity of the proposed method make it highly practical for the hyperspectral data in real scenes. Extensive experiments on three benchmark HSI data sets demonstrate the effectiveness of the proposed TD-TSE for hyperspectral target detection. [ABSTRACT FROM AUTHOR]

It is challenging to extend the support region of state-of-the-art local edge-preserving filtering approaches to the entire input image on account of huge memory cost and heavy computational burden. In this paper, we propose an O(N) time recursive non-local edge-aware filter. A novel graph and a linear time algorithm are presented to effectively propagate information across the entire image. In this graph, information is propagated along all directions to avoid visual artifacts. Both the intensity similarity and the spatial affinity are utilized to estimate the similarity of neighboring pixels, and the distance of any two pixels is the length of the path between these two pixels on a binary tree. Specifically, the input image is filtered at four directions, namely left-to-right, right-to-left, top-to-bottom and bottom-to-top. In each pass, the un-normalized output and the normalization constant of the root node are computed recursively from leaf nodes to the root node on a binary tree in linear time. The filtering output is the average of the outputs for these four directions. A comparison with other non-local edge-aware filters is presented to show the advantages of our approach. Extensive experiments demonstrate that our recursive non-local edge-preserving filter is effective in a variety of computer vision and image processing applications, including edge-aware filtering, detail enhancement, stylization, and stereo matching. [ABSTRACT FROM AUTHOR]

Binary phylogenetic trees inferred from biological data are central to understanding the shared history among evolutionary units. However, inferring the placement of latent nodes in a tree is computationally expensive. State-of-the-art methods rely on carefully designed heuristics for tree search, using different data structures for easy manipulation (e.g., classes in object-oriented programming languages) and readable representation of trees (e.g., Newick-format strings). Here, we present Phylo2Vec, a parsimonious encoding for phylogenetic trees that serves as a unified approach for both manipulating and representing phylogenetic trees. Phylo2Vec maps any binary tree with n leaves to a unique integer vector of length n - 1. The advantages of Phylo2Vec are fourfold: i) fast tree sampling, (ii) compressed tree representation compared to a Newick string, iii) quick and unambiguous verification if two binary trees are identical topologically, and iv) systematic ability to traverse tree space in very large or small jumps. As a proof of concept, we use Phylo2Vec for maximum likelihood inference on five real-world datasets and show that a simple hill-climbing-based optimisation scheme can efficiently traverse the vastness of tree space from a random to an optimal tree., (© The Author(s) 2024. Published by Oxford University Press on behalf of the Society of Systematic Biologists.)

In this article, we introduce the BART R package which is an acronym for Bayesian additive regression trees. BART is a Bayesian nonparametric, machine learning, ensemble predictive modeling method for continuous, binary, categorical and time-to-event outcomes. Furthermore, BART is a tree-based, black-box method which fits the outcome to an arbitrary random function, f , of the covariates. The BART technique is relatively computationally efficient as compared to its competitors, but large sample sizes can be demanding. Therefore, the BART package includes efficient state-of-the-art implementations for continuous, binary, categorical and time-to-event outcomes that can take advantage of modern off-the-shelf hardware and software multi-threading technology. The BART package is written in C++ for both programmer and execution efficiency. The BART package takes advantage of multi-threading via forking as provided by the parallel package and OpenMP when available and supported by the platform. The ensemble of binary trees produced by a BART fit can be stored and re-used later via the R predict function. In addition to being an R package, the installed BART routines can be called directly from C++. The BART package provides the tools for your BART toolbox.