ICCS 2018 Main Track (MT) Session 11
Time and Date: 9:00 - 10:40 on 13th June 2018
Chair: Paul Manstetten
| An experimental assessment of three point-insertion sequences for 3-D incremental Delaunay tessellations [abstract]
Abstract: Currently, state-of-the-art algorithms for generating 3-D Delaunay tessellations are incremental. Thus, their execution costs depend on the order of point insertion. This work evaluates three point-insertion sequences in incremental algorithms for generating 3-D Delaunay tessellations. Specifically, an incremental algorithm with point-insertion order given by the cut-longest-edge kd-tree is evaluated against the BRIO-Hilbert order in conjunction with spatial middle and median policies employed in the 4.11 version of the Computational Geometry Algorithms Library. The results of execution and storage costs of these three algorithms are analyzed experimentally. It follows that the incremental algorithm with a point-insertion sequence in the order given by the BRIO-Hilbert order with spatial middle policy employed in the latest version of the Computational Geometry Algorithms Library shows lower execution and storage costs than the two other algorithms evaluated.
|Sanderson L. Gonzaga de Oliveira, Diogo T. Robaina, Diego N. Brandão, Mauricio Kischinhevsky and G. Oliveira
| Learning Knowledge Graph Embeddings via Generalized Hyperplanes [abstract]
Abstract: For knowledge graph completion, translation-based methods such as Trans(E and H) are promising, which embed knowledge graphs into continuous vector spaces and construct translation operation between head and tail entities. However, TransE and TransH still have limitations in preserving mapping properties of complex relation facts for knowledge graphs. In this paper, we propose a novel translation-based method called translation on generalized hyperplanes (TransGH), which extends TransH by defining a generalized hyperplane for entities projection. TransGH projects head and tail embeddings from a triplet into a generalized relation-specific hyperplane determined by a set of basis vectors, and then fulfills translation operation on the hyperplane. Compared with TransH, TransGH can capture more fertile interactions between entities and relations, and simultaneously has strong expression in mapping properties for knowledge graphs. Experimental results on two tasks, link prediction and triplet classification, show that TransGH can significantly outperform the state-of-the-art embedding methods.
|Qiannan Zhu, Xiaofei Zhou, Jianlong Tan, Ping Liu and Li Guo
| Fast Higher-Order Functions for Tensor Calculus with Tensors and Subtensors [abstract]
Abstract: Tensors analysis has become a popular tool for solving problems in computational neuroscience, pattern recognition and signal processing. Similar to the two-dimensional case, algorithms for multidimensional data consist of basic operations accessing only a subset of tensor data. With multiple offsets and step sizes, basic operations for subtensors require sophisticated implementations even for entrywise operations. In this work, we discuss the design and implementation of optimized higher-order functions that operate entrywise on tensors and subtensors with any non-hierarchical storage format and arbitrary number of dimensions. We propose recursive multi-index algorithms with reduced index computations and additional optimization techniques such as function inlining with partial template specialization. We show that single-index implementations of higher-order functions with subtensors introduce a runtime penalty of an order of magnitude than the recursive and iterative multi-index versions. Including data- and thread-level parallelization, our optimized implementations reach 68% of the maximum throughput of an Intel Core i9-7900X. In comparison with other libraries, the average speedup of our optimized implementations is up to 5x for map-like and more than 9x for reduce-like operations. For symmetric tensors we measured an average speedup of up to 4x.
|Cem Bassoy and Volker Schatz
| The t-modified self-shrinking generator [abstract]
Abstract: Pseudo-random sequences exhibit interesting properties with application in many and distinct areas ranging from reliable communications to number generation or cryptography. Inside the family of decimation-based sequence generators, the modified self-shrinking generator (an improved version of the self-shrinking generator) is one of its best-known elements. In fact, such a generator divides the PN-sequence produced by a maximum-length LFSR into groups of three bits. When the sum of the first two bits in a group is one, then the generator returns the third bit, otherwise the bit is discarded. In this work, we introduce a generalization of this generator, where the PN-sequence is divided into groups of t bits, t ≥ 3. It is possible to check that the properties of the output sequences produced by this family of generators have the same or better properties than those of the classic modified self-shrunken sequences. Moreover, the number of sequences generated by this new family with application in stream cipher cryptography increases dramatically.
|Sara D. Cardell and Amparo Fúster-Sabater
| Simulating Negotiation-based Cloud Markets [abstract]
Abstract: Today, the so called supermarket approach is used for trading Cloud services on Cloud markets. Thereby, consumers purchase Cloud services at fixed prices without negotiation. More dynamic Cloud markets are emerging as e.g. the recent development of the Amazon EC2 spot market shows - with spot blocks and spot fleet management. Hence, autonomous Bazaar-based negotiations are a promising approach for trading Cloud services on future Cloud markets. Thereby, market participants negotiate the characteristics of Cloud services which are described in Service Level Agreements (SLAs). Specifications such as the WS-Agreement Negotiation standard foster the development of such Bazaar-based Cloud markets. In this paper we present a scientific simulation environment for the simulation of Bazaar-based Cloud markets which conforms to the WS-Agreement Negotiation standard. A two-stepped process is required for using the simulation environment: first consumers, intermediaries and providers have to be created, then strategies have to be assigned to them before the result of the simulation can be analyzed. The aim of the simulation environment is to support market participants during the evaluation of their negotiation strategies.
|Benedikt Pittl, Werner Mach and Erich Schikuta