Search

Identification of when and where moving areas intersect is an important problem in maritime operations and air traffic control. This problem can become particularly complicated when considering large numbers of objects, and when taking into account the curvature of the earth. In this paper, we present an approach to conflict identification as a series of stages where the earlier stages are fast, but may result in a false detection of a conflict. These early stages are used to reduce the number of potential conflict pairs for the later stages, which are slower, but more precise. Our approach is generally applicable to objects moving in piece-wise straight lines on a 2D plane, and we present a specific case where the Mercator Projection is used to transform objects moving along rhumb lines on the earth into straight lines to fit in our approach. We present several examples to demonstrate our methods, as well as to quantify the empirical time complexity by using randomly generated areas.

Despite the fact that SimRank has been successfully applied to various applications as a link-based similarity measure, it suffers from a counter-intuitive property called a pairwise normalization problem ; JacSim is a powerful variant of SimRank that alleviates this problem. In this paper, we first point out three existing drawbacks of JacSim and then propose JacSim* to effectively solve them; JacSim* exploits those paths neglected by JacSim in similarity computation, its matrix form provides the exact similarity scores while not being sensitive to the number of node-pairs with common neighbors, and it has simpler, easier to understand, and easier to implement formulas in both iterative and matrix forms than those of JacSim. We conduct extensive experiments with eight real-world datasets to evaluate both the accuracy and performance of JacSim* in comparison with those of JacSim. Our experimental results demonstrate that JacSim* shows better accuracy than JacSim and the JacSim* matrix form is dramatically faster than its own iterative form and also than the two forms of JacSim with all datasets.

To protect image data privacy, a secure and fast image encryption algorithm using hyper-chaos based key generator and vector operation is proposed. Firstly, we introduce a novel post-process method to create a key matrix for significantly reducing the iterations of the hyperchaotic system from $W\,\,\times \,\,H$ /4 to $2W$ for an image size of $W\,\,\times \,\,H$ . And within the post-process, a random selector driven by the piecewise linear chaotic map ensures the good randomness and unpredictability of the generated key matrix. Secondly, the vector operation is employed to accelerate the cipher block chaining based diffusion process, so the plain image can be parallel encrypted row by row and column by column with high efficiency. Thirdly, we utilize a Logistic map to quickly produce an initial vector for the vectorized diffusion process. Finally, the proposed algorithm is evaluated by some common security and performance tests. Experimental results show that the cipher image can pass all tests of NIST SP 800–22 with $P$ -values $\gg ~0.01$ , its correlation coefficient between pixels is close to 0, and the entropy is greater than 7.999. Combined with other results of security tests, we can safely conclude that the proposed image encryption algorithm provides adequate protection against statistical, brute-force, chosen-plaintext, and other common types of attacks. In addition, the time complexity is in the order of ${O}$ ( $W+H$ ) and the average encryption time of 512 $\times $ 512 images is only 0.023s. The results indicate that our algorithm with high security and fast speed can meet the requirements of real-time confidential transmission of massive image data.

The maximal covering location problem attempts to locate a limited number of facilities in order to maximize the coverage over a set of demand nodes. This problem is NP-Hard and it has been often addressed by using metaheuristics, where the execution time directly depends on the number of evaluations of the objective function. In this article, the principles of efficient discarding and partial evaluation are applied to obtain more efficient versions of the objective function of this problem, i.e. not-approximate surrogate objective functions. An experimental study is presented to compare the surrogate functions in terms of number of distance comparisons and runtime. The results show that (on average) the best surrogate function is more than 5 times faster than the original function in general, and more than 8 times faster in the largest instances. This proposal allows for a more efficient metaheuristic solution based on swap operators.

In this paper, we propose deep learning–based energy beamforming in a multi-antennae wireless powered communication network (WPCN). We consider a WPCN where a hybrid access point (HAP) equipped with multiple antennae broadcasts an energy-bearing signal to wireless devices using energy beamforming. We investigate the joint optimization of the time allocation for wireless energy transfer (WET) and wireless information transfer (WIT) with the design for energy beams while minimizing the transmit power at the HAP for efficient use of its available resources. However, this is a non-convex problem, and it is numerically intractable to solve it. In the literature, the traditional approach to solving this problem is based on an iterative algorithm that incurs high computational and time complexity, which is not feasible for real-time applications. We study and analyze a deep neural network (DNN)-based scheme and propose a faster and more efficient approach for the fair approximation of a near-optimal solution to this problem. To train the proposed DNN, we acquire training data samples from a sequential parametric convex approximation (SPCA)-based iterative algorithm. Instead of acquiring data samples and training the DNN, which is highly complex, we use offline training for the DNN to provide a faster solution to the real-time resource allocation optimization problem. Through the simulation results, we show the proposed DNN scheme provides a fair approximation of the traditional SPCA method with low computational and time complexity.

In this paper, we propose a novel energy efficiency maximization scheme for social-aware device-to-device (D2D) communications based on a genetic algorithm (GA). The proposed scheme incorporates both social and physical parameters of users to model the energy efficiency maximization problem. The formulated problem considers the spectral reuse, spectral efficiency, and the transmit power constraints of both cellular and D2D users to satisfy their quality of service requirements. Moreover, an algorithm based on the self-adaptive penalty function is applied to convert the constrained problem into an unconstrained problem. Next, GA is utilized to maximize the unconstrained problem. The feasibility of the proposed scheme is shown by computing its time complexity in terms of big- $O$ notation. Moreover, the convergence of the proposed scheme is analyzed by comparing the maximum and average values of the overall energy efficiencies for different iterations. Likewise, the performance is evaluated in terms of overall energy efficiency and system throughput for various D2D communications scenarios. To demonstrate the efficiency of the proposed scheme, the results are compared with those for a static penalty-based GA algorithm. Furthermore, to demonstrate the significance of combining the two types of parameters (i.e., social and physical), the performance of the proposed scheme is compared with schemes based on only social or physical parameters.

