Search

This paper will demonstrate a novel method for consolidating data in an engineered hypercube network for the purpose of optimizing query processing. Query processing typically calls for merging data collected from a small subset of server nodes in a network. This poses the problem of managing efficiently the exchange of data between processing nodes to complete some relational data operation. The method developed here is designed to minimize data transfer, measured as the product of data quantity and network distance, by delegating the processing to a node that is relatively central to the subset. A hypercube not only supports simple computation of network distance between nodes, but also allows for identifying a node to serve as the center for any data consolidation operations. We will show how the consolidation process can be performed by selecting a subgraph of a complex network to simplify the selection of a central node and thus facilitate the computations required. We will also show a prototype implementation of a hypercube using Software-Defined Networking to support query optimization in a distributed heterogeneous database system, making use of network distance information and data quantity.

Overlay networks are logical networks embedded in physical substrate networks. They are useful for supporting specialized applications involving computation and information exchange among subsets of users. This paper examines the characteristics of overlays that make them suitable for different applications in dynamic, distributed database environments. One such characteristic is the ease with which distances between nodes can be calculated. Examples of overlay graph structures that exhibit certain desirable characteristics include the hypercube, toroidal grid graph and the Kautz graph. Applications involving mobile elements are examined, and a system designed to support comparative analysis of the performance of different overlay structures is discussed.

An interconnection network is a programmable system that serves to transport data or messages amongst network components and/or terminals. A network’s topology is typically modeled by a graph. A path of order k in a graph G is a sequence of k distinct vertices, denoted by \(P_k = \langle v_1,v_2,\cdots ,v_k\rangle \), in which any two consecutive vertices are adjacent. The connectivity is a classic index to assess the level of network reliability and fault tolerance. For \(k \ge 2\), a set F of vertex subsets of G is a \(P_k\)-cut if \(G-F\) is disconnected, and each element of F happens to induce a \(P_k\)-subgraph in G. A connected graph G is super \(P_k\)-connected if the smallest component of \(G-F\) is a singleton for every minimum \(P_k\)-cut F of G. A network with smaller diameter can reduce its communication delay in a worst-case perspective. The crossed cube \(CQ_n\) is a hypercube variant whose diameter is about one half of that of the hypercube. This paper is inspired to discover whether \(CQ_n\) is super \(P_k\)-connected for \(k=2,3,4\).

Interconnection networks are emerging as an approach to solving system-level communication problems. A network may be modeled by a graph whose vertices represent the nodes, and whose edges represent communication links. For any vertex v in a graph G, let \(N_G(v)\) denote the open neighborhood of v, and let \(N_G[v] = \{v\} \cup N_G(v)\) denote the closed neighborhood of v. The connectivity has long been a classic factor that characterizes both network reliability and fault tolerance. A set F of vertex subsets of G is called a neighborhood-cut if \(G-F\) is disconnected, and each element of F happens to be the closed neighborhood of some vertex in G. The neighborhood-connectivity of G is the minimum cardinality over all neighborhood-cuts in G. The locally twisted cube network is a promising alternative to hypercube, which is well known as one of the most popular network architectures for high-performance computing. In this paper, we determine the exact neighborhood-connectivity of locally twisted cubes.

We study the problem of learning a finite union of integer (axis-aligned) hypercubes over the d-dimensional integer lattice, i.e., whose edges are parallel to the coordinate axes. This is a natural generalization of the classic problem in the computational learning theory of learning rectangles. We provide a learning algorithm with access to a minimally adequate teacher (i.e. membership and equivalence oracles) that solves this problem in polynomial-time, for any fixed dimension d. Over a non-fixed dimension, the problem subsumes the problem of learning DNF boolean formulas, a central open problem in the field. We have also provided extensions to handle infinite hypercubes in the union, as well as showing how subset queries could improve the performance of the learning algorithm in practice. Our problem has a natural application to the problem of monadic decomposition of quantifier-free integer linear arithmetic formulas, which has been actively studied in recent years. In particular, a finite union of integer hypercubes correspond to a finite disjunction of monadic predicates over integer linear arithmetic (without modulo constraints). Our experiments suggest that our learning algorithms substantially outperform the existing algorithms.

Adding self-loops at each vertex of a graph improves the performance of quantum walks algorithms over loopless algorithms. Many works approach quantum walks to search for a single marked vertex. In this article, we experimentally address several problems related to quantum walk in the hypercube with self-loops to search for multiple marked vertices. We first investigate the quantum walk in the loopless hypercube. We saw that neighbor vertices are also amplified and that approximately $1/2$ of the system energy is concentrated in them. We show that the optimal value of $l$ for a single marked vertex is not optimal for multiple marked vertices. We define a new value of $l = (n/N)\cdot k$ to search multiple marked vertices. Next, we use this new value of $l$ found to analyze the search for multiple marked vertices non-adjacent and show that the probability of success is close to $1$. We also use the new value of $l$ found to analyze the search for several marked vertices that are adjacent and show that the probability of success is directly proportional to the density of marked vertices in the neighborhood. We also show that, in the case where neighbors are marked, if there is at least one non-adjacent marked vertex, the probability of success increases to close to $1$. The results found show that the self-loop value for the quantum walk in the hypercube to search for several marked vertices is $l = (n / N) \cdot k $.

