Show simple item record

dc.contributor.authorMoffat, A
dc.contributor.authorPuglisi, SJ
dc.contributor.authorSinha, R
dc.contributor.editorZhou, X
dc.contributor.editorYokota, H
dc.contributor.editorDeng, K
dc.contributor.editorLiu, Q
dc.date.available2014-05-21T19:45:56Z
dc.date.issued2009-01-01
dc.identifierhttp://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000265740400063&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=d4d813f4571fa7d6246bdc0dfeca3a1c
dc.identifier.citationMoffat, 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.
dc.identifier.isbn978-3-642-00886-3
dc.identifier.issn0302-9743
dc.identifier.urihttp://hdl.handle.net/11343/26728
dc.descriptionF1 - Full Written Papers Refereed
dc.description.abstractSuffix 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.
dc.formatapplication/pdf
dc.languageEnglish
dc.publisherSPRINGER-VERLAG BERLIN
dc.source14th International Conference on Database Systems for Advanced Applications
dc.subjectInformation and Computing Sciences not elsewhere classified; Information and Communication Services not elsewhere classified
dc.titleReducing Space Requirements for Disk Resident Suffix Arrays
dc.typeConference Paper
dc.identifier.doi10.1007/978-3-642-00887-0_63
melbourne.peerreviewPeer Reviewed
melbourne.affiliationThe University of Melbourne
melbourne.affiliation.departmentComputer Science And Software Engineering
melbourne.source.titleLecture Notes in Computer Science
melbourne.source.volume5463
melbourne.source.pages730-+
melbourne.publicationid131731
melbourne.elementsid314200
melbourne.contributor.authorMoffat, Alistair
melbourne.contributor.authorSINHA, RANJAN
dc.identifier.eissn1611-3349
melbourne.event.locationBrisbane, AUSTRALIA
melbourne.accessrightsThis item is currently not available from this repository


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record