FAR-Tree: A Spatial Index For Solid State Drives

  • Author / Creator
    Jiang, Feng
  • Solid state drives (SSDs) are becoming more common with their main advantage of faster reads compared to hard disk drives (HDDs). However, writes are relatively slower, indeed asymmetric with respect to reads, unlike in HDDs where read and write are comparable. Current indexing structures were designed for HDDs and aim at reducing the number of reads at query time. In SSDs, index writes may impact the overall query performance in the presence of updates. Thus, we focus on minimizing the number of writes during index update, considering the R-tree in particular, given that it is an ubiquitous and update-expensive indexing structure. We propose the FAR-tree (for Flash Aware R-tree) which aims at avoiding node splits by building a chain of nodes on leaf nodes. Our experiments using real and synthetic datasets show that the FAR-tree can yield a more update-efficient index at the cost of some overhead at query time.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Nascimento, Mario (Computing Science)
  • Examining committee members and their departments
    • Lu, Paul (Computing Science)
    • Wong, Ken (Computing Science)