An efficient algorithm for partially matched services in internet of services

Internet of Things (IoT) connects billions of devices in an Internet-like structure. Each device encapsulated as a real-world service which provides functionality and exchanges information with other devices. This large-scale information exchange results in new interactions between things and people. Unlike traditional web services, internet of services is highly dynamic and continuously changing due to constant degrade, vanish and possibly reappear of the devices, this opens a new challenge in the process of resource discovery and selection. In response to increasing numbers of services in the discovery and selection process, there is a corresponding increase in number of service consumers and consequent diversity of quality of service (QoS) available. Increase in both sides’ leads to the diversity in the demand and supply of services, which would result in the partial match of the requirements and offers. This paper proposed an IoT service ranking and selection algorithm by considering multiple QoS requirements and allowing partially matched services to be counted as a candidate for the selection process. One of the applications of IoT sensory data that attracts many researchers is transportation especially emergency and accident services which is used as a case study in this paper. Experimental results from real-world services showed that the proposed method achieved significant improvement in the accuracy and performance in the selection process.     

Scrolling partially ordered event displays

Understanding the partial-order relationship between events is critical to understand the behaviour of a distributed or parallel application. Many problems need to be solved in order to provide an accurate and useful display of a large partial order, such as will occur during the execution of any non-trivial application. A display will most likely resemble a process-time diagram, but the “time” axis does not have a fixed interpretation. Flexibility in positioning events along this axis allows more-useful displays to be created, but also greatly complicates scrolling through the event history. This paper first discusses the properties that are arguably desirable for such scrolling and then presents an algorithm that provides scrolling with those properties.     

Segmental partially ordered generalized patterns

