Missing value replacement in strings and applications

Area of Science:

• Computer Science
• Bioinformatics
• Data Science

Background:

• Missing values are common in sequential data due to measurement errors, flexible modeling, or privacy concerns.
• Analyzing such data requires efficient and effective methods for replacing missing values with valid characters.
• Existing methods may not adequately address constraints like context and forbidden patterns.

Purpose of the Study:

• To formalize the problem of replacing missing values in sequential data as a combinatorial optimization problem.
• To develop an efficient algorithm for solving this problem, considering context and forbidden patterns.
• To apply the algorithm for sanitizing private strings and clustering collections of strings.

Main Methods:

• Formalizing the problem as finding shortest paths in graphs with forbidden edges.
• Designing a linear-time algorithm for strings over constant-sized alphabets.
• Applying techniques from formal languages and combinatorial pattern matching.

Main Results:

• A linear-time algorithm for efficient missing value replacement in sequential data.
• Demonstration of the algorithm's effectiveness in fully sanitizing private strings.
• A methodology for sanitizing and clustering private string collections that preserves clustering quality.
• Experimental results showing superior performance over state-of-the-art methods.

Conclusions:

• The proposed algorithm efficiently handles missing values in sequential data under complex constraints.
• The methodology offers effective privacy protection for string datasets while maintaining data utility for clustering.
• This work advances the state of the art in data sanitization and analysis of sequential data.