CITI has stopped operations in 2014, to co-launch NOVA LINCS THIS SITE IS NOT BEING UPDATED SINCE 2013
citi banner
Home Page FCT/UNL UNL
  Home  \  Seminars @ CITI  \  Seminar Page Login  
   
banner bottom
File Top
Representing Almost All Local Longest Common Subsequence Values
{ Wed, 27 May 2009, 14h00 }

By: Luís Russo

In this talk we consider the problem of representing the values of the local Longest Common Subsequences (LCS), of two strings. In a recent paper Tiskin proposed a way to represent the size of the LCS's of one string against all the substrings of another string and all the suffixes of one against all the prefixes of the other string. His representation requires only O((m + n) log(m + n)) bits and obtains any of the O((m + n)^2 ) possible values with only O(log(m + n)/ log log(m + n)) operations, assuming m and n are the size of the strings. This result exposed regularities that occur when trying to represent all these values together instead of individually. We take this approach one step further and propose a way to represent the LCS values of every prefix of one string against every substring of another string. This representation requires only mn + o(m(m + n)) bits and returns each of the O(m(m + n)^2 ) possible values in O((log(m + n) log log(m + n))^2 ) time. Simply iterating Tiskin's representation would be faster by a factor of O(log m(log log m)^3 ) but it would require more space, O(m(m + n) log(m + n)) bits. In fact our approach offers a range of inbetween space time trade-offs and presents new insights into the framework presented by Tiskin.


Hosted by: Software Systems

Location: DI seminars room

File Bottom