Browsing by Author "He, Meng"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Fast and Compact Planar Embeddings
    (2017) Ferres, Leo; Fuentes-Sepúlveda, José; Gagie, Travis; He, Meng
    There are many representations of planar graphs, but few are as elegant as Turan's (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multiedges, and can store any specified embedding. Its main disadvantage has been that "it does not allow efficient searching" (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turan's representation such that it supports fast navigation while retaining simplicity. As a consequence of the inherited simplicity, we offer the first efficient parallel construction of a compact encoding of a planar graph embedding. Our experimental results show that the resulting representation uses about 6 bits per edge in practice, supports basic navigation operations within a few microseconds, and can be built sequentially at a rate below 1 microsecond per edge, featuring a linear speedup with a parallel efficiency around 50% for large datasets. (C) 2020 Elsevier B.V. All rights reserved
  • Thumbnail Image
    Item
    Fast and compact planar embeddings
    (2020) Ferres, Leo; Fuentes-Sepúlveda, José; Gagie, Travis; He, Meng; Navarro, Gonzalo
    There are many representations of planar graphs, but few are as elegant as Turán’s (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multiedges, and can store any specified embedding. Its main disadvantage has been that “it does not allow efficient searching” (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turán’s representation such that it supports fast navigation while retaining simplicity. As a consequence of the inherited simplicity, we offer the first efficient parallel construction of a compact encoding of a planar graph embedding. Our experimental results show that the resulting representation uses about 6 bits per edge in practice, supports basic navigation operations within a few microseconds, and can be built sequentially at a rate below 1 microsecond per edge, featuring a linear speedup with a parallel efficiency around 50% for large datasets.
  • Thumbnail Image
    Item
    Fast and Compact Planar Embeddings
    (2019) Ferres, Leo; Fuentes-Sepúlveda, José; Gagie, Travis; He, Meng; Navarro, Gonzalo
    There are many representations of planar graphs, but few are as elegant as Turán’s (1984): it is simple and practical, uses only 4 bits per edge, can handle self-loops and multi-edges, and can store any specified embedding. Its main disadvantage has been that “it does not allow efficient searching” (Jacobson, 1989). In this paper we show how to add a sublinear number of bits to Turán’s representation such that it supports fast navigation while retaining simplicity. As a consequence of the inherited simplicity, we offer the first efficient parallel construction of a compact encoding of a planar graph embedding. Our experimental results show that the resulting representation uses about 6 bits per edge in practice, supports basic navigation operations within a few microseconds, and can be built sequentially at a rate below 1 microsecond per edge, featuring a linear speedup with a parallel efficiency around 50% for large datasets.
  • Thumbnail Image
    Item
    Parallel construction of succinct trees
    (2017) Fuentes-Sepúlveda, José; Ferres, Leo; He, Meng; Zeh, Norbert
    Succinct representations of trees are an elegant solution to make large trees fit in main memory while still supporting navigational operations in constant time. However, their construction time remains a bottleneck. We introduce two parallel algorithms that improve the state of the art in succinct tree construction. Our results are presented in terms of work, the time needed to execute a parallel computation using one thread, and span, the minimum amount of time needed to execute a parallel computation, for any amount of threads. Given a tree on n nodes stored as a sequence of balanced parentheses, our first algorithm builds a succinct tree representation with O(n) work, O(lg⁡n) span and supports a rich set of operations in O(lg⁡n) time. Our second algorithm improves the query support. It constructs a succinct representation that supports queries in O(c) time, taking O(n+nlgc⁡nlg⁡(nlgc⁡n)+cc) work and O(c+lg⁡(ncclgc⁡n)) span, for any positive constant c. Both algorithms use O(nlg⁡n) bits of working space. In experiments using up to 64 cores on inputs of different sizes, our first algorithm achieved good parallel speed-up. We also present an algorithm that takes O(n) work and O(lg⁡n) span to construct the balanced parenthesis sequence of the input tree required by our succinct tree construction algorithm.

Implementado por OpenGeek Services