Ajwani, DeepakDeepakAjwaniBeckmann, AndreasAndreasBeckmannJacob, RikoRikoJacobet al.2019-04-112019-04-112009 Sprin2009-08-20978-3-642-02010-00302-9743http://hdl.handle.net/10197/9903Flash memory-based solid-state disks are fast becoming the dominant form of end-user storage devices, partly even replacing the traditional hard-disks. Existing two-level memory hierarchy models fail to realize the full potential of flash-based storage devices. We propose two new computation models, the general flash model and the unit-cost model, for memory hierarchies involving these devices. Our models are simple enough for meaningful algorithm design and analysis. In particular, we show that a broad range of existing external-memory algorithms and data structures based on the merging paradigm can be adapted efficiently into the unit-cost model. Our experiments show that the theoretical analysis of algorithms on our models corresponds to the empirical behavior of algorithms when using solid-state disks as external memory.enThe final publication is available at www.springerlink.com.Block sizePriority queueExternal memoryInternal memorySparse graphConference Publication10.1007/978-3-642-02011-7_42019-04-01ME 3250/1-1https://creativecommons.org/licenses/by-nc-nd/3.0/ie/