Generalized Preparata codes and 2-resolvable Steiner quadruple systems

We consider generalized Preparata codes with a noncommutative group operation. These codes are shown to induce new partitions of Hamming codes into cosets of these Preparata codes. The constructed partitions induce 2-resolvable Steiner quadruple systems S(n, 4, 3) (i.e., systems S(n, 4, 3) that can be partitioned into disjoint Steiner systems S(n, 4, 2)). The obtained partitions of systems S(n, 4, 3) into systems S(n, 4, 2) are not equivalent to such partitions previously known.     

Tilings of nonorientable surfaces by Steiner triple systems

A Steiner triple system of order n (for short, STS(n)) is a system of three-element blocks (triples) of elements of an n-set such that each unordered pair of elements occurs in precisely one triple. Assign to each triple (i,j,k) ? STS(n) a topological triangle with vertices i, j, and k. Gluing together like sides of the triangles that correspond to a pair of disjoint STS(n) of a special form yields a black-and-white tiling of some closed surface. For each n ≡ 3 (mod 6) we prove that there exist nonisomorphic tilings of nonorientable surfaces by pairs of Steiner triple systems of order n. We also show that for half of the values n ≡ 1 (mod 6) there are nonisomorphic tilings of nonorientable closed surfaces.     

Bootstrapping Inference in the IDP Knowledge Base System

Declarative systems aim at solving tasks by running inference engines on a specification, to free their users from having to specify how a task should be tackled. In order to provide such functionality, declarative systems themselves apply complex reasoning techniques, and, as a consequence, the development of such systems can be laborious work. In this paper, we demonstrate that the declarative approach can be applied to develop such systems, by tackling the tasks solved inside a declarative system declaratively. In order to do this, a meta-level representation of those specifications is often required. Furthermore, by using the language of the system for the meta-level representation, it opens the door to bootstrapping: an inference engine can be improved using the inference it performs itself.One such declarative system is the IDP knowledge base system, based on the language \(\rm FO(\cdot)^{\rm IDP}\), a rich extension of first-order logic. In this paper, we discuss how \(\rm FO(\cdot)^{\rm IDP}\) can support meta-level representations in general and which language constructs make those representations even more natural. Afterwards, we show how meta-\(\rm FO(\cdot)^{\rm IDP}\) can be applied to bootstrap its model expansion inference engine. We discuss the advantages of this approach: the resulting program is easier to understand, easier to maintain, and more flexible.     

Almost cover-free codes

