Old algorithm textbooks often covered algorithms that did well on tape drives, since tape drives used to be a common storage type on almost all computers. Since memory on modern CPUs with data prefetching is starting to more and more resemble a tape drive, I was wondering if there used to be some "canonical" books/papers back in the day on algorithms operating on tape storage? I'd be very interested in checking out what was ideas were available back then.

  • $\begingroup$ This reference request feels a tad too broad for me (community votes, please!). What features are you interested in? What kind of algorithms? $\endgroup$
    – Raphael
    Jul 18 '15 at 13:35
  • $\begingroup$ I don't mind if it's made into a community wiki. $\endgroup$ Jul 18 '15 at 13:35
  • 1
    $\begingroup$ Yes, it's too broad. What specific task are you looking for an algorithm for? Community wiki doesn't help; we don't use community wiki as a way to accept questions that don't meet our standards. I suggest you look at streaming algorithms, cache-oblivious algorithms, memory-hierarchy-aware algorithms, and external sorting. The database literature probably also has a lot of relevant techniques, since they have to deal with this problem in spades. $\endgroup$
    – D.W.
    Jul 18 '15 at 15:46
  • $\begingroup$ I think it is a valid question, but maybe should be a bit focused. I would've liked to know how old-time algorithms compare to current streaming algorithms. The scarcity of memory back then seems to fit into this comparison as well. $\endgroup$
    – Ran G.
    Jul 18 '15 at 21:36
  • $\begingroup$ I'll think of how to make my question more focused. However, one reason for asking it was precisely how much we're reinventing the wheel in modern big data applications when trying to optimize memory layout. Few people I've talked to seem to have thought of this obvious link to the tape drive era. In other words, how far can we trace back ideas? $\endgroup$ Jul 18 '15 at 22:54