Searchable encryption is an important cryptographic technique that achieves data security and keyword retrieval over encrypted data in cloud. In 2004, Boneh et.al proposed the first searchable encryption scheme based on asymmetric cryptography. Since then, many variants of public key searchable encryption schemes were proposed. However, most previous works are vulnerable to multi-ciphertext attack, and they cannot provide trapdoor indistinguishability. Another problem is how to improve the searching efficiency. To deal with two issues, we construct a fast and secure public key authenticated searchable encryption scheme with designed server. Our scheme can resist keyword guessing attacks, chosen multi-keyword attacks and multi-trapdoor attacks. The search function in our scheme achieves the logarithmic search time in number of keywords while most existing schemes required the linear time. By comparison with previous schemes in computational complexity, our scheme is very fast in keyword search.

The clustered shortest-path tree problem (CluSPTP) is an extension of the classical single-source shortest-path problem, in which, given a graph with the set of nodes partitioned into a predefined, mutually exclusive and exhaustive set of clusters, we are looking for a shortest-path spanning tree from a given source to all the other nodes of the graph, with the property that each cluster should induce a connected subtree. CluSPTP belongs to the class of generalized combinatorial optimization problems, and, in general, is proved to be a non-deterministic polynomial time hard (NP-hard) problem. In this paper, we propose a novel genetic algorithm (GA), which is designed to fit the challenges of the investigated problem. The main features of our GA are: the use of an innovative representation scheme that allows us to define meaningful genetic operators and the use of a hybrid initial population. Extensive computational results are reported and discussed for two sets of instances: euclidean and non-euclidean. The performance of the proposed algorithm was evaluated on six types of benchmark euclidean instances available in the literature and on six types of non-euclidean instances obtained from the corresponding euclidean ones. The obtained results show an improvement with respect to existing methods from the literature, both in terms of the quality of the achieved solutions and the computation times necessary to obtain them. They demonstrate that our genetic algorithm outperforms all the existing methods from the literature, providing for all the existing benchmark instances the optimal solutions in all 30 independent trials.

Computer and communication systems and networks deal with many cases that require rearrangement of data either in descending or ascending order. This operation is called sorting, and the purpose of an efficient sorting algorithm is to reduce the computational complexity and time taken to perform the comparison, swapping, and assignment operations. In this article, we propose an efficient mean-based sorting algorithm that sorts integer/non-integer data by making approximately the same length independent quasi-sorted subarrays. It gradually finds sorted data and checks if the elements are partially sorted or have similar values. The elapsed time, the number of divisions and swaps, and the difference between the locations of the sorted and unsorted data in different samples demonstrate the superiority of the proposed algorithm to the Merge, Quick, Heap, and conventional mean-based sorts for both integer and non-integer large data sets which are random or partially/entirely sorted. Numerical analyses indicate that the mean-based pivot is appropriate for making subarrays with approximately similar lengths. Also, the complexity study shows that the proposed mean-based sorting algorithm offers a memory complexity same as the Quick-sort and a time complexity better than the Merge, Heap, and Quick sorts in the best-case. It is similar to the Merge and Heap sorts in view of the time complexity of the worst-case much better than the Quick-sort while these algorithms experience identical complexity in the average-case. In addition to finding part by part incremental (or decremental) sorted data before reaching the end, it can be implemented by parallel processing the sections running at the same time faster than the other conventional algorithms due to having independent subarrays with similar lengths.

Age of information (AoI) captures the freshness of information and has been used broadly as an important performance metric in big data analytics in the Internet of Things (IoT). We consider a general scenario where a meaningful piece of information consists of multiple packets and the information is not complete until all related packets have been correctly received. Minimizing AoI in this general scenario is challenging in both scheduling algorithm design and theoretical analysis, because we need to track the history of received packets before a complete piece of information can be updated. We first analyse the necessary condition for optimal scheduling, based on which we present an optimal scheduling method. The optimal solution, however, has high time complexity. To address the problem, we investigate the problem with a special type of learning, i.e., learning in restless multi-armed bandits (RMAB), and propose a Whittle index-based scheduling method. We also propose a new transmission strategy based on erasure codes to improve the performance of scheduling policies in lossy networks. Performance evaluation results demonstrate that our solution outperforms other baseline policies such as greedy policy and naïve Whittle index policy in both lossless and lossy networks.

To date, quality-related multivariate statistical methods are extensively used in process monitoring and have achieved admirable effects. However, most of them contain recursive processes, which result in higher time complexity and are not suitable for increasingly complex industrial processes. Therefore, this paper embeds singular value decomposition (SVD) into the kernel principal component regression (KPCR) to accomplish Quality-related process monitoring with a lower computational cost. Specifically, the kernel technique is devoted to map the original input into the higher dimensional space to boost the nonlinear ability of the principal component regression (PCR), and then the KPCR is employed to capture the correlation between the input kernel matrix and the output matrix. At the same time, the kernelized input space is decomposed into two orthogonal quality-related and quality-unrelated spaces by SVD, and the statistics of the two spaces are calculated to detect the faults respectively. Compared with other multivariate statistical methods, it has the following advantages: 1) A quality-related kernel principal component analysis (QR-KPCR) algorithm is proposed. 2) Compared with partial least squares method, the recursive process is omitted and the training time is shortened. 3) The model is more concise and the fault detection process is faster. 4) By contrast with other multivariate statistical process monitoring, it has a higher fault detection rate. Experimental results on a widespread example and an industry benchmark verify the effectiveness and reliability of the proposed method.

