Papers › Indexing Strings with Utilities
Indexing Strings with Utilities
Giulia Bernardini, Huiping Chen, Alessio Conte, Roberto Grossi, Veronica Guerrini, Grigorios Loukides, Nadia Pisanti, and Solon P. Pissis
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Applications in domains ranging from bioinformatics to advertising feature strings that come with numerical scores (utilities). The utilities quantify the importance, interest, profit, or risk of the letters occurring at every position of a string. Motivated by the ever-increasing rate of generating such data, as well as by their importance in several domains, we introduce Useful String Indexing (USI), a natural generalization of the classic String Indexing problem. Given a string S (the text) of length n, USI asks for preprocessing S into a compact data structure supporting the following queries efficiently: given a shorter string P (the pattern), return the global utility U(P) of P in S, where U is a function that maps any string P to a utility score based on the utilities of the letters of every occurrence of P in S. Our work also makes the following contributions: (1) We propose a novel and efficient data structure for USI based on finding the top-K frequent substrings of S. (2) We propose a linear-space data structure that can be used to mine the top-K frequent substrings of S or to tune the parameters of the USI data structure. (3) We propose a novel space-efficient algorithm for estimating the set of the top-K frequent substrings of S, thus improving the construction space of the data structure for USI. (4) We show that popular space-efficient top-K frequent item mining strategies employed by state-of-the-art algorithms do not smoothly translate from items to substrings. (5) Using billion-letter datasets, we experimentally demonstrate that: (i) our top-K frequent substring mining algorithms are accurate and scalable, unlike two state-of-the-art methods; and (ii) our USI data structures are up to $15$ times faster in querying than $4$ nontrivial baselines while occupying the same space with them.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections