University Library
  • Login
A gateway to Melbourne's research publications
Minerva Access is the University's Institutional Repository. It aims to collect, preserve, and showcase the intellectual output of staff and students of the University of Melbourne for a global audience.
View Item 
  • Minerva Access
  • Engineering
  • Computing and Information Systems
  • Computing and Information Systems - Research Publications
  • View Item
  • Minerva Access
  • Engineering
  • Computing and Information Systems
  • Computing and Information Systems - Research Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

    Reducing Space Requirements for Disk Resident Suffix Arrays

    Thumbnail
    Citations
    Scopus
    Altmetric
    5
    Author
    Moffat, A; Puglisi, SJ; Sinha, R
    Editor
    Zhou, X; Yokota, H; Deng, K; Liu, Q
    Date
    2009-01-01
    Source Title
    DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PROCEEDINGS
    Publisher
    SPRINGER-VERLAG BERLIN
    University of Melbourne Author/s
    Moffat, Alistair; SINHA, RANJAN
    Affiliation
    Computer Science And Software Engineering
    Metadata
    Show full item record
    Document Type
    Conference Paper
    Citations
    Moffat, A., Puglisi, S. J. & Sinha, R. (2009). Reducing Space Requirements for Disk Resident Suffix Arrays. Zhou, X (Ed.) Yokota, H (Ed.) Deng, K (Ed.) Liu, Q (Ed.) DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PROCEEDINGS, 5463, pp.730-+. SPRINGER-VERLAG BERLIN. https://doi.org/10.1007/978-3-642-00887-0_63.
    Access Status
    This item is currently not available from this repository
    URI
    http://hdl.handle.net/11343/26728
    DOI
    10.1007/978-3-642-00887-0_63
    Description

    F1 - Full Written Papers Refereed

    Abstract
    Suffix trees and suffix arrays are important data structures for string processing, providing efficient solutions for many applications involving pattern matching. Recent work by Sinha et al. (SIGMOD 2008) addressed the problem of arranging a suffix array on disk so that querying is fast, and showed that the combination of a small trie and a suffix array-like blocked data structure allows queries to be answered many times faster than alternative disk-based suffix trees. A drawback of their LOF-SA structure, and common to all current disk resident suffix tree/array approaches, is that the space requirement of the data structure, though on disk, is large relative to the text – for the LOF-SA, 13n bytes including the underlying n byte text. In this paper we explore techniques for reducing the space required by the LOF-SA. Experiments show these methods cut the data structure to nearly half its original size, without, for large strings that necessitate on-disk structures, any impact on search times.
    Keywords
    Information and Computing Sciences not elsewhere classified; Information and Communication Services not elsewhere classified

    Export Reference in RIS Format     

    Endnote

    • Click on "Export Reference in RIS Format" and choose "open with... Endnote".

    Refworks

    • Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References


    Collections
    • Minerva Elements Records [45689]
    • Computing and Information Systems - Research Publications [1454]
    Minerva AccessDepositing Your Work (for University of Melbourne Staff and Students)NewsFAQs

    BrowseCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects
    My AccountLoginRegister
    StatisticsMost Popular ItemsStatistics by CountryMost Popular Authors