Reliability is one of the major concerns of Time Sensitive Networking (TSN). Current systems mostly rely on static redundancy to protect functionality from permanent component failures. This greatly increases the cost of Time-Triggered (TT) flows. Instead, Software Defined Networking (SDN) enables dynamic redundancy. Disrupted traffic can be rerouted by a centralized controller to reduce the cost while maintaining reliability. This paper presents an approach to compute alternative paths at run-time and analyze their impact on reliability. We define a novel three-mode recovery scheme, which includes full functionality, reduced functionality, and emergency halt modes. Run-time recovery for TT flows is explored using Integer Linear Programming (ILP) and a heuristic algorithm. Then, a Markov chain-based design-time reliability analysis is developed to evaluate the Mean Time to Reduced Functionality Mode (MTTRF) and Mean Time to Failure (MTTF) of run-time recoverable systems. Our experiments show that run-time recovery provides better protection against multi-point failures than static redundancy. Compared with the state of the art, our proposed ILP has better routing efficiency. The proposed heuristic algorithm can perform routing and scheduling in polynomial time, but it tends to route multicast flows to longer paths than ILP. Furthermore, when applied to realistic recovery scenarios, our proposed ILP improves the MTTF by up to $2\times $ and the average execution time by up to $20\times $ than the raw ILP of the state of the art. Although less efficient with multicast flows, the heuristic algorithm achieves similar reliability as the ILP, and its worst-case recovery time is below $100ms$ on an embedded ARM processor.

Automatic lane detection is a classical task in autonomous vehicles that traditional computer vision techniques can perform. However, such techniques lack reliability for achieving high accuracy while maintaining adequate time complexity in the context of real-time detection in complex and dynamic road scenes. Deep neural networks have proved their ability to achieve competing accuracy and time complexity while training them on manually labeled data. Yet, the unavailability of segmentation masks for host lanes in harsh road environments hinders fully supervised methods’ operability on such a problem. This work proposes integrating traditional computer vision techniques and deep learning methods to develop a reliable benchmarking framework for lane detection tasks in complex and dynamic road scenes. Firstly, an automatic segmentation algorithm based on a sequence of traditional computer vision techniques has been experimented. This algorithm precisely segments the semantic region of the host lane in the complex urban images of nuScenes dataset used in this framework; hence corresponding weak labels are generated. After that, the developed data is qualitatively evaluated to be used in training and benchmarking five state-of-the-art FCN-based architectures: SegNet, Modified SegNet, U-Net, ResUNet, and ResUNet++. The performance evaluation of the trained models is done visually and quantitatively by considering lane detection a binary semantic segmentation task. The output results show robust performance, especially ResUNet++, which outperforms all the other models while testing them in different complex road scenes with dynamic scenarios and various lighting conditions.

The maximum information coefficient (MIC) is a novel and widely-using measure of association detection in large datasets. The most outstanding feature of MIC is that it has both generality and equability. However, MIC can only deal with two variables and cannot precisely estimate coupling associations of multiple variables. In this paper, we propose an extension of MIC to deal with multi-variable datasets, called the multi-variable maximum information coefficient (MMIC). Some inherited and novel properties of MMIC are proved, including generality, equability, monotonicity, and subadditivity. We design an algorithm based on greedy stepwise strategy and upper confidence bound (UCB) for an approximate calculation of MMIC. The tests of MMIC on generated datasets and examples on real datasets are carried out to detect known and novel associations.

The edge cloud provides heterogeneous resources, such as cores, memory, and storage which are then allocated to mobile applications in mobile edge computing, which require multiple types of resources to execute. While current work on mobile edge computing focuses on tasks needing a single resource to run, we investigate the task allocation problem aiming to minimize total energy consumption while considering heterogeneous resource settings. Specifically, we consider the binary computation offloading mode, in which a task executes successfully as a whole. We formulate this as an integer programming problem, and transform that to the two subproblems of the resource allocation and the offloading decision. We propose a heuristic approach to solve the resource allocation subproblem and an approximation algorithm for the offloading decision subproblem. We show that our proposed approximation algorithm is a polynomial time approximation scheme, and hence it achieves a tradeoff between optimality loss and time complexity. Experimental results demonstrate that the performance of our proposed algorithm scales very well for multi-resource allocation in different conditions, and it achieves a good balance of performance and speed.

As a solution to mitigate the key exposure problems in the digital signature, the forward security has been proposed. The forward security guarantees the integrity of the messages generated in the past despite leaks of a current time period secret key by evolving a secret key on each time period. In this paper, we propose a new forward secure aggregate signature scheme utilizing recursive zk-SNARKs (zero knowledge Succinct Non-interactive ARguments of Knowledge). Our proposal has constant complexities in key/signature sizes, signature generation, and verification time. The proposed forward secure signature scheme can aggregate signatures generated by multiple users as well as a single user. The security of the proposed scheme is formally proven under zero-knowledge assumption and random oracle model. The experiment results show that our signature scheme yields 12 s for signing time, 1 ms for verification time, 25 s for aggregation time, with the 1.6 KB secret key size and signature size independent of the number of time periods.

Measuring the space area of obstacles is one of the important problems in obstacle localizing fields. Most of the existing research works on the localization of obstacles focus on where the obstacles are, and few of them measure both the positions and the areas of the obstacles. In this paper, we propose a Minimum convex bounding Polygon localizing algorithm based on Visible light Tracking (MPVT) in order to rapidly and accurately locate the position and area of a 2D obstacle in the environment of sparsely-deployed sensors. MPVT first determines the initial localization light by Visible Light Tracing method (VLT). Second, it searches for the first side of the Minimum Convex Bounding Polygon (MCBP) of the obstacle. Third, MPVT calculates the subsequent other sides and the vertexes of MCBP until the next side coincides with the first side. In order to evaluate the approximation degree between the actual values and the localization values in terms of areas, positions and shapes, we propose two performance evaluation indexes, i.e., the area ratio and the ratio of equivalent radius. We conducted experiments on the influence of obstacle orientation and sparseness of sensor deployment, the accuracy comparison with the existing methods, and the time complexity. Experiment results show that MPVT can accurately locate the position and area of the obstacle in the environment of sparsely-deployed sensors with low time overhead, and is suitable for low-cost obstacle localization applications.

