DOTTED SUFFIX TREES: A STRUCTURE FOR APPROXIMATE TEXT INDEXING
Luis Coelho,
D – Departamento de Engenharia Informática, Instituto Superior Técnico, Universidade de Lisboa –
Abstract:
The problem we address is text indexing for approximate matching. We consider that we are given a text T which undergoes some preprocessing to generate an index. We can later query this index to identify the places where a string occurs up to a certain number of allowed errors k, where by error we mean the substitution, deletion or replacement of one character (edition or Levenstein distance).
We present a structure for indexing which occupies space O(n log^k n) in the average case, independent of alphabet size, n being the text size. This structure can be used to report the existence of a match with k errors in O (3k mk+1 ) and to report the occurrences in O(3^k m^{k+1} + ed) time, where m is the length of the pattern and where ed the number of matching edit scripts. These bounds are independent of alphabet size. The construction of the structure has time bound by O (k N |S|), where N is the number of nodes in the index and |S| the alphabet size.
Date: 2006-Jul-06 Time: 16:30:00 Room: 336
For more information:
Upcoming Events
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.
Preliminary agenda