Digital CC: Colorado College's Institutional Repository

Contacting Tutt Library
  • Circulation Desk: 389-6184
  • Reference Desk: 389-6662
  • Email | IM a Librarian

High Performance Persistent Graphs

by Moody, John




Media Files
Creator
Moody, John
Date Created
2016-05
Date Issued
2016-05
Place
Colorado Springs, Colorado
Language
  • English
Subject
Topic
  • computers
  • graphs
  • data
  • insectoid creatures
Genre
  • thesis
Abstract

Persistent data structures allow large and complex data structures to be copied and manipulated inexpensively. The persistent way of representing data offers opportunities to more elegantly and more efficiently implement certain algorithms and programming patterns. Few persistent data structure libraries, however, are designed with an emphasis on speed and performance compared to their mutable cousins. We describe and present a C library for a persistent graph data structure, which uses array compression techniques and balanced wide-fanout tries to create a structure that enables persistence without sacrificing performance. Compared to a competitive C++ mutable graph library, we consistently achieve 30-40% slower random read performance using up to 30% fewer bytes in memory, with the benefit of highly space-efficient persistence.

Note

The author has given permission for this work to be deposited in the Digital Archive of Colorado College.

Colorado College Honor Code upheld.

Includes bibliographical references.

Administrative Notes

The author has given permission for this work to be deposited in the Digital Archive of Colorado College.

Colorado College Honor Code upheld.

Copyright
Copyright restrictions apply.
Publisher
Colorado College
PID
coccc:25837
Digital Origin
born digital
Extent
6 pages : illustrations
Thesis
Senior Thesis -- Colorado College
Thesis Advisor
Ylvisaker, Ben
Department/Program
Math and Computer Science
Degree Name
Bachelor of Arts
Degree Type
bachelor
Degree Grantor
Colorado College
Date Issued
2016-05