Ambient Occlusion (AO) is a widely used shadowing technique in 3D rendering. One of the main disadvantages of using it is that it requires not only the surface depth but also the normal vector, which usually causes severe aliasing. This work introduces a novel AO algorithm by applying Chebyshev’s inequality. Instead of requiring the normal vector, we process the mean ( $\mu $ ) of the distribution of depth values from the screen space. We can efficiently calculate the variance ( $\sigma ^{2}$ ) over any kernel region. Using the Chebyshev AO, we can get the upper bound on the percentage of the shaded surface that is occluded. Our proposed method can usually provide a good approximation of true occlusion and can be used as an approximate value for AO rendering. As a post-processing rending, the time complexity of Chebyshev AO is $O\left ({2k}\right)$ which is simple to implement on current graphics devices and can be applied to the next generation of ray tracing technology.

Network representation learning can map complex network to the low dimensional vector space, capture the topological properties of networks, and reduce the time complexity and space complexity of the algorithm. However, most of the existing network representation learning (NRL) methods are for the homogeneous networks, while the real-world networks are usually heterogeneous, therefore, it is more practical to provide an intelligent insight into the evolution of heterogeneous networks. In this paper, we propose a novel heterogeneous network embedding method, called AttrHIN, which adopts weighted meta-path-based random walks strategy, and can make full use of the attribute information to capture the latent features. AttrHIN is suitable for the different types of nodes in heterogeneous networks. Extensive experimental results show that compared with the state-of-art algorithms, AttrHIN achieves better results in Macro-F1 and Micro-F1 for multi-class node classification and Link Prediction on several real-world datasets.

Efficient, robust and precise algorithms for linear quadratic regulator (LQR) and matrix differential Riccati equation (MDRE) are essential in optimal control. However, there are lack of good algorithms for time-varying LQR problem because of the difficulty of solving the nonlinear time-varying MDRE. In this paper, we proved that the $n$ -th order LQR problem is equivalent to $n$ parallel 1-dim Hamiltonian systems and proposed the explicit symplectic-precise iteration method (SPIM) for solving LQR and MDRE. The explicit symplectic-precise iteration algorithms (ESPIA) designed with SPIM have three typical merits: firstly, there are no accumulative errors in the sense of long-term time which inherits from symplectic difference scheme; secondly the stiffness problem due to the inverse of matrix is avoided by the precise iteration method; and finally the algorithmic structure of ESPIA is simple and no extra assumptions are required. Systematic analysis shows that the time complexity of the symplectic algorithms for the $n$ -th order LQR and MDRE is $\mathcal {O}(k_{max}n^{3})$ where $k_{max}$ is the iteration times specified by the time duration. Numerical examples and simulations are provided to validate the performance of the ESPIA.

Given a directed graph and a node $v$ , the transitive closure (TC) of $v$ is the set of nodes that $v$ can reach in the graph. TC size is very important in many applications but the cost of TC size computation is high in both time and space, which makes computing accurate TC size not applicable to the scenario where we need to know the TC size quickly for large graphs. Considering that existing approaches are either inefficient or inaccurate, we propose an algorithm, namely buTCS, to efficiently make more accurate estimation. Our approach works in linear time and space. The basic idea is to compute a node’s TC size based on that of its out-neighbors and perform a top-down verification. We further propose two optimizations to improve the estimation accuracy. The experimental results on 13 real datasets show that buTCS achieves better estimation on TC size efficiently.

Currently, the recommendation method on tourist sight and tour route lacks of the mechanism of tourists' interests mining and the precise tourist sights recommending, and the planned tour routes cannot properly and adequately combine with the real world environment. Meanwhile, the research on the multivariate transportation modes in tour route recommendation is not sufficient. Aim at the problems of the tourist sight and tour route recommendation in intelligent tourism recommendation system of the intelligent tourism construction, this paper brings forward a tourism recommendation algorithm based on text mining and MP nerve cell model of multivariate transportation modes. The research specially focuses on the optimal tourist sight matching algorithm based on tourists' interests mining and the optimal tour route chain algorithm based on the multivariate transportation modes. First, it analyzes the problems on tourism recommendation, based on which, the tourist sight clustering algorithm on feature attribute label and the tourist sight text mining algorithm on interest label are developed. The mined tourist sights will approach tourists' interests to the maximum extent. Secondly, Considering the critical impact of the selected transportation mode on motive benefit satisfaction in the tour route chain, the tour route chain algorithm based on the nerve cell model of multivariate transportation modes is developed. This algorithm combines with geographic information element and transportation element, and it simulates the bionic principle of input and output information process on MP nerve cell, then the tour route chain model based on the nerve cell of multivariate transportation modes is set up. Through the iteration of multiple layer nerve cell motive weight values and accommodation coefficients, the algorithm finally outputs the signal information flow motive values, in which the tour route chain with the maximum information flow motive value is generated. Thirdly, to testify the feasibility and practicalness of the algorithm, an experimental example in real-world environment is designed and performed. The feasible matched tourist sights and tour route chains are output, meanwhile, the three commonly used optimal route searching algorithms are set as the control group, and along with the developed algorithm, they are compared with each other on the aspect of optimal tour route chain. The experiment testifies that the developed algorithm is feasible and practical, and has advantages on the tourism recommendation. Through the algorithm design and the experiment, it finds that the mined tourist sights by the objective function in the algorithm can best match tourists' interest labels. The algorithm adequately combines with the real world tourism data of the geographic information, traffic information and tourist sight information and outputs the tour routes that best match tourists' interests. Compare with the control group algorithms, the tour routes output by the developed algorithm have the highest motive satisfaction, lowest time complexity and space complexity. The developed algorithm is mainly used as the embedded algorithm for the intelligent tourism recommendation system, whose direct aim is to provide service for the tourists. Meanwhile, it can also provide service for the tourism administrations to collect, manage and mine the interest data as well as discover knowledge, and help the government to optimize the urban transportation system, launch the public vehicles and optimize the transportation guarantee strategy.

