1
$\begingroup$

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.

$\endgroup$

closed as too broad by D.W., David Richerby, Raphael Jul 19 '15 at 7:06

Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer. Avoid asking multiple distinct questions at once. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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$ – Edvard Fagerholm 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$ – Edvard Fagerholm Jul 18 '15 at 22:54