Reducing Space Requirements for Disk Resident Suffix Arrays
Author
Moffat, A; Puglisi, SJ; Sinha, REditor
Zhou, X; Yokota, H; Deng, K; Liu, QDate
2009-01-01Source Title
DATABASE SYSTEMS FOR ADVANCED APPLICATIONS, PROCEEDINGSPublisher
SPRINGER-VERLAG BERLINAffiliation
Computer Science And Software EngineeringMetadata
Show full item recordDocument Type
Conference PaperCitations
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 repositoryDescription
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 classifiedExport 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