Reinforcement Learning is at the core of a recent revolution in Arti cial Intelligence. Simultaneously, we are witnessing the emergence of a new eld: Quantum Machine Learning. In the context of these two major developments, this work addresses the interplay between Quantum Computing and Reinforcement Learning. Learning by interaction is possible in the quantum setting using the concept of oraculization of environments. The paper extends previous oracular instances to address more general stochastic environments. In this setting, we developed a novel quantum algorithm for near-optimal decision-making based on the Reinforcement Learning paradigm known as Sparse Sampling. The proposed algorithm exhibits a quadratic speedup compared to its classical counterpart. To the best of the authors' knowledge, this is the first quantum planning algorithm exhibiting a time complexity independent of the number of states of the environment, which makes it suitable for large state space environments, where planning is otherwise intractable., This work is financed by National Funds through the Portuguese funding agency, FCT - Fundação para a Ciência e a Tecnologia, within project UIDB/50014/2020.

Fault diagnosis for a multiprocessor system is a process of identifying the faulty nodes in the system and is an important issue on the reliability of the system. As to the problem that there are few effective algorithms to diagnose faulty nodes in a given star network system in the literature, this paper proposes a precise fault diagnosis algorithm to identify faulty nodes in a star network system with a given syndrome under the comparison model. Such an algorithm contains three main parts. In the first part, we present an algorithm called Partition-Cycle for partitioning a cycle into sequences based on a given syndrome of the cycle. In the second part, we introduce an algorithm called Digout to diagnose these cycle sequences obtained the first part, which can diagnose each node in the cycle to be faulty or fault-free or unknown. In the third part, we design a diagnosis algorithm called Star-Digout to diagnose faulty nodes in an $n$ -dimensional ( $n\geqslant 6$ ) star networks, which is proved to contain a cycle that contains all nodes in the network and is not the same two nodes. Our theoretical analysis shows the time complexity of the diagnosis algorithm is $O(n!)$ . Our simulation results show that our algorithm is a precise diagnosis algorithm for a star network system.

The Shell sort algorithm is one of the most practically effective in-place sorting algorithms. However, it is difficult to execute this algorithm with its intended running time complexity on data encrypted using fully homomorphic encryption (FHE), because the insertion sort in Shell sort has to be performed by considering the worst-case input data. In this paper, in order for the sorting algorithm to be used on the FHE data, we modify the Shell sort with an additional parameter $\alpha $ , allowing exponentially small sorting failure probability. For a gap sequence of powers of two, the modified Shell sort with input array length $n$ is found to have the trade-off between the running time complexity of $O(n^{3/2}\sqrt {\alpha +\log \log n})$ and the sorting failure probability of $2^{-\alpha }$ . Its running time complexity is close to the intended running time complexity of $O(n^{3/2})$ and the sorting failure probability can be made very low with slightly increased running time. Further, the near-optimal window length of the modified Shell sort is also derived via convex optimization. The proposed analysis of the modified Shell sort is numerically confirmed by using randomly generated arrays. For the practical aspect, our modification can be applied to any gap sequence, and we show that Ciura’s gap sequence, which is known to have good practical performance, is also practically effective when our modified Shell sort is applied. We compare our modified Shell sort with other sorting algorithms with the FHE over the torus (TFHE) library, and it is shown that this modified Shell sort has the best performance in running time among in-place sorting algorithms on homomorphic encryption scheme.

Due to the large number of typical applications, it is very important and urgent to study the fast classification learning of accumulated big data in nonstationary environments. The newly proposed algorithm, named Learn++.NSE, is one of the important research results in this research field. And a pruning version, named Learn++.NSE-Error-based, was given for accumulated big data to improve the learning efficiency. However, the studies have found that the Learn++.NSE-Error-based algorithm often encounters a situation that the newly generated base classifier is pruned in the next integration, which reduces the accuracy of the ensemble classifier. The newly generated base classifier is very important in the next ensemble learning and should be retained. Therefore, the two latest base classifiers are reserved without being pruned, and a new pruning algorithm named NewLearn++.NSE-Error-based was proposed. The experimental results on the generated dataset and the real-world dataset show that NewLearn++.NSE-Error-based can further improve the accuracy of the ensemble classifier under the premise of obtaining the same time complexity as Learn++.NSE algorithm. It is suitable for fast classification learning of long-term accumulated big data.

