Show simple item record

dc.contributor.authorPuglisi, Simon
dc.contributor.authorSmyth, William
dc.contributor.authorTurpin, Andrew
dc.contributor.editorFabio Crestani
dc.date.accessioned2017-01-30T15:07:23Z
dc.date.available2017-01-30T15:07:23Z
dc.date.created2010-04-01T20:02:06Z
dc.date.issued2006
dc.identifier.citationPuglisi, Simon J. and Smyth, W.F. and Turpin, Andrew. 2006. Inverted files versus suffix arrays for locating patterns in primary memory, in Fabio Crestani (ed), 13th Symposium on String Processing and Information Retrieval (SPIRE), Oct 11 2006, pp. 122-133. Glasgow, UK: Springer.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/43428
dc.identifier.doi10.1007/11880561_11
dc.description.abstract

Recent advances in the asymptotic resource costs of pattern matching with compressed suffix arrays are attractive, but a key rival structure, the compressed inverted file, has been dismissed or ignored in papers presenting the new structures. In this paper we examine the resource requirements of compressed suffix array algorithms against compressed inverted file data structures for general pattern matching in genomic and English texts. In both cases, the inverted file indexes q-grams, thus allowing full pattern matching capabilities, rather than simple word based search, making their functionality equivalent to the compressed suffix array structures. When using equivalent memory for the two structures, inverted files are faster at reporting the location of patterns when the number of occurrences of the patterns is high.

dc.publisherSpringer
dc.titleInverted files versus suffix arrays for locating patterns in primary memory
dc.typeConference Paper
dcterms.source.startPage122
dcterms.source.endPage133
dcterms.source.titleInverted files versus suffix arrays for locating patterns in primary memory
dcterms.source.seriesInverted files versus suffix arrays for locating patterns in primary memory
dcterms.source.isbn978-3-540-45774-9
dcterms.source.conference13th Symposium on String Processing and Information Retrieval (SPIRE)
dcterms.source.conference-start-dateOct 11 2006
dcterms.source.conferencelocationGlasgow, UK
dcterms.source.placeHeidelberg
curtin.note

The original publication is available at : http://www.springerlink.com

curtin.departmentOther
curtin.accessStatusFulltext not available
curtin.facultyCurtin Business School
curtin.facultyThe Digital Ecosystems and Business Intelligence Institute (DEBII)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record