Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Resizable Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
A dynamic retrieval data structure encodes a function for a set , while supporting queries for , insertions \texttt{Insert}$…
cs.DS2024
Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval
William Kuszmaul, Aaron Putterman, Tingqiang Xu +2
Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four sett…
cs.DS2023
Nearly Optimal Internal Dictionary Matching
Jingbang Chen, Jiangqi Dai, Qiuyang Mang +2
We study the internal dictionary matching (IDM) problem where a dictionary containing substrings of a text is given, and each query concerns the occurrences o…