Fast and Cache-Oblivious Dynamic Programming with Local Dependencies

Publication: Research - peer-reviewArticle in proceedings – Annual report year: 2012

View graph of relations

String comparison such as sequence alignment, edit distance computation, longest common subsequence computation, and approximate string matching is a key task (and often computational bottleneck) in large-scale textual information retrieval. For instance, algorithms for sequence alignment are widely used in bioinformatics to compare DNA and protein sequences. These problems can all be solved using essentially the same dynamic programming scheme over a two-dimensional matrix, where each entry depends locally on at most 3 neighboring entries. We present a simple, fast, and cache-oblivious algorithm for this type of local dynamic programming suitable for comparing large-scale strings. Our algorithm outperforms the previous state-of-the-art solutions. Surprisingly, our new simple algorithm is competitive with a complicated, optimized, and tuned implementation of the best cache-aware algorithm. Additionally, our new algorithm generalizes the best known theoretical complexity trade-offs for the problem.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications : 6th International Conference, LATA 2012 A Coruña, Spain, March 5-9, 2012 Proceedings
PublisherSpringer
Publication date2012
Pages131–142
ISBN (print)978-3-642-28331-4
ISBN (electronic)978-3-642-28332-1
DOIs
StatePublished

Conference

ConferenceThe 6th International Conference on Language and Automata Theory and Applications, LATA
CountrySpain
CityCoruña
Period05/03/1209/03/12
NameLecture Notes in Computer Science
Volume7183
ISSN (Print)0302-9743
CitationsWeb of Science® Times Cited: No match on DOI
Download as:
Download as PDF
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBEHarvardMLAStandardVancouverShortLong
Word

ID: 7740274