Finding Common Patterns in Strings with Outliers
Author Information
Author(s): Christina Boucher, Bin Ma
Primary Institution: David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON
Hypothesis
Can we find a center string that is close to most input strings while ignoring outliers?
Conclusion
The proposed model effectively identifies a center string that represents a majority of input strings while revealing outliers.
Supporting Evidence
- The CLOSEST STRING problem is NP-complete, indicating the difficulty of finding a solution.
- The CSWO model allows for a more flexible approach by accommodating outliers.
- Algorithms for CSWO are provided for both bounded and unbounded alphabets.
Takeaway
This study helps us find a string that is similar to most others, even if some are very different. It's like finding a common favorite toy among a group of kids, even if one kid has a completely different toy.
Methodology
The study introduces a refined model called the CLOSEST STRING WITH OUTLIERS (CSWO) and provides algorithms for solving it.
Limitations
The model's effectiveness can be sensitive to the choice of parameters and the presence of outliers.
Digital Object Identifier (DOI)
Want to read the original?
Access the complete publication on the publisher's website