Note on Table 1 in paper Top-k Ranked Document Search in General Text Databases, ESA 2010

This note relates to the paper

J.S. Culpepper, G. Navaro, S. Puglisi and A. Turpin.
"Top-k Ranked Document Search in General Text Databases",
Proc. 18th Annual European Symposium on Algorithms (ESA 2010),
Liverpool, UK. September 2010.

The space reported in Table 1 is not peak memory usage during search time for method `Sada`. It is an estimate, assuming a space-optimal implementation of the $2n+o(n)$-bit range minimum query data structures. The actual memory usage for Sada is about two times larger.

Thanks to Simon Gog for spotting this discrepency, and writing the text of this note.

Page created by Andrew Turpin Wed 16 Apr 2014 13:31:00 EST