rdf-syntax-grammar
mods:
  schema location: http://www.loc.gov/mods/v3 http://www.loc.gov/standards/mods/v3/mods-3-2.xsd
  title info:
    title: Scalable Parallel Algorithms for Massive Scale-free Graphs
  name:
    name part: Pearce, Roger Allan
    role:
      role term: creator
    role:
      role term: author.
  name:
    name part: Amato, Nancy
    role:
      role term: thesis advisor.
  name:
    name part: Texas A & M University
    role:
      role term: degree granting institution.
  type of resource: text
  genre: bibliography
  origin info:
    place:
      place term: txu
    date issued: 2014
    issuance: monographic
  language:
    language term: eng
  physical description:
    form: remote
    extent: 1 online resource.
  abstract: Efficiently storing and processing massive graph data sets is a challenging problem as researchers seek to leverage "Big Data" to answer next-generation scientific questions. New techniques are required to process large scale-free graphs in shared, distributed, and external memory. This dissertation develops new techniques to parallelize the storage, computation, and communication for scale-free graphs with high-degree vertices. Our work facilitates the processing of large real-world graph datasets through the development of parallel algorithms and tools that scale to large computational and memory resources, overcoming challenges not addressed by existing techniques. Our aim is to scale to trillions of edges, and our research is targeted at leadership class supercomputers, clusters with local non-volatile memory, and shared memory systems. We present three novel techniques to address scaling challenges in processing large scale-free graphs. We apply an asynchronous graph traversal technique using prioritized visitor queues that is capable of tolerating data latencies to the external graph storage media and message passing communication. To accommodate large high-degree vertices, we present an edge list partitioning technique that evenly partitions graphs containing high-degree vertices. Finally, we propose a technique we call distributed delegates that distributes and parallelizes the storage, computation, and communication when processing high-degree vertices. The edges of high-degree vertices are distributed, providing additional opportunities for parallelism not present in existing methods. We apply our techniques to multiple graph algorithms: Breadth-First Search, Single Source Shortest Path, Connected Components, K-Core decomposition, Triangle Counting, and Page Rank. Our experimental study of these algorithms demonstrates excellent scalability on supercomputers, clusters with non-volatile memory, and shared memory systems. Our study includes multiple syntheti…
  note: by Roger Pearce.
  note: "Major Subject: Computer Science"
  note: Includes vita.
  note: Doctor of Philosophy Texas A & M University 2013 http://hdl.handle.net/1969.1/151937
  note: Includes bibliographical references.
  note: Text (Dissertation)
  subject:
    topic: Major Computer Science
  subject:
    topic: parallel algorithms
  subject:
    topic: graph algorithms
  subject:
    topic: scale-free graphs
  subject:
    topic: graph partitioning
  identifier: http://hdl.handle.net/1969.1/151937
  record info:
    record content source: TXA
    record creation date: 140530
    record change date: 20151206101243.0
    record identifier: in00003442983
    language of cataloging:
      language term: eng