Explore the vast range of titles available.

To design an algorithm for detecting outliers over streaming data has become an important task in many common applications, arising in areas such as fraud detections, network analysis, environment monitoring and so forth. Due to the fact that real-time data may arrive in the form of streams rather than batches, properties such as concept drift, temporal context, transiency, and uncertainty need to be considered. In addition, data processing needs to be incremental with limited memory resource, and scalable. These facts create big challenges for existing outlier detection algorithms in terms of their accuracies when they are implemented in an incremental fashion, especially in the streaming environment. To address these problems, we first propose C_KDE_WR, which uses sliding window and kernel function to process the streaming data online, and reports its results demonstrating high throughput on handling real-time streaming data, implemented in a CUDA framework on Graphics Processing Unit (GPU). We also present another algorithm, C_LOF, based on a very popular and effective outlier detection algorithm called Local Outlier Factor (LOF) which unfortunately works only on batched data. Using a novel incremental approach that compensates the drawback of high complexity in LOF, we show how to implement it in a streaming context and to obtain results in a timely manner. Like C_KDE_WR, C_LOF also employs sliding-window and statistical-summary to help making decision based on the data in the current window. It also addresses all those challenges of streaming data as addressed in C_KDE_WR. In addition, we report the comparative evaluation on the accuracy of C_KDE_WR with the state-of-the-art SOD_GPU using Precision, Recall and F-score metrics. Furthermore, a t-test is also performed to demonstrate the significance of the improvement. We further report the testing results of C_LOF on different parameter settings and drew ROC and PR curve with their area under the curve (AUC) and Average Precision (AP) values calculated respectively. Experimental results show that C_LOF can overcome the masquerading problem, which often exists in outlier detection on streaming data. We provide complexity analysis and report experiment results on the accuracy of both C_KDE_WR and C_LOF algorithms in order to evaluate their effectiveness as well as their efficiencies.

Background Principal component analysis (PCA) is an essential method for analyzing single-cell RNA-seq (scRNA-seq) datasets, but for large-scale scRNA-seq datasets, computation time is long and consumes large amounts of memory. Results In this work, we review the existing fast and memory-efficient PCA algorithms and implementations and evaluate their practical application to large-scale scRNA-seq datasets. Our benchmark shows that some PCA algorithms based on Krylov subspace and randomized singular value decomposition are fast, memory-efficient, and more accurate than the other algorithms. Conclusion We develop a guideline to select an appropriate PCA implementation based on the differences in the computational environment of users and developers.

For minimizing a sum of finitely many proper, convex and lower semicontinuous functions over a nonempty closed convex set in an Euclidean space we propose a stochastic incremental mirror descent algorithm constructed by means of the Nesterov smoothing. Further, we modify the algorithm in order to minimize over a nonempty closed convex set in an Euclidean space a sum of finitely many proper, convex and lower semicontinuous functions composed with linear operators. Next, a stochastic incremental mirror descent Bregman-proximal scheme with Nesterov smoothing is proposed in order to minimize over a nonempty closed convex set in an Euclidean space a sum of finitely many proper, convex and lower semicontinuous functions and a prox-friendly proper, convex and lower semicontinuous function. Different to the previous contributions from the literature on mirror descent methods for minimizing sums of functions, we do not require these to be (Lipschitz) continuous or differentiable. Applications in Logistics, Tomography and Machine Learning modelled as optimization problems illustrate the theoretical achievements

Convex hull computation is a critical problem in computational geometry with a wide range of applications. Existing approaches focus on separate algorithms for calculating the convex hull of polygons and curvilinear polygons, leaving room for improvement in terms of efficiency and accuracy. To address these limitations, we propose the “Simulation of Progressively Supporting Elastic lines” (SPSEL) algorithm, which leverages the physical properties of elastic lines and their progressive support process. The SPSEL algorithm efficiently computes the convex hull of generic polygons that contain both straight and curved edges. This paper provides a comprehensive overview of the SPSEL algorithm, including its terminology, overall process, and specific methods used in key algorithmic steps. Comparative tests are conducted to assess its performance, and the experimental results demonstrate the superior performance of the SPSEL algorithm compared to the Johnstone’s algorithm, specifically designed for curved convex hulls. The SPSEL algorithm exhibits efficiency and effectiveness in handling various types of generic polygons, showcasing its potential for achieving linear-time operations. Furthermore, the paper discusses the possibilities of extending the SPSEL algorithm to address the computation of convex envelopes for 3D shapes, a challenging research area with theoretical and practical implications. Overall, the SPSEL algorithm offers an advanced solution for computing convex hulls of polygons with both straight and curved edges, demonstrating improved efficiency and accuracy compared to existing methods. These findings contribute to the field of computational geometry and have broad implications for applications requiring convex hull computation in diverse domains.