As the scale of systems increased, the probability of a single node failure also increasing. Therefore, exploring the reliability of complex systems is crucial to the operation of the network. Few of Scholar focus on the reliability of subsystems of irregular networks. While exchanged hypercube EH(s, t) was firstly proposed by Loh et al. [9] and it is a irregular network. In this paper, we evaluate the reliability of EH(s, t) by studying the reliability of subsystems \(EH(s-1,t-1)\). Specifically, we use the PIE (Principle of Inclusion-Exclusion) method to derive the approximate value of the reliability and the upper bound with the intersection of no more than 3 subgraphs \(EH(s-1,t-1)\) under the probability fault model.

The b-chromatic number b(G) of a graph G is the maximum k for which G has a proper vertex coloring using k colors such that each color class contains at least one vertex adjacent to a vertex of every other color classes. In this paper, we mainly investigate on one of the open problems given in [1]. As a consequence, we obtain an upper bound for the b-chromatic number of some powers of hypercube. This turns out to be the improvement of the existing bounds.

Structures of opposition, such as the hexagon and different cubes, derived from the square of opposition of ancient logic, have for more than a decade shown their interest in the analysis of various frameworks for the representation and processing of information (possibly pervaded with uncertainty). The use of a renewed and less constrained vision of the structures of opposition leads in this article to consider a general cube and a hypercube of opposition applicable to binary or gradual settings, which is here exemplified on Sugeno integrals and related integrals

The subgroup discovery problem aims to identify a subset of objects which exhibit interesting characteristics according to a quality measure defined on a target attribute. In this paper, we propose a new optimized approach, called SD-CEDI, which originality consists of extracting subgroups defined on discontinued attribute intervals. The intuition behind this approach is that disjoint intervals allow refining the definition of subgroups and therefore the quality of the subgroups identified. For this purpose, the approach we propose models the search space through a hypercube and aims to slice this hypercube to highlight subgroups. Unlike recent methods that also exploit the concept of hypercubes, the originality of our approach relies on the way it performs the slicing in order to bring out discontinuous attribute intervals. The good performances of the approach are demonstrated by comparing, qualitatively and quantitatively, the results with the main algorithms that are the references in the domain.

The n-dimensional locally twisted cube LTQn, a variation of the hypercube Qn, has the same number of vertices and the same number of edges as Qn, but it has only about half of the diameter of Qn. The existence of the Hamiltonian cycle provides an advantage when implementing algorithms that require a ring structure. In addition, k (≥ 2) edge-disjoint Hamiltonian cycles also provide the edge-fault tolerant Hamiltonicity for the interconnection network. Hung [Theoretical Computer Science 412, 4747–4753, 2011] proved that LTQn with n ⩾ 4 contains two edge-disjoint Hamiltonian cycles, and posted an open problem what is the maximum number of edge-disjoint Hamiltonian cycles in LTQn for n ⩾ 6? In this paper, we show that there exist three edge-disjoint Hamiltonian cycles on LTQn while n ⩾ 6.

According to Courant's theorem, an eigenfunction as\-sociated with the $n$-th eigenvalue $\lambda_n$ has at most $n$ nodal domains. A footnote in the book of Courant and Hilbert, states that the same assertion is true for any linear combination of eigenfunctions associated with eigenvalues less than or equal to $\lambda_n$. We call this assertion the \emph{Extended Courant Property}.\smallskip In this paper, we propose simple and explicit examples for which the extended Courant property is false: convex domains in $\R^n$ (hypercube and equilateral triangle), domains with cracks in $\mathbb{R}^2$, on the round sphere $\mathbb{S}^2$, and on a flat torus $\mathbb{T}^2$.

