On-line suffix tree construction with reduced branching

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F12%3A10100613" target="_blank" >RIV/00216208:11320/12:10100613 - isvavai.cz</a>
Result on the web
<a href="http://www.sciencedirect.com/science/article/pii/S1570866712000159" target="_blank" >http://www.sciencedirect.com/science/article/pii/S1570866712000159</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.jda.2012.01.001" target="_blank" >10.1016/j.jda.2012.01.001</a>

Result language
angličtina
Original language name
On-line suffix tree construction with reduced branching
Original language description
Classical suffix tree construction algorithms by McCreight and Ukkonen spend most of the time looking up the right branch to follow from the current node. However, not all these slow branching operations are necessary. A significant portion of them is used for implicit suffix link simulation and can be avoided by replacing the traditional top-down descent with bottom-up climbing. We describe the bottom-up approach and analyze its costs and benefits. An experimental evaluation on two standard data corpora shows that bottom-up climbing removes forty to sixty six percent of branching operations and consequently saves twenty one to thirty two percent of construction time. However, a theoretical analysis of the worst-case behavior reveals that the time complexity of the bottom-up approach is superlinear. This is remedied by a combination of both approaches that removes nearly as many branching operations as the bottom-up climb, but still runs in linear time like the top-down descent.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach

Publication year
2012
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)