The incremental least-mean-square (ILMS) algorithm is a useful method to perform distributed adaptation and learning in Hamiltonian networks. To implement the ILMS algorithm, each node needs to receive the local estimate of the previous node on the cycle path to update its own local estimate. However, in some practical situations, perfect data exchange may not be possible among the nodes. In this paper, we develop a new version of ILMS algorithm, wherein in its adaptation step, only a random subset of the coordinates of update vector is available. We draw a comparison between the proposed coordinate-descent incremental LMS (CD-ILMS) algorithm and the ILMS algorithm in terms of convergence rate and computational complexity. Employing the energy conservation relation approach, we derive closed-form expressions to describe the learning curves in terms of excess mean-square-error (EMSE) and mean-square deviation (MSD). We show that, the CD-ILMS algorithm has the same steady-state error performance compared with the ILMS algorithm. However, the CD-ILMS algorithm has a faster convergence rate. Numerical examples are given to verify the efficiency of the CD-ILMS algorithm and the accuracy of theoretical analysis.

Incremental algorithms are among the most popular approaches for Delaunay triangulation, and the point insertion sequence has a substantial impact on the amount of work needed to construct Delaunay triangulations in incremental algorithm triangulation. In this paper, 2D adaptive Hilbert curve insertion, including the method of dividing 3D multi-grids and adjusting the 3D adaptive Hilbert curve to avoid the “jump” phenomenon, is extended to 3D Delaunay triangulation. In addition, on the basis of adaptive Hilbert curve insertion, we continue to optimize the addition of control points by selecting control points in every order and every grid level. As a result, the number of conflicting elongated tetrahedra that have to be created and deleted multiple times and the number of search steps for positioning inserted points can both be reduced. Lastly, a new comparison method is used in the point location process to solve the precision problem in 3D Delaunay triangulation. As shown by detailed experiments and analysis, compared with previous adaptive Hilbert curve insertion, CGAL, regular grid insertion, multi-grid insertion and random insertion, the proposed 3D Delaunay triangulation is the most efficient for both artificial and real surface sampling point sets.

This work proposes a variable step-size strategy for estimation over distributed networks using the incremental scheme. The proposed algorithm employs the ratio of filtered squared instantaneous error to the squared instantaneous error in a windowed format. This reduces the dependency on the error power which is particularly beneficial in low signal-to-noise power ratio situations. A comprehensive theoretical analysis has been performed, and closed-form solutions of mean squared error, excess mean squared error and mean squared deviation have been derived. The theoretical results are verified via simulation results. Extensive testing has been done through experiments under various scenarios to show the supremacy of the proposed algorithm in comparison with several other algorithms.

A significant part of highway and street congestion is produced by work zones. Depending on the type of construction and/or rehabilitation activity, street capacity could be significantly decreased, or the street could be completely closed. The work zone generates traffic delays in the street where maintenance is performed. Additionally, the work zone generates additional traffic on the neighboring streets, since many drivers change their routes. There are numerous possible work zone schedules. The total travel time of all network users highly depends on the chosen work zones schedule. Work zones scheduling problem has a natural nested structure that requires to be modeled as a bi-level problem. We considered the bi-level work zones scheduling problem. The objective function in the upper level, which we try to minimize, represents the total travel time of all network users. Relations in the lower level, help us to compute User Equilibrium flows. The proposed solution to the problem is based on the combination of Integer Programming and a heuristic traffic assignment algorithm. The output of the developed model consists of the start time of each work zone. The Sioux Falls benchmark network is used to illustrate the proposed procedures and the achieved performances.

The problem of real-time extraction of meaningful patterns from time-changing data streams is of increasing importance for the machine learning and data mining communities. Regression in time-changing data streams is a relatively unexplored topic, despite the apparent applications. This paper proposes an efficient and incremental stream mining algorithm which is able to learn regression and model trees from possibly unbounded, high-speed and time-changing data streams. The algorithm is evaluated extensively in a variety of settings involving artificial and real data. To the best of our knowledge there is no other general purpose algorithm for incremental learning regression/model trees able to perform explicit change detection and informed adaptation. The algorithm performs online and in real-time, observes each example only once at the speed of arrival, and maintains at any-time a ready-to-use model tree. The tree leaves contain linear models induced online from the examples assigned to them, a process with low complexity. The algorithm has mechanisms for drift detection and model adaptation, which enable it to maintain accurate and updated regression models at any time. The drift detection mechanism exploits the structure of the tree in the process of local change detection. As a response to local drift, the algorithm is able to update the tree structure only locally. This approach improves the any-time performance and greatly reduces the costs of adaptation.

We propose an analytical definition of discrete circles in the hexagonal grid. Our approach is based on a non-constant thickness function. We determine the thickness using the (edge and vertex) flake model. Both types of circles are connected. We prove that edge flake circles are without simple points for integer radii. Incremental generation algorithms are deduced from the analytical characterization of both edge and vertex flake circles. We compare our approach with existing algorithms for the circle generation on the hexagonal grid. Our approach offers simpler algorithm and an analytical characterization that the other algorithms do not offer. The benefit of an analytical characterization is that it makes the question of the membership of a point to a primitive trivial.