The number of malware has steadily increased as malware spread and evasion techniques have advanced. Machine learning has contributed to making malware analysis more efficient by detecting various behavioral and evasion patterns. However, when analyzing large-scale malware datasets, malware analysis through learning models has both high temporal and spatial complexity. In order to address these problems, this work proposes a low-dimensional feature using histogram entropy and a prototype selection algorithm using hyperrectangles. The low-dimensional feature forms an $L \times 256$ map according to the preselected parameter $L$ . The prototype selection algorithm divides the input space into overlapping subspaces where each subspace is decided by its hyperrectangle that becomes a prototype in the same class. A set cover optimization algorithm is employed to select a small number of prototypes that construct a new training dataset. A set of prototypes selected by the prototype selection algorithm is used to classify malware families. The experiment compares the performance of machine learning models for the histogram entropy feature using both the BIG 2015 dataset and the collected dataset. The integrated approach is evaluated using learning algorithms, such as Decision Tree, Random Forest, XGBoost, and CNN. The experimental results indicate that learning models perform competitively when compared to the entire dataset, while the proposed selection approach benefits from smaller datasets and lower time complexity.

Binary sequences are widely used in many practical fields, such as radar applications, telecommunications and cryptography. Finding low autocorrelation binary sequences with good peak side-lobe level (PSL) values is a difficult optimization problem. In this paper we present an improved heuristic algorithm for searching low autocorrelation PSL sequences. A heuristic algorithm can find a sequence with a PSL value, which is not necessarily optimal, but is usually near optimal, and the algorithm finds it in a reasonable amount of time. In the experimental work we applied our algorithm to find binary sequences with low PSL values, and made a comparison with the state-of-the-art algorithms from literature. With our algorithm many sequences with the currently best-known PSL values have been improved. We found new sequences with better, i.e., lower, PSL values.

Finite fields are well-studied algebraic structures with enormous efficient properties which have applications in the fields of cryptology and coding theory. In this study, we proposed a lossless binary Galois field extension-based efficient algorithm for digital audio encryption. The proposed architecture hired a special type of curve in the diffusion module which depends on efficient elliptic curve arithmetic operations. So, it generates good quality pseudo-random numbers (PRN) and with slight computational efforts, it produces optimum diffusion in the encrypted audio files. For the confusion module, a novel construction mechanism of block cipher has been employed which includes prominent arithmetic operations of binary Galois field inversion and multiplication operations. The suggested scheme generates multiple substitution boxes (S-boxes) by using a higher-order Galois field. Thus, the replacement with multiple S-boxes generates effective perplexity in the data and provides additional security to the ciphered audio. The investigational outcomes through different analyses and time complexity demonstrated the ability of the technique to counter various attacks. Furthermore, as a consequence of a rapid and simple application of the binary finite field in hardware and software, the proposed scheme is more appropriate to be applied for data security. 10.13039/501100007446-Deanship of Scientific Research at King Khalid University through the Research Groups Program (Grant Number: RG.P. 2/150/42)

There are a few dependent multivariate relationships among high dimensional data sets. Then how to identify these dependent variables from high dimensional data sets is an important issue for data analysis. Now, the most frequently used method is the enumeration method, that is all multivariate relationships in the high dimensional data sets are examined. However, the time complexity of the enumeration method is exponential ( $2^{n}$ ) and the calculation load is very heavy when the dimension is high. Aiming at solving this problem, the matrix iteration algorithm with pruning (MIP) is proposed for pinpointing multivariate dependent relationships in high dimensional data sets without examining all multivariate relationships. Some not dependent relationships are ignored without examined by the pruning process of the proposed MIP and the computing burden is reduced. The maximal information coefficient (MIC) is adopted as the measure of correlations in the proposed MIP algorithm due to the excellent properties, generality and equitability, of MIC. In the case of the data set with 5 variables, more than 50% multivariate relationships are pruned without examining. Numerical experiments also show that the calculating burden is greatly reduced. Compared to the enumeration method, 82.5% calculating time and 98.5% calculating times of multivariate relationships are saved for the data set with two dependent multivariate relationships among 30 variables in the experiment. The proposed MIP algorithm is effective for pinpointing multivariate dependent relationships from data sets with high dimensions.

Network representation learning aims to map nodes in the network into low-dimensional dense vectors, which can be widely used to solve the network analysis tasks. Existing methods mainly focus on single-layer homogeneous networks. However, many real-world networks consist of multiple types of nodes and edges, which are called multilayer networks. The problem of how to capture node information and use multi-type relational information is a major challenge of multilayer network representation learning. To address this problem, we propose a method of random walk of multiple information, called IFMNE, to efficiently preserve and learn node information and multi-type relational information into a unified space. This method combines node structure information with network topology information to obtain the node random walk sequence, and trains the node walk sequence on the neural network model. Experimental results are performed on five real multilayer networks, and the embedding vectors were evaluated by link prediction task. The accuracy was significantly improved on the basis of low time complexity compared with the baseline methods.

Screen Content (SC) videos require proper tools to handle their special characteristics since they include repeated regions, sharp edges, and limited number of colors. Therefore, SC extension to High Efficiency Video Coding (HEVC) standard has been released for this purpose. SC extension has new tools such as Intra Block Copy (IBC) and Palette (PLT) mode. These tools improve the coding efficiency, but they come with a huge computation complexity. In this paper, we propose a scheme to reduce the encoding time of SC encoder. It has two algorithms based on the Decision Rule (DR) machine learning technique. The first algorithm, which is called Mode Skipping (MS), is used to skip the unnecessary SC mode checking. Early Pruning Termination (EPT), which is the second algorithm, is used to stop the partitioning process early. A small number of features has to be calculated for the trained models. The proposed scheme was implemented then simulated by using the standard software test model SCM-6. The experimental results show that the time complexity is reduced by 37.84% on average while the Bjøntegaard delta bit-rate (BD-R) increases by 1.34% only.

