Search

The problem of finding a maximum size matching in a graph (known as the maximum matching problem) is one of the most classical problems in computer science. Despite a significant body of work dedicated to the study of this problem in the data stream model, the state-of-the-art single-pass semi-streaming algorithm for it is still a simple greedy algorithm that computes a maximal matching, and this way obtains 1 / 2 -approximation. Some previous works described two/three-pass algorithms that improve over this approximation ratio by using their second and third passes to improve the above mentioned maximal matching. One contribution of this paper continues this line of work by presenting new three-pass semi-streaming algorithms that work along these lines and obtain improved approximation ratios of 0.6111 and 0.5694 for triangle-free and general graphs, respectively. Unfortunately, a recent work Konrad and Naidu (Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2021, August 16–18, 2021. LIPIcs, vol 207, pp 19:1–19:18, 2021. https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.19) shows that the strategy of constructing a maximal matching in the first pass and then improving it in further passes has limitations. Additionally, this technique is unlikely to get us closer to single-pass semi-streaming algorithms obtaining a better than 1 / 2 -approximation. Therefore, it is interesting to come up with algorithms that do something else with their first pass (we term such algorithms non-maximal-matching-first algorithms). No such algorithms were previously known, and the main contribution of this paper is describing such algorithms that obtain approximation ratios of 0.5384 and 0.5555 in two and three passes, respectively, for general graphs. The main significance of our results is not in the numerical improvements, but in demonstrating the potential of non-maximal-matching-first algorithms. [ABSTRACT FROM AUTHOR]

Cluster analysis is one of the most fundamental methods in data mining, and it has been widely used in economics, social sciences and computer science. However, with the rapid development of Internet technology, the volume of data required for various web applications has grown rapidly, making the traditional clustering analysis methods face technical challenges. How to obtain useful information in a large amount of data quickly and efficiently is an urgent problem in many industrial fields. With the continuous development of cloud computing technology, large amounts of data can be performed quickly and efficiently. Hadoop is an open source distributed cloud computing platform with HDFS (Digital File System) and MapReduce as its core. HDFS provides massive data storage, while MapReduce uses the MapReduce programming model to achieve parallel processing. Compared with the traditional parallel programming model, it contains basic functions such as data partitioning, task scheduling, and parallel processing, making it possible for users to develop distributed applications on their own without understanding the basics of distributed basics, thus facilitating the design of parallel programs. K-means algorithm is a typical clustering analysis method, which is widely used in industry, but the number of iterations will increase significantly due to the growth of data volume, thus reducing the efficiency of computation. In order to better apply to the cluster analysis of large-scale data, this paper firstly implements a parallelization algorithm based on MapReduce on Hadoop platform using the basic idea of MapReduce and improves the K-means algorithm for the problems of blindness and easy to fall into local optimum when selecting randomly in clusters. [ABSTRACT FROM AUTHOR]

In recent years, artificial intelligence has become an important discipline in the field of computer science. Students, in the absence of basic prior knowledge, may have difficulty tracking materials when they first encounter complex and abstract artificial intelligence algorithms. Numerous researchers and educators point out that the use of simulation systems and software tools to illustrate the dynamic behavior of the algorithm can prove to be an effective solution. The introduction and adoption of new technologies in learning and teaching has evolved rapidly. This conceptual review paper aims to explore the emergence of innovative educational technologies in the teaching and learning of artificial intelligence. The aim of this paper is to analyze the existing representative educational tools for learning topics in the field of artificial intelligence to highlight their characteristics and areas they cover, so that readers can more easily draw conclusions about the possible use of some of the analyzed systems. [ABSTRACT FROM AUTHOR]

The theory of Formal Concept Analysis (FCA) finds diverse applications in fields like knowledge extraction, cognitive concept learning and data mining. The construction of a concept lattice significantly influences the effectiveness of formal concept analysis; hence, the development of high-performance algorithms for concept construction is crucial. In this paper, we introduce a novel algorithm called "Bit-Close" for formal concept construction. Bit-Close leverages bit representation and operations, fundamental to computer science, to enhance the In-Close algorithm. Furthermore, we explore the parallel method of Bit-Close. Our experimental results, obtained from multiple public and random datasets, demonstrate that Bit-Close outperforms In-Close by approximately 20% and is significantly better than other competing algorithms. [ABSTRACT FROM AUTHOR]

