publications

2024

1. FakeSamples

   

   The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples

   Simone Faro, Francesco Pio Marino, Andrea Moschetto, and 2 more authors

   In 12th International Conference on Fun with Algorithms (FUN 2024), May 2024

   Abs DOI Bib

   Sampled String Matching is presented as an efficient solution to the string matching problem, aiming to tackle the space constraints of indexed string matching while purportedly reducing search times for online solutions. Despite the problem’s inception dating back to 1991, practical solutions have only recently emerged. These purportedly accelerate online searches by up to 35 times compared to conventional methods, achieved through a partial index occupying a mere 5% of the text size. This paper delves into the intricacies of one of the latest and most effective text sampling techniques, character distance sampling, which revolves around sampling distances between characters of a selected alphabet within the text. Specifically, we introduce fake samples while remaining honest! In other words, the study reveals that, interestingly, strategically introducing fake samples within the sampled sequence slashes the required index space by almost half, just avoid compromising the algorithm’s correctness. Additionally, since efficiency is everything, this approach, in turn, purportedly enhances the algorithm’s efficiency under specific conditions.

   @inproceedings{faro_et_al:LIPIcs.FUN.2024.13,
     author = {Faro, Simone and Marino, Francesco Pio and Moschetto, Andrea and Pavone, Arianna and Scardace, Antonio},
     title = {The Great Textual Hoax: Boosting Sampled String Matching with Fake Samples},
     booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)},
     pages = {13:1--13:17},
     isbn = {978-3-95977-314-0},
     issn = {1868-8969},
     year = {2024},
     month = may,
     volume = {291},
     editor = {Broder, Andrei Z. and Tamir, Tami},
     publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
     address = {Dagstuhl, Germany},
     url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.13},
     urn = {urn:nbn:de:0030-drops-199211},
     doi = {10.4230/LIPIcs.FUN.2024.13},
     annote = {Keywords: string matching, sampling},
   }