We continue the study of partially ordered generalized patterns (POGPs) considered in [E. Babson, E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Séminaire Lotharingien de Combinatoire, 2000, B44b:18pp] for permutations and in [A. Burstein, T. Mansour, Words restricted by patterns with at most 2 distinct letters, Electron. J. Combin. 9 (2) (2002) #R3] for words. We deal with segmental POGPs (SPOGPs). We state some general results and treat a number of patterns of length 4. We prove a result from [S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math. 260 (2003) 89–100] in a much simpler way and also establish a connection between SPOGPs and walks on lattice points starting from the origin and remaining in the positive quadrant. We give a combinatorial interpretation of the powers of the (generalized) Fibonacci numbers. The entire distribution of the maximum number of non-overlapping occurrences of a generalized pattern with no dashes in permutations or words studied in [S. Kitaev, Partially ordered generalized patterns, Discrete Math. to appear, S. Kitaev, T. Mansour, Partially ordered generalized patterns and k-ary words, Ann. Combin. 7 (2003) 191–200], respectively, has its counterpart in case of SPOGPs.     

Scheduling problems with partially ordered jobs

Scheduling problems with given precedence constraints (with partially ordered jobs) are considered. A review of the results obtained in this area by the members of Minsk Scheduling Theory school created by V.S. Tanaev is done.     

Logic modeling with partially ordered preferences

Logic modeling is the use of formal logic as a modeling tool for problems of interest to management science. Based on a review of the logic of preference literature this paper presents five axioms for reasoning about a decision maker's preferences. A semantics of situations is adopted for the symbols used. Both logical deduction and a modification of dynamic programming are proposed for the problem of selecting preferred states of affairs over time. Finally, a sketch of an implementation in Prolog is presented.     

Abelian extensions of partially ordered partial monoids

In this paper we introduce the notion of a partially ordered partial monoid (po PM), and we study extensions of cancellative po PMs by abelian groups. We concentrate on the so-called central extensions, and prove that every such extension is an F-product of a po PM by an abelian group defined by a cocycle $f.$ Like in partially ordered groups, the extension can be ordered by means of special sets. We also compare extensions of po PMs with the extensions of their universal groups.     

Sequential decision making with partially ordered preferences

This paper presents new insights and novel algorithms for strategy selection in sequential decision making with partially ordered preferences; that is, where some strategies may be incomparable with respect to expected utility. We assume that incomparability amongst strategies is caused by indeterminacy/imprecision in probability values. We investigate six criteria for consequentialist strategy selection: Γ-Maximin, Γ-Maximax, Γ-Maximix, Interval Dominance, Maximality and E-admissibility. We focus on the popular decision tree and influence diagram representations. Algorithms resort to linear/multilinear programming; we describe implementation and experiments.     

A note on partially ordered tree automata

A recent paper by Bouajjani, Muscholl and Touili shows that the class of languages accepted by partially ordered word automata (or equivalently accepted by Σ₂-formulae) is closed under semi-commutation and it suggested the following open question: can we extend this result to tree languages? This problem can be addressed by proving (1) that the class of tree regular languages accepted by Σ₂ formulae is strictly included in the class of languages accepted by partially ordered automata, and (2) that Bouajjani and the others results cannot be extended to tree.     

A distributed self-scheduler for partially ordered tasks

Large scale scientific applications such as weather modelling and continuous simulation require the orders of magnitude performance improvement available with the new generation of parallel vector supercomputers such as the Floating Point Systems T Series. Many of these applications exhibit a high degree of parallelism, much of which can be expressed as computational tasks which are of varying size and degrees of dependence on one another, and can be partially ordered for execution. DeSPOT (A Distributed Self-Scheduler for Partially Ordered Tasks) is an algorithm for the dynamic distribution of such non-uniform tasks to achieve automatic load balancing on a distributed memory hypercube multiprocessor. This paper describes the DeSPOt algorithm and presents its performance characteristics of various test cases using result timings on the FPS T 20.     

Application of statistical inference for partially ordered hypotheses

In quality control and decision support systems, ranking and selection are very important, because we often encounter situations in which we need to rank several objects and to select some out of them. We investigate a problem of ranking k( 2) independent normal populations and selecting superior or inferior m(≤ k) out of them. The purpose of this paper is to formulate the problem as that of statistical hypothesis test, and to give critical values for practical use. We present computational methods for the level probabilities, which are needed for finding the critical values.     

Some classes of automata as partially ordered sets

A class of automata is considered as a partially ordered set by homomorphism relation. We show first that some classes of automata. e.g., quasiperfect automata, perfect automata and strongly cofinal automata, are lattices, and other classes, e.g., strongly connected automata, cyclic automata and cofinal automata, are not lattices. At the same time, we give algorithms for computing the least upper bound and the greatest lower bound of given two elements in each class which forms a lattice.     

On Herglotz theorem in partially ordered vector spaces

Herglotz theorem is generalized for a monotone σ-complete partially ordered vector space.     

Operator factorization on partially ordered Hilbert resolution spaces

The classical study of factorization of operators along a linearly ordered chain of orthoprojectors is extended to the more general context of partially ordered chains. With this extension the factorization theory becomes relevant to stochastic approximation, filtering and control of multidimensional systems.     

Discovering anomalous frequent patterns from partially ordered event logs

Conformance checking allows organizations to compare process executions recorded by the IT system against a process model representing the normative behavior. Most of the existing techniques, however, are only able to pinpoint where individual process executions deviate from the normative behavior, without considering neither possible correlations among occurred deviations nor their frequency. Moreover, the actual control-flow of the process is not taken into account in the analysis. Neglecting possible parallelisms among process activities can lead to inaccurate diagnostics; it also poses some challenges in interpreting the results, since deviations occurring in parallel behaviors are often instantiated in different sequential behaviors in different traces. In this work, we present an approach to extract anomalous frequent patterns from historical logging data. The extracted patterns can exhibit parallel behaviors and correlate recurrent deviations that have occurred in possibly different portions of the process, thus providing analysts with a valuable aid for investigating nonconforming behaviors. Our approach has been implemented as a plug-in of the ESub tool and evaluated using both synthetic and real-life logs.     

A segmentation-based algorithm for large-scale partially ordered monotonic regression

Monotonic regression (MR) is an efficient tool for estimating functions that are monotonic with respect to input variables. A fast and highly accurate approximate algorithm called the GPAV was recently developed for efficient solving large-scale multivariate MR problems. When such problems are too large, the GPAV becomes too demanding in terms of computational time and memory. An approach, that extends the application area of the GPAV to encompass much larger MR problems, is presented. It is based on segmentation of a large-scale MR problem into a set of moderate-scale MR problems, each solved by the GPAV. The major contribution is the development of a computationally efficient strategy that produces a monotonic response using the local solutions. A theoretically motivated trend-following technique is introduced to ensure higher accuracy of the solution. The presented results of extensive simulations on very large data sets demonstrate the high efficiency of the new algorithm.     

Maximum elements of a partially ordered set of binary vectors

A method is described for determining the maximum elements of a partially ordered set of binary vectors. The method uses a fast conjunctive transform and is computationally more efficient than enumerative methods.Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 165–166, July–August, 1991.     

Synthesizing optimization algorithms for scheduling partially ordered set of problems

We consider the issues of optimal algorithms synthesis in the scheduling theory from a set of heuristic algorithms with low computational complexity. Optimal algorithm is derived which includes no more than seven tasks with identical duration of operations.