In our paper, we consider the following general problems: check feasibility, count the number of feasible solutions, find an optimal solution, and count the number of optimal solutions in P ∩ Z n , assuming that P is a polyhedron, defined by systems A x ≤ b or A x = b , x ≥ 0 with a sparse matrix A. We develop algorithms for these problems that outperform state-of-the-art ILP and counting algorithms on sparse instances with bounded elements in terms of the computational complexity. Assuming that the matrix A has bounded elements, our complexity bounds have the form s O (n) , where s is the minimum between numbers of non-zeroes in columns and rows of A, respectively. For s = o (log n) , this bound outperforms the state-of-the-art ILP feasibility complexity bound (log n) O (n) , due to Reis & Rothvoss (in: 2023 IEEE 64th Annual symposium on foundations of computer science (FOCS), IEEE, pp. 974–988). For s = ϕ o (log n) , where ϕ denotes the input bit-encoding length, it outperforms the state-of-the-art ILP counting complexity bound ϕ O (n log n) , due to Barvinok et al. (in: Proceedings of 1993 IEEE 34th annual foundations of computer science, pp. 566–572, https://doi.org/10.1109/SFCS.1993.366830, 1993), Dyer, Kannan (Math Oper Res 22(3):545–549, https://doi.org/10.1287/moor.22.3.545, 1997), Barvinok, Pommersheim (Algebr Combin 38:91–147, 1999), Barvinok (in: European Mathematical Society, ETH-Zentrum, Zurich, 2008). We use known and new methods to develop new exponential algorithms for Edge/Vertex Multi-Packing/Multi-Cover Problems on graphs and hypergraphs. This framework consists of many different problems, such as the Stable Multi-set, Vertex Multi-cover, Dominating Multi-set, Set Multi-cover, Multi-set Multi-cover, and Hypergraph Multi-matching problems, which are natural generalizations of the standard Stable Set, Vertex Cover, Dominating Set, Set Cover, and Maximum Matching problems. [ABSTRACT FROM AUTHOR]

We consider the weighted k-set packing problem, where, given a collection S of sets, each of cardinality at most k, and a positive weight function w : S → Q > 0 , the task is to find a sub-collection of S consisting of pairwise disjoint sets of maximum total weight. As this problem does not permit a polynomial-time o (k log k) -approximation unless P = N P (Hazan et al. in Comput Complex 15:20–39, 2006. https://doi.org/10.1007/s00037-006-0205-6), most previous approaches rely on local search. For twenty years, Berman's algorithm SquareImp (Berman, in: Scandinavian workshop on algorithm theory, Springer, 2000. https://doi.org/10.1007/3-540-44985-X%5f19), which yields a polynomial-time k + 1 2 + ϵ -approximation for any fixed ϵ > 0 , has remained unchallenged. Only recently, it could be improved to k + 1 2 - 1 63 , 700 , 993 by Neuwohner (38th International symposium on theoretical aspects of computer science (STACS 2021), Leibniz international proceedings in informatics (LIPIcs), 2021. https://doi.org/10.4230/LIPIcs.STACS.2021.53). In her paper, she showed that instances for which the analysis of SquareImp is almost tight are "close to unweighted" in a certain sense. But for the unit weight variant, the best known approximation guarantee is k + 1 3 + ϵ (Fürer and Yu in International symposium on combinatorial optimization, Springer, 2014. https://doi.org/10.1007/978-3-319-09174-7%5f35). Using this observation as a starting point, we conduct a more in-depth analysis of close-to-tight instances of SquareImp. This finally allows us to generalize techniques used in the unweighted case to the weighted setting. In doing so, we obtain approximation guarantees of k + ϵ k 2 , where lim k → ∞ ϵ k = 0 . On the other hand, we prove that this is asymptotically best possible in that local improvements of logarithmically bounded size cannot produce an approximation ratio below k 2 . [ABSTRACT FROM AUTHOR]

Many researchers have recently considered patients' health and provided an optimal and appropriate solution. With the advent of technologies such as cloud computing, Internet of Things and 5G, information can be exchanged faster and more securely. The Internet of things (IoT) offers many opportunities in the field of e-health. This technology can improve health services and lead to various innovations in this regard. Using cloud computing and IoT in this process can significantly improve the monitoring of patients. Therefore, it is important to provide a useful method in the medical industry and computer science to monitor the status of patients using connected sensors. Thus, due to its optimal efficiency, speed, and accuracy of data processing and classification, the use of cloud computing to process the data collected from remote patient sensors and IoT platform has been suggested. In this paper, a prioritization system is used to prioritize sensitive information in IoT, and in cloud computing, LSTM deep neural network is applied to classify and monitor patients' condition remotely, which can be considered as an important innovative aspect of this paper. Sensor data in the IoT platform is sent to the cloud with the help of the 5th generation Internet. The core of cloud computing uses the LSTM (long short-term memory) deep neural network algorithm. By simulating the proposed method and comparing the obtained results with other methods, it is observed that the accuracy of the proposed method is 97.13%, which has been improved by 10.41% in average over the other methods. [ABSTRACT FROM AUTHOR]

We focus on the automatic detection of communities in large networks, a challenging problem in many disciplines (such as sociology, biology, and computer science). Humans tend to associate to form families, villages, and nations. Similarly, the elements of real-world networks naturally tend to form highly connected groups. A popular model to represent such structures is the clique, that is, a set of fully interconnected nodes. However, it has been observed that cliques are too strict to represent communities in practice. The k-plex relaxes the notion of clique, by allowing each node to miss up to k connections. Although k-plexes are more flexible than cliques, finding them is more challenging as their number is greater. In addition, most of them are small and not significant. In this paper we tackle the problem of finding only large k-plexes (i.e., comparable in size to the largest clique) and design a meta-algorithm that can be used on top of known enumeration algorithms to return only significant k-plexes in a fraction of the time. Our approach relies on: (1) methods for strongly reducing the search space and (2) decomposition techniques based on the efficient computation of maximal cliques. We demonstrate experimentally that known enumeration algorithms equipped with our approach can run orders of magnitude faster than full enumeration. [ABSTRACT FROM AUTHOR]

Knowledge graph has wide applications in the field of computer science. In the knowledge service environment, the information is large and explosive, and it is difficult to find knowledge of common phenomena. The urban traffic knowledge graph is a knowledge system that formally describes urban traffic concepts, entities and their interrelationships. It has great application potential in application scenarios such as user travel, route planning, and urban planning. This paper first defines the urban traffic knowledge graph and the star subgraph query of the urban traffic knowledge graph. Then, the road network data and trajectory data are collected to extract the urban traffic knowledge, and the urban traffic knowledge graph is constructed with this knowledge. Finally, a star subgraph query algorithm on the urban traffic knowledge graph is proposed. The discussion of the star subgraph query mode gives the corresponding application scenarios of our method in the urban traffic knowledge graph. Experimental results verify the performance advantages of this method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new effective algorithm for the categorical syllogisms by using a calculus system Syllogistic Logic with Carroll Diagrams, which determines a formal approach to logical reasoning with diagrams, for representations of the fundamental Aristotelian categorical syllogisms. We show that this logical reasoning is closed under the syllogistic criterion of inference. Therefore, the calculus system is implemented to let the formalism which comprises synchronically bilateral and trilateral diagrammatical appearance and naive algorithmic nature. And also, there is no need specific knowledge or exclusive ability to understand this decision procedure as well as to use it in an algorithmic system. Consequently, the empirical contributions of this paper are to design a polynomial-time algorithm at the first time in the literature to conduce to researchers getting into the act in different areas of science used categorical syllogisms such as artificial intelligence, engineering, computer science and etc. [ABSTRACT FROM AUTHOR]

Algorithmic statistics looks for models of observed data that are good in the following sense: a model is simple (i.e., has small Kolmogorov complexity) and captures all the algorithmically discoverable regularities in the data. However, this idea can not be used in practice as is because Kolmogorov complexity is not computable. In this paper we develop an algorithmic version of algorithmic statistics that uses space-bounded Kolmogorov complexity. We prove a space-bounded version of a basic result from "classical" algorithmic statistics, the connection between optimality and randomness deficiences. The main tool is the Nisan–Wigderson pseudo-random generator. An extended abstract of this paper was presented at the 12th International Computer Science Symposium in Russia (Milovanov 10). [ABSTRACT FROM AUTHOR]

We study a security game over a network played between a defender and kattackers. Every attacker chooses, probabilistically, a node of the network to damage. The defender chooses, probabilistically as well, a connected induced subgraph of the network of λ nodes to scan and clean. Each attacker wishes to maximize the probability of escaping her cleaning by the defender. On the other hand, the goal of the defender is to maximize the expected number of attackers that she catches. This game is a generalization of the model from the seminal paper of Mavronicolas et al. Mavronicolas et al. (in: International symposium on mathematical foundations of computer science, MFCS, pp 717–728, 2006). We are interested in Nash equilibria of this game, as well as in characterizing defense-optimal networks which allow for the best equilibrium defense ratio; this is the ratio of k over the expected number of attackers that the defender catches in equilibrium. We provide a characterization of the Nash equilibria of this game and defense-optimal networks. The equilibrium characterizations allow us to show that even if the attackers are centrally controlled the equilibria of the game remain the same. In addition, we give an algorithm for computing Nash equilibria. Our algorithm requires exponential time in the worst case, but it is polynomial-time for λ constantly close to 1 or n. For the special case of tree-networks, we further refine our characterization which allows us to derive a polynomial-time algorithm for deciding whether a tree is defense-optimal and if this is the case it computes a defense-optimal Nash equilibrium. On the other hand, we prove that it is NP -hard to find a best-defense strategy if the tree is not defense-optimal. We complement this negative result with a polynomial-time constant-approximation algorithm that computes solutions that are close to optimal ones for general graphs. Finally, we provide asymptotically (almost) tight bounds for the Price of Defense for any λ ; this is the worst equilibrium defense ratio over all graphs. [ABSTRACT FROM AUTHOR]

In many applications, top- k query is an important operation to return a set of interesting points in a potentially huge data space. The existing algorithms, either maintaining too many candidates, or requiring assistant structures built on the specific attribute subset, or returning results with probabilistic guarantee, cannot process top- k query on massive data efficiently. This paper proposes a sorted-list-based TKAP algorithm, which utilizes some data structures of low space overhead, to efficiently compute top- k results on massive data. In round-robin retrieval on sorted lists, TKAP performs adaptive pruning operation and maintains the required candidates until the stop condition is satisfied. The adaptive pruning operation can be adjusted by the information obtained in round-robin retrieval to achieve a better pruning effect. The adaptive pruning rule is developed in this paper, along with its theoretical analysis. The extensive experimental results, conducted on synthetic and real-life data sets, show the significant advantage of TKAP over the existing algorithms. [ABSTRACT FROM AUTHOR]

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. Sampled string matching is an efficient approach recently introduced in order to overcome the prohibitive space requirements of an index construction, on the one hand, and drastically reduce searching time for the online solutions, on the other hand. In this paper we present a new algorithm for the sampled string matching problem, based on a characters distance sampling approach. The main idea is to sample the distances between consecutive occurrences of a given pivot character and then to search online the sampled data for any occurrence of the sampled pattern, before verifying the original text. From a theoretical point of view we prove that, under suitable conditions, our solution can achieve both linear worst-case time complexity and optimal average-time complexity. From a practical point of view it turns out that our solution shows a sub-linear behaviour in practice and speeds up online searching by a factor of up to 9, using limited additional space whose amount goes from 11 to 2.8% of the text size, with a gain up to 50% if compared with previous solutions. [ABSTRACT FROM AUTHOR]

This problem can benefit from machine learning techniques, thanks to their capability of finding "hidden" relationships among the available data and therefore generate placement actions. In society, data producers and data consumers continuously exchange their roles. Since the very beginning, there has been a fruitful exchange between machine learning (ML) and optimization. [Extracted from the article]

In this paper, we prove that, given a clique-width k-expression of an n-vertex graph, Hamiltonian Cycle can be solved in time n O (k) . This improves the naive algorithm that runs in time n O (k 2) by Espelage et al. (Graph-theoretic concepts in computer science, vol 2204. Springer, Berlin, 2001), and it also matches with the lower bound result by Fomin et al. that, unless the Exponential Time Hypothesis fails, there is no algorithm running in time n o (k) (Fomin et al. in SIAM J Comput 43:1541–1563, 2014). We present a technique of representative sets using two-edge colored multigraphs on k vertices. The essential idea is that, for a two-edge colored multigraph, the existence of an Eulerian trail that uses edges with different colors alternately can be determined by two information: the number of colored edges incident with each vertex, and the connectedness of the multigraph. With this idea, we avoid the bottleneck of the naive algorithm, which stores all the possible multigraphs on k vertices with at most n edges. [ABSTRACT FROM AUTHOR]

In 1994, Klapper and Goresky (Proceedings of the 1993 Cambridge Security Workshop, Lecture Notes in Computer Science, vol 809, Cambridge, pp 174–178, 1994) proposed a new device called feedback with carry shift register to generate pseudo-random sequences instead of using the traditional device linear feedback shift register. They raised an algorithm called as rational approximation algorithm to recover the device for a given sequence (Klapper and Goresky, Advances in Cryptology, Crypto'95, Lecture Notes in Computer Science, vol 963, Springer, Berlin, pp 262–274, 1995). In this paper, we propose a new algorithm by introducing a new parameter and get the best rational approximation of the sequence much more quickly, especially when the size of the sequence increases dramatically. Unlike most of known algorithms, we can solve the minimal lattice basis instead of one shortest vector. Besides, we can prove that the solution of each step is optimal regardless of the length of the input sequence theoretically. [ABSTRACT FROM AUTHOR]

Let B = (X , Y , E) be a bipartite graph. A half-square of B has one color class of B as vertex set, say X; two vertices are adjacent whenever they have a common neighbor in Y. Every planar graph is a half-square of a planar bipartite graph, namely of its subdivision. Until recently, only half-squares of planar bipartite graphs, also known as map graphs (Chen et al., in: Proceedings of the thirtieth annual ACM symposium on the theory of computing, STOC '98, pp 514–523. 10.1145/276698.276865, 1998; J ACM 49(2):127–138. 10.1145/506147.506148, 2002), have been investigated, and the most discussed problem is whether it is possible to recognize these graphs faster and simpler than Thorup's O (n 120) -time algorithm (Thorup, in: Proceedings of the 39th IEEE symposium on foundations of computer science (FOCS), pp 396–405. 10.1109/SFCS.1998.743490, 1998). In this paper, we identify the first hardness case, namely that deciding if a graph is a half-square of a balanced bisplit graph is NP-complete. (Balanced bisplit graphs form a proper subclass of star convex bipartite graphs). For classical subclasses of tree convex bipartite graphs such as biconvex, convex, and chordal bipartite graphs, we give good structural characterizations of their half-squares that imply efficient recognition algorithms. As a by-product, we obtain new characterizations of unit interval graphs, interval graphs, and of strongly chordal graphs in terms of half-squares of biconvex bipartite, convex bipartite, and of chordal bipartite graphs, respectively. Good characterizations of half-squares of star convex and star biconvex bipartite graphs are also given, giving linear-time recognition algorithms for these half-squares. [ABSTRACT FROM AUTHOR]

Different sets of research mainly focus on one variable time series now, while researches involving multivariate time series have been insufficient. In this paper, combined linear segments and fitting error for multivariate time series, we present a new method to reduce the time complexity of DTW distance metric algorithm. Based on the shape feature and the tilt angle, we propose a new approach for similarity matching of DTW multivariate time series. Experimental results demonstrate that this method is helpful for ensuring accuracy and for reducing the time complexity of similarity matching. [ABSTRACT FROM AUTHOR]

Although ordering-based pruning algorithms possess relatively high efficiency, there remains room for further improvement. To this end, this paper describes the combination of a dynamic programming technique with the ensemble-pruning problem. We incorporate dynamic programming into the classical ordering-based ensemble-pruning algorithm with complementariness measure (ComEP), and, with the help of two auxiliary tables, propose a reasonably efficient dynamic form, which we refer to as ComDPEP. To examine the performance of the proposed algorithm, we conduct a series of simulations on four benchmark classification datasets. The experimental results demonstrate the significantly higher efficiency of ComDPEP over the classic ComEP algorithm. The proposed ComDPEP algorithm also outperforms two other state-of-the-art ordering-based ensemble-pruning algorithms, which use uncertainty weighted accuracy and reduce-error pruning, respectively, as their measures. It is noteworthy that, the effectiveness of ComDPEP is just the same with that of the classical ComEP algorithm. [ABSTRACT FROM AUTHOR]

In this paper we find a connection between constructive number fields and computable reals. This connection is applied to prove the computability in the rigorous sense of computable analysis) of solutions of some important systems of partial differential equations, by means of algorithms which are really used in numerical analysis. [ABSTRACT FROM AUTHOR]

Research on graph searching has recently gained interest in computer science, mathematics, and physics. This paper studies fast searching of a fugitive in a graph, a model that was introduced by Dyer et al. (in: Fleischer, Xu (eds.) Algorithmic aspects in information and management, Springer, New York, 2008). We provide lower bounds and upper bounds on the fast search number (i.e., the minimum number of searchers required for capturing the fugitive) of complete k-partite graphs. We also investigate some special classes of complete k-partite graphs, such as complete bipartite graphs and complete split graphs. We solve the open problem of determining the fast search number of complete bipartite graphs, and present upper and lower bounds on the fast search number of complete split graphs. [ABSTRACT FROM AUTHOR]

Voice activity detection (VAD) refers to the task of identifying vocal segments from an audio clip. It helps in reducing the computational overhead as well elevate the recognition performance of speech-based systems by helping to discard the non vocal portions from an input signal. In this paper, a VAD technique is presented that uses line spectral frequency-based statistical features namely LSF-S coupled with extreme learning-based classification. The experiments were performed on a database of more than 350 h consisting of data from multifarious sources. We have obtained an encouraging overall accuracy of 99.43%. [ABSTRACT FROM AUTHOR]

In the field of computer science, the metaheuristics is a top level approach that is configured to discover, to yield or to pick a biased searching algorithm that may deliver an adequate and proper explication to an optimization problem, particularly with deficient information or with restricted reckoning potential. Metaheuristic algorithms experiments to figure out finest explication compared to all feasible explications of an optimizing problems. Because of scanty link authenticity, dynamic changing topology and overloading this type networks have least network traffic capacity in mobile adhoc networks. In this present study paper, a new nature stimulated metaheuristics algorithm called Emperor Penguin Optimizing Algorithm is proposed to find out an energy efficient routing with QoS requirements in Mobile Adhoc Networks. This proposed Emperor penguin colony optimizing algorithm is governed by the penguin heat emission and their spiral shaped movement in the huddle to determine an optimal routing that satisfies various QoS requirements. Simulation results outperforms that the proposed work enhances packet delivery ratio, throughput of a network and the reliability of the routing process. [ABSTRACT FROM AUTHOR]

The article focuses on using test collections for information retrieval evaluation. Test collections play an important role in providing a basis for the measurement and comparison of the effectiveness of information retrieval algorithms and techniques. The use of standard test collections helped to differentiate the field of information retrieval in computer science.

Node distance/proximity measures are used for quantifying how nearby or otherwise related two or more nodes on a graph are. In particular, personalized PageRank (PPR) based measures of node proximity have been shown to be highly effective in many prediction and recommendation applications. Despite its effectiveness, however, the use of personalized PageRank for large graphs is difficult due to its high computation cost. In this paper, we propose a Locality-sensitive, Re-use promoting, approximate Personalized PageRank (LR-PPR) algorithm for efficiently computing the PPR values relying on the localities of the given seed nodes on the graph: (a) The LR-PPR algorithm is locality sensitive in the sense that it reduces the computational cost of the PPR computation process by focusing on the local neighborhoods of the seed nodes. (b) LR-PPR is re-use promoting in that instead of performing a monolithic computation for the given seed node set using the entire graph, LR-PPR divides the work into localities of the seeds and caches the intermediary results obtained during the computation. These cached results are then reused for future queries sharing seed nodes. Experiment results for different data sets and under different scenarios show that LR-PPR algorithm is highly-efficient and accurate. [ABSTRACT FROM AUTHOR]

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2 nodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(| P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log| T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the lz78 encoding of a given string of length n over an alphabet of size σ in sublinear ( o( n)) time and sublinear ( o( nlog σ) bits) working space for small alphabets ( $\sigma= 2^{o(\log n \frac{\log\log\log n}{(\log\log n)^{2}})}$). Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size. [ABSTRACT FROM AUTHOR]

Cognitive Computing breaks the boundary between two separate fields, neuroscience and computer science. Regarding the issue, Jiang et al. [[3]] consider the communication cost of virtual machine (VM) migration and proposes a VM Migration Algorithm based on Gene Aggregation Genetic Algorithm (VMM-GAGA). Mobile Netw Appl. 10.1007/s11036-019-01375-8 3 Jiang Y, Wang J, Shi J et al (2020) Network-aware virtual machine migration based on gene aggregation genetic algorithm. [Extracted from the article]

Recently, as a result of the popularity of online social networks, the analysis and comparison of their contents are in an incremental need. The study of social network and social interaction including both positive and negative connections, which is obviously significant. Our finding denotes that the contacts in the basic social networks, including their accuracy, are predictable. The trust of numerous users' imparting on a node accounts for the form of networks. In this paper, We propose a model in this article to figure out the prestige on nodes in a network based on trust. This network also lays more emphasis to on trustworthy nodes. In the beginning, to achieve this goal, we try to indicate signed advantages in networks to predict an user's opinion to another. After that, we present an algorithm, which can compute the prestige and trustworthiness. In their edge weight, we can find out the trust score. According to our experiments on the public dataset, we demonstrate the validity and efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

Correction to: Multimedia Systems https://doi.org/10.1007/s00530-021-00858-7 In the original publication of the article, the third author affiliation was erroneously published; the correct affiliation should read as: School of Computer Science, University of Technology Sydney, Sydney, Australia. Publisher's Note Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations. [Extracted from the article]

Identification of influential spreaders is still a challenging issue in network science. Therefore, it attracts increasing attention from both computer science and physical societies, and many algorithms to identify influential spreaders have been proposed so far. Degree centrality, as the most widely used neighborhood-based centrality, was introduced into the network world to evaluate the spreading ability of nodes. However, degree centrality always assigns too many nodes with the same value, so it leads to the problem of resolution limitation in distinguishing the real influences of these nodes, which further affects the ranking efficiency of the algorithm. The k-shell decomposition method also faces the same problem. In order to solve the resolution limit problem, we propose a high-resolution index combining both degree centrality and the k-shell decomposition method. Furthermore, based on the proposed index and the well-known gravity law, we propose an improved gravity model to measure the importance of nodes in propagation dynamics. Experiments on ten real networks show that our model outperforms most of the state-of-the-art methods. It has a better performance in terms of ranking performance as measured by the Kendall's rank correlation, and in terms of ranking efficiency as measured by the monotonicity value. [ABSTRACT FROM AUTHOR]

Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length n contains a given pattern of length k. In this work we give two new algorithms for this well-studied problem, one whose running time is n k / 4 + o (k) , and a polynomial-space algorithm whose running time is the better of O (1. 6181 n) and O (n k / 2 + 1) . These results improve the earlier best bounds of n 0.47 k + o (k) and O (1. 79 n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when k ∈ Ω (log n) . We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. Our algorithms can also count, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time f (k) · n o (k / log k) would contradict the exponential-time hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing (4321-avoiding) and 3-decreasing (1234-avoiding) permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes. [ABSTRACT FROM AUTHOR]

Papadimitriou and Yannakakis (Proceedings of the 41st annual IEEE symposium on the Foundations of Computer Science (FOCS), pp 86–92, 2000) show that the polynomial-time solvability of a certain auxiliary problem determines the class of multiobjective optimization problems that admit a polynomial-time computable (1 + ε , ⋯ , 1 + ε) -approximate Pareto set (also called an ε -Pareto set). Similarly, in this article, we characterize the class of multiobjective optimization problems having a polynomial-time computable approximate ε -Pareto set that is exact in one objective by the efficient solvability of an appropriate auxiliary problem. This class includes important problems such as multiobjective shortest path and spanning tree, and the approximation guarantee we provide is, in general, best possible. Furthermore, for biobjective optimization problems from this class, we provide an algorithm that computes a one-exact ε -Pareto set of cardinality at most twice the cardinality of a smallest such set and show that this factor of 2 is best possible. For three or more objective functions, however, we prove that no constant-factor approximation on the cardinality of the set can be obtained efficiently. [ABSTRACT FROM AUTHOR]

There exists a direct need to automate the process of test suite generation to get the most optimal results as testing accounts for more than 40% of total cost. One method to solve this problem is the use of meta-heuristic algorithms which iteratively improve the test data to reach the most optimized test suites. This study focuses on the performance evaluation of six meta-heuristic algorithms namely: hill-climbing algorithm (HCA), particle swarm optimization (PSO), firefly algorithm (FA), cuckoo search algorithm (CS), bat algorithm (BA) and artificial bee colony algorithm (ABC) by using their standard implementation to optimize the path coverage and branch coverage produced by the test data. The goal of the study was to find the best-suited algorithm to narrow down the future research in the field of test automation for path coverage-based optimization approaches. Each algorithm was first implemented to automatically generate test suites based on the program under test. This was followed by the performance evaluation of each algorithm for five programs written in Java. The algorithms were compared using process metrics: average time, best time, worst time and product metrics: path coverage & objective function values of the generated test suites. Results indicated ABC as the best-suited algorithm as it gave the most optimal test suites in reasonable time. BA was found to be the fastest but produced less optimal results. FA was found to be the slowest algorithm, while CS, PSO and HCA performed in between. These results show the relative performance of the six algorithms for this scenario and may be used by the future researchers to narrow down and improve the best performing algorithms for path coverage-based optimization approaches. [ABSTRACT FROM AUTHOR]

Objectives: (1) To assess the methodological quality of radiomics studies investigating histological subtypes, therapy response, and survival in patients with renal cell carcinoma (RCC) and (2) to determine the risk of bias in these radiomics studies.Methods: In this systematic review, literature published since 2000 on radiomics in RCC was included and assessed for methodological quality using the Radiomics Quality Score. The risk of bias was assessed using the Quality Assessment of Diagnostic Accuracy Studies tool and a meta-analysis of radiomics studies focusing on differentiating between angiomyolipoma without visible fat and RCC was performed.Results: Fifty-seven studies investigating the use of radiomics in renal cancer were identified, including 4590 patients in total. The average Radiomics Quality Score was 3.41 (9.4% of total) with good inter-rater agreement (ICC 0.96, 95% CI 0.93-0.98). Three studies validated results with an independent dataset, one used a publically available validation dataset. None of the studies shared the code, images, or regions of interest. The meta-analysis showed moderate heterogeneity among the included studies and an odds ratio of 6.24 (95% CI 4.27-9.12; p < 0.001) for the differentiation of angiomyolipoma without visible fat from RCC.Conclusions: Radiomics algorithms show promise for answering clinical questions where subjective interpretation is challenging or not established. However, the generalizability of findings to prospective cohorts needs to be demonstrated in future trials for progression towards clinical translation. Improved sharing of methods including code and images could facilitate independent validation of radiomics signatures.Key Points: • Studies achieved an average Radiomics Quality Score of 10.8%. Common reasons for low Radiomics Quality Scores were unvalidated results, retrospective study design, absence of open science, and insufficient control for multiple comparisons. • A previous training phase allowed reaching almost perfect inter-rater agreement in the application of the Radiomics Quality Score. • Meta-analysis of radiomics studies distinguishing angiomyolipoma without visible fat from renal cell carcinoma show moderate diagnostic odds ratios of 6.24 and moderate methodological diversity. [ABSTRACT FROM AUTHOR]

A computational problem fed into a gate-model quantum computer identifies an objective function with a particular computational pathway (objective function connectivity). The solution of the computational problem involves identifying a target objective function value that is the subject to be reached. A bottleneck in a gate-model quantum computer is the requirement of several rounds of quantum state preparations, high-cost run sequences, and multiple rounds of measurements to determine a target (optimal) state of the quantum computer that achieves the target objective function value. Here, we define a method for optimal quantum state determination and computational path evaluation for gate-model quantum computers. We prove a state determination method that finds a target system state for a quantum computer at a given target objective function value. The computational pathway evaluation procedure sets the connectivity of the objective function in the target system state on a fixed hardware architecture of the quantum computer. The proposed solution evolves the target system state without requiring the preparation of intermediate states between the initial and target states of the quantum computer. Our method avoids high-cost system state preparations and expensive running procedures and measurement apparatuses in gate-model quantum computers. The results are convenient for gate-model quantum computations and the near-term quantum devices of the quantum Internet. [ABSTRACT FROM AUTHOR]

In the recent years, there has been a push to engage primary and secondary students in computer science to prepare them to live and work in a world influenced by computation. One of the efforts involves getting primary and secondary students to think computationally by introducing computational ideas such as, algorithms and abstraction. Majority of this work around computational thinking has focused on the use of digital technologies, in particular programming environments (Yadav, Stephenson, and Hong 2017). In today's highly digitalized world, we often associate computational problem-solving processes with the use of computers. Yet, solving problems computationally by designing solutions and processing data is not a digital skill, rather a mental skill. Humans have solved problems for eons and before anyone even thought about the types of digital technologies and devices we know today. The purpose of this article is to examine the historical route of computational thinking and how history can inspire and inform initiatives today. We introduce how computational thinking skills are rooted in non-digital (unplugged) human approaches to problem solving, and discuss how mainstream focus changed to digital (plugged) computer approaches, particularly on programming. In addition, we connect past research with current work in computer science education to argue that computational thinking skills and computing principles need to be taught in both unplugged and plugged ways for learners to develop deeper understanding of computational thinking ideas and their relevance in today's society. [ABSTRACT FROM AUTHOR]

Hash tables are ubiquitous in computer science for efficient access to large datasets. However, there is always a need for approaches that offer compact memory utilisation without substantial degradation of lookup performance. Cuckoo hashing is an efficient technique of creating hash tables with high space utilisation and offer a guaranteed constant access time. We are given n locations and m items. Each item has to be placed in one of the k ≥ 2 locations chosen by k random hash functions. By allowing more than one choice for a single item, cuckoo hashing resembles multiple choice allocations schemes. In addition it supports dynamically changing the location of an item among its possible locations. We propose and analyse an insertion algorithm for cuckoo hashing that runs in linear time with high probability and in expectation. Previous work on total allocation time has analysed breadth first search, and it was shown to be linear only in expectation. Our algorithm finds an assignment (with probability 1) whenever it exists. In contrast, the other known insertion method, known as random walk insertion, may run indefinitely even for a solvable instance. We also present experimental results comparing the performance of our algorithm with the random walk method, also for the case when each location can hold more than one item. As a corollary we obtain a linear time algorithm (with high probability and in expectation) for finding perfect matchings in a special class of sparse random bipartite graphs. We support this by performing experiments on a real world large dataset for finding maximum matchings in general large bipartite graphs. We report an order of magnitude improvement in the running time as compared to the Hopkraft–Karp matching algorithm. [ABSTRACT FROM AUTHOR]

Lifted Reed–Solomon codes, introduced by Guo et al. (in: Kleinberg (ed) Proceedings of the 4th conference on innovations in theoretical computer science, ITCS'13, ACM, New York, 2013), are known as one of the few families of high-rate locally correctable codes. They are built through the evaluation over the affine space of multivariate polynomials whose restriction along any affine line can be interpolated as a low degree univariate polynomial. In this work, we give a formal definition of their analogues over projective spaces, and we study some of their parameters and features. Local correcting algorithms are first derived from the very nature of these codes, generalizing the well-known local correcting algorithms for Reed–Muller codes. We also prove that the lifting of both Reed–Solomon and projective Reed–Solomon codes are deeply linked through shortening and puncturing operations. It leads to recursive formulae on their dimension and their monomial bases. We finally emphasize the practicality of lifted projective Reed–Solomon codes by computing their information sets and by providing an implementation of the codes and their local correcting algorithms. [ABSTRACT FROM AUTHOR]

Two mobile robots are initially placed at the same point on an infinite line. Each robot may move on the line in either direction not exceeding its maximal speed. The robots need to find a stationary target placed at an unknown location on the line. The search is completed when both robots arrive at the target point. The target is discovered at the moment when either robot arrives at its position. The robot knowing the placement of the target may communicate it to the other robot. We look for the algorithm with the shortest possible search time (i.e. the worst-case time at which both robots meet at the target) measured as a function of the target distance from the origin (i.e. the time required to travel directly from the starting point to the target at unit velocity). We consider two standard models of communication between the robots, namely wireless communication and communication by meeting. In the case of communication by meeting, a robot learns about the target while sharing the same location with a robot possessing this knowledge. We propose here an optimal search strategy for two robots including the respective lower bound argument, for the full spectrum of their maximal speeds. This extends the main result of Chrobak et al. (in: Italiano, Margaria-Steffen, Pokorný, Quisquater, Wattenhofer (eds) Current trends in theory and practice of computer science, SOFSEM, 2015) referring to the exact complexity of the problem for the case when the speed of the slower robot is at least one third of the faster one. In the wireless communication model, a message sent by one robot is instantly received by the other robot, regardless of their current positions on the line. For this model, we design a strategy which is optimal whenever the faster robot is at most 17+4≈8.123 times faster than the slower one. We also prove that otherwise the wireless communication offers no advantage over communication by meeting. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses various reports within the issue on topics including labeled and unlabeled k-trees, linear probing hashing with buckets, and asymptotic lattice path enumeration using diagonals.

We describe an algorithm that builds a plane spanner with a maximum degree of 8 and a spanning ratio of ≈4.414 with respect to the complete graph. This is the best currently known spanning ratio for a plane spanner with a maximum degree of less than 14. [ABSTRACT FROM AUTHOR]

Personal route prediction has emerged as an important topic within the mobility mining domain. In this context, many proposals apply an off-line learning process before being able to run the on-line prediction algorithm. The present work introduces a novel framework that integrates the route learning and the prediction algorithm in an on-line manner. By means of a thin-client and server architecture, it also puts forward a new concept for route abstraction based on the detection of spatial regions where certain velocity features of routes frequently change. The proposal is evaluated by real-world and synthetic datasets and compared with a well-established mechanism by exhibiting quite promising results. [ABSTRACT FROM AUTHOR]

Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609-618. doi:, 2012) proved the following result: Unless the unlikely complexity-theoretic collapse $$\mathsf {coNP}\subseteq \mathsf {NP/poly}$$ occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker's theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $$x_1,\ldots ,x_t$$ to a single SAT-instance y of size $${\text {poly}}(\max _i|x_i|)$$ such that y is satisfiable if and only if all $$x_i$$ are satisfiable. The 'AND' in the name stems from the fact that the predicate ' y is satisfiable' can be written as the AND of all predicates ' $$x_i$$ is satisfiable'. Drucker's theorem complements the result by Bodlaender et al. (J Comput Syst Sci 75:423-434, 2009) and Fortnow and Santhanam (J Comput Syst Sci 77:91-106, 2011), who proved the analogous statement for OR-compressions, and Drucker's proof not only subsumes their result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (Proceedings of the 53rd annual symposium on foundations of computer science (FOCS), pp 609-618. doi:, 2012) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (J Comput Syst Sci 26:209-211, 1983) for $$\mathsf {P}$$ -selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker's theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker. [ABSTRACT FROM AUTHOR]

Three results are shown on producibility in the hierarchical model of tile self-assembly. It is shown that a simple greedy polynomial-time strategy decides whether an assembly α is producible. The algorithm can be optimized to use $$O(|\alpha | \log ^2 |\alpha |)$$ time. Cannon et al. (STACS 2013: proceedings of the thirtieth international symposium on theoretical aspects of computer science. pp 172-184, ) showed that the problem of deciding if an assembly α is the unique producible terminal assembly of a tile system $${\mathcal {T}}$$ can be solved in $$O(|\alpha |^2 |{\mathcal {T}}| + |\alpha | |{\mathcal {T}}|^2)$$ time for the special case of noncooperative 'temperature 1' systems. It is shown that this can be improved to $$O(|\alpha | |{\mathcal {T}}| \log |{\mathcal {T}}|)$$ time. Finally, it is shown that if two assemblies are producible, and if they can be overlapped consistently-i.e., if the positions that they share have the same tile type in each assembly-then their union is also producible . [ABSTRACT FROM AUTHOR]

Existing causal discovery algorithms are usually not effective and efficient enough on high dimensional data. Because the high dimensionality reduces the discovered accuracy and increases the computation complexity. To alleviate these problems, we present a three-phase approach to learn the structure of nonlinear causal models by taking the advantage of feature selection method and two state of the art causal discovery methods. In the first phase, a greedy search method based on Max-Relevance and Min-Redundancy is employed to discover the candidate causal set, a rough skeleton of the causal network is generated accordingly. In the second phase, constraint-based method is explored to discover the accurate skeleton from the rough skeleton. In the third phase, direction learning algorithm IGCI is conducted to distinguish the direction of causalities from the accurate skeleton. The experimental results show that the proposed approach is both effective and scalable, particularly with interesting findings on the high dimensional data. [ABSTRACT FROM AUTHOR]

GPU tessellation is very efficient and is reshaping the terrain-rendering paradigm. We present a novel terrain-rendering algorithm based on GPU tessellation. The planar domain of the terrain is partitioned into a set of tiles, and a coarse-grained quadtree is constructed for each tile using a screen-space error metric. Then, each node of the quadtree is input to the GPU pipeline together with its own tessellation factors. The nodes are tessellated and the vertices of the tessellated mesh are displaced by filtering the displacement maps. The multi-resolution scheme is designed to optimize the use of GPU tessellation. Further, it accepts not only height maps but also geometry images, which displace more vertices toward the higher curvature feature parts of the terrain surface such that the surface detail can be well reconstructed with a small number of vertices. The efficiency of the proposed method is proven through experiments on large terrain models. When the screen-space error threshold is set to a pixel, a terrain surface tessellated into 8.5 M triangles is rendered at 110 fps on commodity PCs. [ABSTRACT FROM AUTHOR]