Along with the development of big data, knowledge updating occurs in various situations, some scholars had studied the dynamic method of updating knowledge in multigranulation decision-theoretic rough sets when adding or deleting granular structures. However, there is no study about the case of adding or deleting objects, which limits the development of multigranulation decision-theoretic rough sets. Based on the matrix method, the dynamic knowledge updating of optimistic multigranulation decision-theoretic rough set and pessimistic multigranulation decision-theoretic rough set were studied in this paper, then given the static algorithm and dynamic algorithms, and the time complexity of three algorithms was analyzed. The theory and experimental results show that two dynamic algorithms are both more effective than the static algorithm.

This paper presents a novel solution for detecting rare and mutating malware programs and provides a strategy to address the scarcity of datasets for modeling these types of malware. To provide sufficient training data for malware behavioral modeling, genetic algorithms are used together with an optimization strategy that selectively creates generations of mutated elite malware samples. In our unique method, a sequence of system API calls is extracted using tracker filter drivers in a sandbox environment. The most obfuscated and metamorphic malware are chosen by an elite selection method. The behavioral chromosomes are formed by mapping extracted APIs to genes using linear regression. Our analysis system includes an Internet simulator and a human emulator to deceive intelligent classes of malware to successfully execute themselves and prevent system halting. The evolution process is performed through crossover and permutation of genes, which are encoded based on the addresses of the kernel-level system functions. An objective function has been defined to optimize the vital indicators of malignancy and tracking rate with a linear time complexity. This guarantees that new generations of malware are more destructive and stealthy than their parents. J48 and deep neural networks were employed in our experiments as they are two popular modeling and classification strategies in the area of behavioral malware detection. Real-world malware samples from valid references were used for the performance evaluation of our approach. Comprehensive scenarios were involved in the experiments to evaluate the performance of our proposed strategy. The results demonstrate significant improvement in detection accuracy - up to 5% considering rare and metamorphic malware. The results also demonstrated a considerable enhancement in true positive rate for the proposed deep-learning algorithm.

The goal of trajectory planning is to shorten the flight distance as much as possible on the premise of ensuring the safety of UAV in flight. Therefore, the research of trajectory planning has broad prospects and great significance. As the key technology of trajectory planning, optimization algorithm has increasingly become one of the focuses of scholars at home and abroad. The dynamic programming algorithm is characterized by high computational efficiency and global optimization in trajectory planning. In 3D trajectory planning, as the spatial search space expands, the number of grid points increases faster, and time complexity of the dynamic programming algorithm is ${O}({n}^{3}) $ . It often leads to a “Curse of Dimension” phenomenon, which lowers its computational efficiency drastically. To solve this problem, this paper divides the entire planning space into stages based on Bellman’s optimality principle. A dynamic programming-genetic algorithm(DPGA) is proposed by using genetic algorithm(GA) in each stage for optimization, while using dynamic programming algorithm(DP) in global planning. The global optimization ability of the algorithm is verified through convergence analysis. Moreover, based on a series of simulation experiments, it shows that the improved algorithm proposed in this paper is more efficient than the dynamic programming algorithm and genetic algorithm alone in global optimization.

Localization problem is a hot topic in the field of wireless sensor networks. The distance vector-hop (DV-Hop) is a typical range-free localization algorithm which is widely used in many applications owing to its advantages such as simplicity, feasibility, low cost, and less hardware requirements. However, its localization error is relatively large. In this article, a novel approach designated as CWDV-Hop was presented to improve the localization accuracy. In the first step of CWDV-Hop, the distance-weighted hop distance was calculated by introducing the new defined distance-weighted factor and single-node hop distance, which can effectively reduce the impact of curved path on the estimation of average hop distance. Furthermore, the locations of unknown nodes are obtained by utilizing two-dimensional hyperbolic scheme. At last, Chicken Swarm Optimization (CSO), which is a kind of nature inspired algorithm, is introduced to optimize the locations of unknown nodes. In comparison with the traditional DV-Hop approach, the localization accuracy of CWDV-Hop can be raised by 53.6%, 39.5% and 53.1% for the square, $X$ -shaped and $O$ -shaped random distribution environment respectively, with the time complexity slightly gained. It demonstrates the effectiveness of CWDV-Hop not only in the isotropy network, but also in the anisotropy network with holes or other uneven distributions.

Community detection can not only help people understand organizational structure and function of complex networks, but also attributes to many potential applications including targeted advertising and customer relationship management. Due to the low time complexity, the label propagation algorithm is widely used, but there is still room to improve the community quality and the detection stability. Inspired by resource allocation and local path similarity, we first give a new two-level neighbourhood similarity measure called TNS, and on this basis we propose an improved label propagation algorithm for community detection. In this new algorithm, the minimum distance and local centrality index are considered to select the initial community centers, to ensure that they are both important and far away from each other. In the process of forming initial community, we employ the new similarity measure and an optimization strategy of asynchronously updating labels according to node importance. To further improve the accuracy of community division, we introduce the label influence based on the new similarity measure to further optimize the community division of networks. The experimental results on both the artificial network and ten real-world networks show that our proposed algorithm has better comprehensive performance than several existing algorithms in terms of modularity, normalized mutual information and adjusted rand index.

Correlation Power Analysis (CPA) uses a lot of computational resources for deploying side-channel analysis to power traces. For every guessing key, it searches all data points and all power traces to reveal the secret key implemented in the encryption module. In this work, we propose a novel technique to narrow down the target region for applying CPA to the power traces. As byte-wise operations occur in every clock period, the assumed amplitude value based on the power consumption model and the actual amplitude are most correlated at the points where the peaks are observed. We extract the calculation points of each power trace using signal processing and machine learning techniques, and select the region where the CPA will be applied to. Our proposed approach achieves an approximately 20% improvement in accuracy and requires less computational resources compared to conventional CPA.

