On the relationship between histogram indexing and block-mass indexing

Area of Science:

• Computer Science
• Algorithms
• Computational Complexity

Background:

• Histogram indexing, also known as jumbled pattern indexing, remains an open problem in pattern matching.
• Existing algorithms struggle with preprocessing times for histogram indexing, especially over large alphabets.
• The block-mass pattern matching problem, relevant to mass spectrometry, also presents indexing challenges.

Purpose of the Study:

• To establish a significant connection between histogram indexing and block-mass pattern indexing.
• To explore new algorithmic approaches for pattern matching indexing problems.
• To introduce a novel trade-off between preprocessing and query times for indexing.

Main Methods:

• Demonstrated a simple reduction between histogram indexing and block-mass pattern indexing problems.
• Developed algorithms for both problems over unbounded alphabets with improved preprocessing times.
• Introduced a framework allowing trade-offs between preprocessing and query efficiency.

Main Results:

• A strong, simple connection was established between histogram and block-mass pattern indexing.
• Algorithms were presented that preprocess text T in o(|T|(2)/polylog|T|) time, enabling polynomial query times.
• The research opens avenues for addressing previously intractable indexing problems.

Conclusions:

• The identified connection simplifies understanding and potentially solving complex indexing problems.
• The proposed trade-off strategy offers a new perspective on optimizing indexing algorithms.
• This work lays the foundation for a new class of indexing problems with inherent preprocessing limitations.