An Efficient Algorithm for Generating Super Condensed Neighborhoods
Luís M. S. Russo,
R – INESC-ID Lisboa –
Approximate string matching is the problem of finding a pattern in a text
allowing for some errors to occur.
Indexing methods for the approximate string matching problem spend a
considerable effort generating condensed neighborhoods. In this session we
point out that condensed neighborhoods are not a minimal
representation of a pattern neighborhood. We show that we can restrict
our attention to super condensed neighborhoods which are minimal. We
then present a basic algorithm for generating Super Condensed
Neighborhoods. The algorithm runs in O(m s), where m is the
pattern size and s is the size of the super condensed
neighborhood. Previous algorithms took O(m c) time, where c is the
size of the condensed neighborhood. We present an implementation of the
algorithm using modern Bit-Parallelism and Increased Bit-Parallelism
Date: 2005-Feb-10 Time: 16:30:00 Room: Room 425
For more information:
INESC Brussels HUB Winter Meeting | JAN 25-26, 2024, in Porto
The INESC Winter Meeting, organized in collaboration with INESC Holding, is scheduled for January 25th and 26th, 2024, and it will be held in the city of Porto.
On January 25th, the primary goal is to bring together individuals from all five INESC institutes, fostering an environment that encourages networking, forging new connections, and collectively engaging in a forward-thinking exercise regarding the future of our research fields and the positioning of the INESC group within the European landscape.
There will be a welcome lunch, followed by an afternoon dedicated to collaboration, openness, and curiosity. The event will have a participatory approach, and will be guided by Dirk Stockmans, a highly experienced facilitator who has worked for the European Commission for the last 30 years.
Furthermore, all INESC researchers are invited to submit proposals for e-posters to be displayed at the Winter Meeting. Deadline for submissions is December 10 and more information is available here.
On January 26th, a senior administration and management committee will be held. Participants will be selected by each institute administration by invitation only.
If you would to take part on the 25th of January, please register here by November 30th.
The INESC Brussels HUB website will soon share more information about the venue and uptaded agenda.