UpComing Seminars

Recent Seminars

Seminar Archive

Mr Krisztian Monostori
Suffix Vector: A Space-Efficient Suffix Tree Representation

Dr Remco Bouckaert
Bayes Nets (in Weka)

Dr Dale Carnegie
Autonomous Mobile Robotics

Dr William Wong
Situation Awareness in Emergency Ambulance Command and Control: Implications for Human-Systems Interaction

Seminar Archive >> 2001
Mr Krisztian Monostori - Suffix Vector: A Space-Efficient Suffix Tree Representation

Affiliation : School of Computer Science and Software Engineering, Monash University


Computer Science Seminar Room, G1.15

Suffix trees are very versatile data structures that are used in many areas of computing including string-matching, DNA-matching, file-compression, etc. One of the main arguments against suffix trees is that they are greedy for space. Numerous attempts have been made in the past to improve the space-efficiency of suffix trees but most of these attempts resulted in representations tailored to specific problems.

The suffix vector representation is a general representation, which can be used in any application area where a suffix tree is applicable. The suffix vector is more space-efficient than any other suffix tree representations that have the same versatility.

Our data structure eliminates the redundancies present in other suffix tree representations, which not only saves space but also results in faster runs of certain algorithm because they do not have to analyse redundant parts of the tree.

Suffix trees and suffix vectors have efficiently been used in our document comparison prototype system: MatchDetectReveal (MDR). A short demonstration of this system will also be presented.

  2007 FCMS. The University of Waikato - Te Whare Wananga o Waikato