In this paper, a parametric approach to design a Luenberger functional observer for linear time-varying (LTV) systems with time-delay is investigated. Based on the solution to generalized Sylvester equation (GSE), the complete general parametric expressions for the functional observer gain matrices are established with the time-varying coefficient matrices, the time-varying closed-loop system and a group of arbitrary parameters. With the parametric method, the observation error system can be transformed into a linear system with the expected eigenstructure. Finally, a numerical simulation is provided to illustrate the effectiveness of the parametric approach.

Clustering, which is a commonly used tool, has been applied in machine learning, data mining and so on, and has received extensive research. However, there are usually noise and outliers in the data, which will bring about significant errors in the clustering results. In this paper, a robust clustering model with adaptive graph regularization (RCAG) is proposed, on which, sparse error matrix is introduced to express sparse noise, such as impulse noise, dead line, stripes, and $\ell _{1}$ norm is introduced to alleviate the sparse noise. In addition, the $\ell _{2,1}$ norm is also proposed mitigating the effects of outliers, and it has rotation invariance property. Therefore, our RCAG is insensitive to data noise and outliers. More importantly, the adaptive graph regularization is introduced into the RCAG to improve the clustering performance. Aiming at the optimization objective, we propose an iterative updating algorithm, named the Augmented Lagrangian Method (ALM), to update each optimization variable respectively. The convergence and time complexity of RCAG is also proved in theory. Finally, experimental results on fourteen datasets of four application scenarios, such as face image, handwriting recognition and UCI, elaborate the superiority of proposed method over seven existing classical clustering methods. The experimental results demonstrate that our approach achieves better clustering performance in ACC and Purity, which is a little less impressive in other ways.

Consensus clustering algorithm, which integrates several clustering results obtained by common algorithms, can find a better result that is independent on parameter settings. However, this kind of algorithm is often designed based on simple, such as $K$ -means, algorithms, which is limited by the time complexity. In this work, a P system, a novel branch of bio-inspired computing with inherent parallel and distributed computation, is combined with the consensus clustering algorithm. As a result, an improved consensus clustering algorithm is constructed using the hierarchical membrane structure and parallel evolution mechanism in a cell-like P system with multi-catalysts, where the catalysts are utilized to regulate the parallelism of objects evolution. The integration strategy of the algorithm is based on a revised PAM where only the $q$ -nearest neighbors of the original medoids are considered as candidates for the new medoids. The experimental results indicate that the clustering quality of the proposed algorithm is more robust than well-known consensus clustering algorithms on data sets with noises and outliers. This work gives evidence that the effectiveness and efficiency of consensus clustering algorithms can be improved using P systems.

In a graph $G$ , two spanning trees $T_{1}$ and $T_{2}$ are rooted at the same vertex $r$ . If, for every $v \in V(G)$ , the paths from $v$ to the root $r$ in $T_{1}$ and $T_{2}$ are internally vertex-disjoint, they are called independent spanning trees (ISTs). ISTs can be applied in numerous fields, such as fault-tolerant broadcasting and secure message distribution. The ( $n$ , $k$ )-star graphs $S_{n,k}$ constitute a generalized version of the star network. The method of constructing ISTs in ( $n$ , $k$ )-star graphs remains unknown. In this paper, we propose one recursive algorithm and one parallel algorithm for constructing ISTs on ( $n$ , $k$ )-star graphs. The main ideas of the recursive algorithm are to use induction to change small trees into large trees, to use a modified breadth-first search (MBFS) traversal to create a frame for an IST, and to use a breadth-first search (BFS) traversal to connect the rest of nodes. The main ideas of the parallel algorithm are to create frames through MBFS traversals in parallel, and to use some specific rules to connect the rest of nodes in parallel. We also present validation proofs for both algorithms, and analyze the time complexities of both algorithms. The time complexity of the recursive algorithm in $S_{n,k}$ is $O\left({n\times \frac {n!}{(n-k)!}}\right)$ , where $\frac {n!}{(n-k)!}$ is the number of nodes of $S_{n,k}$ . The time complexity of the parallel algorithm can be reduced to $O\left({\frac {n!}{(n-k)!}}\right)$ if the system has $n-1$ processors computing in parallel. Both algorithms are correct with the stated time complexity values; the parallel algorithm is more efficient than the recursive algorithm.

In this paper, we propose a method for optimizing search engine results based on user interaction. This method generates different search results mainly through the user’s operation on different search topics. There are two main differences between our method and the traditional personalized search method: personal privacy and storage space. First, traditional personal search methods need to record search and click records for individual users. However, these records have great personal privacy issues for users; especially in recent years, there have been personal privacy leaks that occurred in many large online companies (such as Facebook and Yahoo). Secondly, because different users need to record their own search records, the size of the storage space is closely related to the number of users and the amount of search records stored. However, the sum of individual users’ search and click records is a huge storage space in today’s Internet environment. To avoid these two issues for traditional personalized search methods, this study proposes a storage-free approach based on individual users operating on different search topics. In general, in addition to avoiding personal privacy and storage space issues, our method can also achieve optimal linear time in generating personalized search results.

Users' historical activities are usually contained in real-life sequential recommendation systems to predict their future behaviors. In this situation, traditional Factorization Machines (FMs) approaches may be not suitable. Recently, a new surge of interest aims to use recurrent neural networks(RNN) to encode users' dynamic features with temporal characteristics. However, most of these works fail to reproduce computational simplicity of FMs. In this paper, we propose an architecture of extended-FM for sequential recommendation, which presents temporal feature interactions in an explicit way as traditional FM's formula. Our approach also allows us to accomplish computation of the model in linear time. Furthermore, we merge extended-FM into higher-order interaction framework without significant changes to the deeper models themselves. We conduct comprehensive experiments on two real-world datasets. The results demonstrate that extended-FM outperforms traditional FMs as well as deep learning feature combination models on sequential recommendation tasks.