We say that an s-subset of codewords of a code X is (s, l)-bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be (s, l)-bad. A binary code X is called a disjunctive (s, l) cover-free (CF) code if X does not contain (s, l)-bad subsets. We consider a probabilistic generalization of (s, l) CF codes: we say that a binary code is an (s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are (s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of (s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log₂ e/(le).     

A parallel pattern for iterative stencil + reduce

We advocate the Loop-of-stencil-reduce pattern as a means of simplifying the implementation of data-parallel programs on heterogeneous multi-core platforms. Loop-of-stencil-reduce is general enough to subsume map, reduce, map-reduce, stencil, stencil-reduce, and, crucially, their usage in a loop in both data-parallel and streaming applications, or a combination of both. The pattern makes it possible to deploy a single stencil computation kernel on different GPUs. We discuss the implementation of Loop-of-stencil-reduce in FastFlow, a framework for the implementation of applications based on the parallel patterns. Experiments are presented to illustrate the use of Loop-of-stencil-reduce in developing data-parallel kernels running on heterogeneous systems.     

Tracking frequent items over distributed probabilistic data

Tracking frequent items (also called heavy hitters) is one of the most fundamental queries in real-time data due to its wide applications, such as logistics monitoring, association rule based analysis, etc. Recently, with the growing popularity of Internet of Things (IoT) and pervasive computing, a large amount of real-time data is usually collected from multiple sources in a distributed environment. Unfortunately, data collected from each source is often uncertain due to various factors: imprecise reading, data integration from multiple sources (or versions), transmission errors, etc. In addition, due to network delay and limited by the economic budget associated with large-scale data communication over a distributed network, an essential problem is to track the global frequent items from all distributed uncertain data sites with the minimum communication cost. In this paper, we focus on the problem of tracking distributed probabilistic frequent items (TDPF). Specifically, given k distributed sites S = {S ₁, … , S _k }, each of which is associated with an uncertain database \(\mathcal {D}_{i}\) of size n _i , a centralized server (or called a coordinator) H, a minimum support ratio r, and a probabilistic threshold t, we are required to find a set of items with minimum communication cost, each item X of which satisfies P r(s u p(X) ≥ r × N) > t, where s u p(X) is a random variable to describe the support of X and \(N={\sum }_{i=1}^{k}n_{i}\). In order to reduce the communication cost, we propose a local threshold-based deterministic algorithm and a sketch-based sampling approximate algorithm, respectively. The effectiveness and efficiency of the proposed algorithms are verified with extensive experiments on both real and synthetic uncertain datasets.     

One-Nonterminal Conjunctive Grammars over a Unary Alphabet

Systems of equations of the form X _i =φ _i (X ₁,…,X _n ) (1≤ i ≤ n) are considered, in which the unknowns are sets of natural numbers. Expressions φ _i may contain the operations of union, intersection and elementwise addition \(S+T=\{m+n\mid m\in S\), n∈T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.     

On resol vability of Steine r systems S( v = 2m, 4, 3) of rank r ≤ v − m + 1 o ve r $$\mathbb{F}_2 $$

Two new constructions of Steiner quadruple systems S(v, 4, 3) are given. Both preserve resolvability of the original Steiner system and make it possible to control the rank of the resulting system. It is proved that any Steiner system S(v = 2 ^m , 4, 3) of rank r ≤ v ? m + 1 over F₂ is resolvable and that all systems of this rank can be constructed in this way. Thus, we find the number of all different Steiner systems of rank r = v ? m + 1.     

Resource allocation in cooperative cognitive radio networks towards secure communications for maritime big data systems

In this paper, an innovative framework labeled as cooperative cognitive maritime big data systems (CCMBDSs) on the sea is developed to provide opportunistic channel access and secure communication. A two-phase frame structure is applied to let Secondary users (SUs) entirely utilize the transmission opportunities for a portion of time as the reward by cooperation with Primary users (PUs). Amplify-and-forward (AF) relaying mode is exploited in SU nodes, and Backward induction method based Stackelberg game is employed to achieve optimal determination of SU, power consumption and time portion of cooperation both for non-secure communication scenario and secure communication. Specifically, a jammer-based secure communications scheme is developed to maximize the secure utility of PU, to confront of the situation that the eavesdropper could overheard the signals from SU _i and the jammer. Close-form solutions for the best access time portion as well as the power for SU _i and jammer are derived to realize the Nash Equilibrium. Simulation results validate the effectiveness of our proposed strategy.     

Tackling heterogeneous concept drift with the Self-Adjusting Memory (SAM)

Instance matching is the problem of determining whether two instances describe the same real-world entity or not. Instance matching plays a key role in data integration and data cleansing, especially for building a knowledge base. For example, we can regard each article in encyclopedias as an instance, and a group of articles which refers to the same real-world object as an entity. Therefore, articles about Washington should be distinguished and grouped into different entities such as Washington, D.C (the capital of the USA), George Washington (first president of the USA), Washington (a state of the USA), Washington (a village in West Sussex, England), Washington F.C. (a football club based in Washington, Tyne and Wear, England), Washington, D.C. (a novel). In this paper, we proposed a novel instance matching approach Active Instance Matching with Pairwise Constraints, which can bring the human into the loop of instance matching. The proposed approach can generate candidate pairs in advance to reduce the computational complexity, and then iteratively select the most informative pairs according to the uncertainty, influence, connectivity and diversity of pairs. We evaluated our approach one two publicly available datasets AMINER and WIDE-NUS and then applied our approach to the two large-scale real-world datasets, Baidu Baike and Hudong Baike, to build a Chinese knowledge base. The experiments and practice illustrate the effectiveness of our approach.     

Determining Steady-State Characteristics of Some Queuing Systems with Erlangian Distributions

This article proposes a method to study M / E _s / 1 / m, E _r E _s /1 / m, and E _r / M / n / m queuing systems including the case when m = ∞. Recurrence relations are obtained to compute the stationary distribution of the number of customers in a system and its steady-state characteristics. The developed algorithms are tested on examples using simulation models constructed with the help of the GPSS World tools.     

Least common container of tree pattern queries and its applications

Tree patterns represent important fragments of XPath. In this paper, we show that some classes \({\mathcal{C}}\) of tree patterns exhibit such a property that, given a finite number of compatible tree patterns \({P_1, \ldots, P_n\in \mathcal{C}}\), there exists another pattern P such that P ₁, . . . , P _n are all contained in P, and for any tree pattern \({Q\in \mathcal{C}}\), P ₁, . . . , P _n are all contained in Q if and only if P is contained in Q. We experimentally demonstrate that the pattern P is usually much smaller than P ₁, . . . , P _n combined together. Using the existence of P above, we show that testing whether a tree pattern, P, is contained in another, \({Q\in \mathcal{C}}\), under an acyclic schema graph G, can be reduced to testing whether P _G , a transformed version of P, is contained in Q without any schema graph, provided that the distinguished node of P is not labeled *. We then show that, under G, the maximal contained rewriting (MCR) of a tree pattern Q using a view V can be found by finding the MCR of Q using V _G without G, when there are no *-nodes on the distinguished path of V and no *-nodes in Q.     

Optimisation of a non linear fuzzy function

 We present a first study concerning the optimization of a non linear fuzzy function f depending both on a crisp variable and a fuzzy number: therefore the function value is a fuzzy number. More specifically, given a real fuzzy number ?∈F and the function f(a,x):R ²→R, we consider the fuzzy extension induced by f, f˜ : F × R → F, f˜(?,x) = Y˜. If K is a convex subset of R, the problem we consider is “maximizing”f˜(?,x), xˉ∈ K. The first problem is the meaning of the word “maximizing”: in fact it is well-known that ranking fuzzy numbers is a complex matter. Following a general method, we introduce a real function (evaluation function) on real fuzzy numbers, in order to get a crisp rating, induced by the order of the real line. In such a way, the optimization problem on fuzzy numbers can be written in terms of an optimization problem for the real-valued function obtained by composition of f with a suitable evaluation function. This approach allows us to state a necessary and sufficient condition in order that ∈K is the maximum for f˜ in K, when f(a,x) is convex-concave (Theorem 4.1).     

Flash as cache extension for online transactional workloads

Considering the current price gap between hard disk and flash memory SSD storages, for applications dealing with large-scale data, it will be economically more sensible to use flash memory drives to supplement disk drives rather than to replace them. This paper presents FaCE, which is a new low-overhead caching strategy that uses flash memory as an extension to the RAM buffer of database systems. FaCE aims at improving the transaction throughput as well as shortening the recovery time from a system failure. To achieve the goals, we propose two novel algorithms for flash cache management, namely multi-version FIFO replacement and group second chance. This was possible due to flash write optimization as well as disk access reduction obtained by the FaCE caching methods. In addition, FaCE takes advantage of the nonvolatility of flash memory to fully support database recovery by extending the scope of a persistent database to include the data pages stored in the flash cache. We have implemented FaCE in the PostgreSQL open-source database server and demonstrated its effectiveness for TPC-C benchmarks in comparison with existing caching methods such as Lazy Cleaning and Linux Bcache.     

Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

Cache-Oblivious R-Trees

We develop a cache-oblivious data structure for storing a set S of N axis-aligned rectangles in the plane, such that all rectangles in S intersecting a query rectangle or point can be found efficiently. Our structure is an axis-aligned bounding-box hierarchy and as such it is the first cache-oblivious R-tree with provable performance guarantees. If no point in the plane is contained in more than a constant number of rectangles in S, we can construct, for any constant ε, a structure that answers a rectangle query using \(O(\sqrt{N/B}+T/B)\) memory transfers and a point query using O((N/B) ^ε ) memory transfers, where T is the number of reported rectangles and B is the block size of memory transfers between any two levels of a multilevel memory hierarchy. We also develop a variant of our structure that achieves the same performance on input sets with arbitrary overlap among the rectangles. The rectangle query bound matches the bound of the best known linear-space cache-aware structure.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

The weight-constrained maximum-density subtree problem and related problems in trees

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _v ,w _v ), where value val _v is a real number and weight w _v is a non-negative integer, the density of T is defined as \(\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}\). A subtree of T is a connected subgraph (V′,E′) of T, where V′?V and E′?E. Given two integers w _min? and w _max?, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _min?≤∑_v∈V′ w _v ≤w _max?. In this paper, we first present an O(w _max? n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S?V, we also present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.     

On the Price of Heterogeneity in Parallel Systems

Suppose we have a parallel or distributed system whose nodes have limited capacities, such as processing speed, bandwidth, memory, or disk space. How does the performance of the system depend on the amount of heterogeneity of its capacity distribution? We propose a general framework to quantify the worst-case effect of increasing heterogeneity in models of parallel systems. Given a cost function g(C,W) representing the system’s performance as a function of its nodes’ capacities C and workload W (such as the makespan of an optimum schedule of jobs W on machines C), we say that g has price of heterogeneity α when for any workload, cost cannot increase by more than a factor α if node capacities become arbitrarily more heterogeneous. The price of heterogeneity also upper bounds the “value of parallelism”: the maximum benefit obtained by increasing parallelism at the expense of decreasing processor speed. We give constant or logarithmic bounds on the price of heterogeneity of several well-known job scheduling and graph degree/diameter problems, indicating that in many cases, increasing heterogeneity can never be much of a disadvantage.     

A linear-time algorithm for finding Hamiltonian (<Emphasis Type="Italic">s</Emphasis>, <Emphasis Type="Italic">t</Emphasis>)-paths in odd-sized rectangular grid graphs with a rectangular hole

A grid graph \(G_{\mathrm{g}}\) is a finite vertex-induced subgraph of the two-dimensional integer grid \(G^\infty \). A rectangular grid graph R(m, n) is a grid graph with horizontal size m and vertical size n. A rectangular grid graph with a rectangular hole is a rectangular grid graph R(m, n) such that a rectangular grid subgraph R(k, l) is removed from it. The Hamiltonian path problem for general grid graphs is NP-complete. In this paper, we give necessary conditions for the existence of a Hamiltonian path between two given vertices in an odd-sized rectangular grid graph with a rectangular hole. In addition, we show that how such paths can be computed in linear time.