DiskTrie: An Efficient Data Structure using Flash Memory for Mobile Devices.
N. M. Mosharaf Kabir Chowdhury, Md. Mostofa Akbar, Mohammad Kaykobad · Workshop on Algorithms and Computation · 2007
DiskTrie is an efficient external-memory data structure for storing strings in mobile devices using flash memory. It supports Lookup and Prefix-Matching operations with a constant internal memory and linear processing requirements. The number of disk accesses it takes to search for a string among n unique finite strings is bounded by Θ(log∗ n), while for a prefix-matching operation it takes Θ(log∗ n) + O( n B ) disk accesses, where B is the size of one page in the flash memory.