In order to satisfy the rapidly increasing demand for data volume, large data center networks (DCNs) have been proposed. In 2019, Zhang et al. proposed a new highly scalable DCN architecture named HSDC, which can achieve greater incremental scalability. In this paper, we give the definition of the logical graph of HSDC, named \(H_n\), which can be treated as a compound graph of hypercube and complete graph of the same dimension. First, we prove that the connectivity and tightly super connectivity of \(H_n\) are both n. Then, we give an O(n) routing algorithm to find a shortest path between any two distinct nodes in \(H_n\), and prove the correctness of this algorithm. In fact, we also prove that the distance constructed by this algorithm is no more than \(2d+1\) if \(d

Recently, an explosive increase of demand on space- and time-consuming computation makes the research activities of massively parallel systems enthusiastic. Because in a massively parallel system a huge number of processors cooperate to process tasks by communicating among others, it forms an interconnection network, which is a network that interconnects the processors. By replacing a processor and a link with a vertex and an edge, respectively, many problems regarding communication and/or routing in interconnection networks are reducible to the problems in the graph theory. There have been many topologies proposed for interconnection networks of the massively parallel systems. The hypercube is the most popular topology and many variants were proposed so far. The bicube is a such topology, which can connect the same number of vertices with the same number degree as the hypercube while its diameter is almost half of that of the hypercube keeping the vertex-symmetric property. Therefore, we focus on the bicube and propose a shortest-path routing algorithm. We give a proof of correctness of the algorithm and demonstrate its execution.

Large scale multiprocessor systems or multicomputer systems, taking interconnection networks as underlying topologies, have been widely used in the big data era. System level diagnosis is a primary strategy to identify the faulty processors in multiprocessor systems. To enhance the robustness of networks against processors and links fail simultaneously, Zhu et al. [21] proposed a novel fault diagnostic model, the hybrid PMC diagnostic model, which involves the failing of vertices and edges. In this paper, we determine the diagnosability of the triangle-free regular networks under the hybrid PMC model. As by-products, we apply the general results to the state-of-the-art regular networks, such as hypercube-like network as well as hypercube-based compound network, for example, DQcube, exchanged hypercube, dual cube, half-hypercube, hierarchical cubic network and so on.

The contribution deals with tessellations of convex uniform honeycombs that consist of only Platonic and Archimedean solids. The Archimedean truncated cuboctahedron is the hull of a 3D model of the 9D cube. Its edges have nine different orientations and are parallel to those of solids applied in the considered space-filling mosaics. The segments connecting the centroids of same cells of a tessellation, have also nine different orientations. These belong to two sets and can be the initial edges of two different 3D models of the 9D cube. Sequences of elements along the segments can be considered a compound edge of a compound model. The elements of the models can be marked by different colours according to their shapes, orientation and roles. The above described correlations make it possible to mark all compound models of all considered convex uniform honeycombs and their tessellations in all original ones by colouring. Using the compound models of the solids, new compound solids and tessellations can be built and this process can be repeated. This way, fractals or fractal like structures can be created. Differently oriented planes cut out periodical plane-tiling patterns from the gained spatial tessellations. An intersecting plane moved parallel to itself creates a series of patterns transforming into each other. These can be queued up as frames of an animation or give the level line depictions of the tessellations.

This chapter is concerned with the binary classification task and some simple machine learning algorithms. In studying the machine learning algorithms, it is assumed that the given task is a binary classification, and the regression or the multiple classification may be decomposed into binary classifications. Some simple machine learning algorithms, which are given as threshold rules or hypercubes, will be mentioned for helping understanding the machine learning algorithms. As a typical type of machine learning algorithm, the linear classifier is expressed as a linear equation. This chapter is intended to provide the warming up for understanding the main machine learning algorithms that are covered in Part II and III. This chapter is concerned with the binary classification task and some simple machine learning algorithms. In studying the machine learning algorithms, it is assumed that the given task is a binary classification, and the regression or the multiple classification may be decomposed into binary classifications. Some simple machine learning algorithms, which are given as threshold rules or hypercubes, will be mentioned for helping understanding the machine learning algorithms. As a typical type of machine learning algorithm, the linear classifier is expressed as a linear equation. This chapter is intended to provide the warming up for understanding the main machine learning algorithms that are covered in Parts II and III.

We introduce a general class of time inhomogeneous random walks on the N-hypercube. These random walks are reversible with an N-product Bernoulli stationary distribution and have a property of local change of coordinates in a transition. Several types of representations for the transition probabilities are found. The paper studies cut-off for the mixing time. We observe that for a sub-class of these processes with long range (i.e. non-local) there exists a critical value of the range that allows an almost-perfect mixing in at most two steps. That is, the total variation distance between the two steps transition and stationary distributions decreases to zero as the dimension of the hypercube N increases. Notice that a well-known result (Theorem 1 in [6]) shows that there does not exist a random walk on Abelian groups (such as the hypercube) which mixes perfectly in exactly two steps.

The maximin D-optimal design (MMD-optimal design) and hypercube design (HCD-optimal design) are two robust designs which overcome the problem of design dependence on the unknown parameters. This article considers the robust designs for Poisson mixed models. Given the prior knowledge of the fixed effects parameters, a modification of the two robust design criteria is proposed by applying the number-theoretic methods. The simulated annealing algorithm is used to find the optimal exact designs. The results show that the modified optimal designs perform better in the relative D-efficiency and programming time.

This chapter discusses an alternative approach to performance-driven surrogate modeling, referred to as nested kriging. The technique involves construction of two levels of surrogates. The first-level model maps the objective space into the geometry parameter space of the system in order to establish the surrogate model domain. The domain is defined as the objective space image through the first-level mapping, orthogonally extended to provide it with non-zero “thickness.” Subsequently, the second-level model is constructed over that domain to represent the system outputs. An important advantage of this methodology is that the surrogate domain is a continuous image of a unit hypercube. This enables straightforward uniform allocation of training data samples, as well as convenient optimization of the surrogate model (including easy identification of a good starting point). The discussed methodology is illustrated using practical design cases from antenna and microwave engineering.