95 0

Full metadata record

DC FieldValueLanguage
dc.contributor.author박희진-
dc.date.accessioned2018-03-26T01:43:39Z-
dc.date.available2018-03-26T01:43:39Z-
dc.date.issued2013-07-
dc.identifier.citationLecture Notes in Computer Science, 2013, 8288, P.337-348en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttps://link.springer.com/chapter/10.1007%2F978-3-642-45278-9_29-
dc.identifier.urihttp://hdl.handle.net/20.500.11754/52109-
dc.description.abstractWe consider an index data structure for similar strings. The generalized suffix tree can be a solution for this. The generalized suffix tree of two strings A and B is a compacted trie representing all suffixes in A and B. It has |A|?+?|B| leaves and can be constructed in O(|A|?+?|B|) time. However, if the two strings are similar, the generalized suffix tree is not efficient because it does not exploit the similarity which is usually represented as an alignment of A and B.In this paper we propose a space/time-efficient suffix tree of alignment which wisely exploits the similarity in an alignment. Our suffix tree for an alignment of A and B has |A|?+?l d ?+?l 1 leaves where l d is the sum of the lengths of all parts of B different from A and l 1 is the sum of the lengths of some common parts of A and B. We did not compromise the pattern search to reduce the space. Our suffix tree can be searched for a pattern P in O(|P|?+?occ) time where occ is the number of occurrences of P in A and B. We also present an efficient algorithm to construct the suffix tree of alignment. When the suffix tree is constructed from scratch, the algorithm requires O(|A|?+?l d ?+?l 1?+?l 2) time where l 2 is the sum of the lengths of other common substrings of A and B. When the suffix tree of A is already given, it requires O(l d ?+?l 1?+?l 2) time.en_US
dc.language.isoenen_US
dc.publisherSPRINGER-VERLAGen_US
dc.subjectIndexes for similar dataen_US
dc.subjectsuffix treesen_US
dc.subjectalignmentsen_US
dc.titleSuffix Tree of Alignment: An Efficient Index for Similar Data.en_US
dc.typeArticleen_US
dc.identifier.doi10.1007/978-3-642-45278-9_29-
dc.relation.page337-348-
dc.contributor.googleauthorNa, Joong Chae-
dc.contributor.googleauthorPark, Heejin-
dc.contributor.googleauthorCrochemore, Maxime-
dc.contributor.googleauthorHolub, Jan-
dc.contributor.googleauthorIliopoulos, Costas S.-
dc.contributor.googleauthorMouchard, Laurent-
dc.contributor.googleauthorPark, Kunsoo-
dc.relation.code20130050-
dc.sector.campusS-
dc.sector.daehakCOLLEGE OF ENGINEERING[S]-
dc.sector.departmentDEPARTMENT OF COMPUTER SCIENCE-
dc.identifier.pidhjpark-
Appears in Collections:
COLLEGE OF ENGINEERING[S](공과대학) > COMPUTER SCIENCE(컴퓨터소프트웨어학부) > Articles
Files in This Item:
There are no files associated with this item.
Export
RIS (EndNote)
XLS (Excel)
XML


qrcode

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

BROWSE