A constant problem for computer science (since its inception) is how to manipulate data that is larger than machine memory. We present here some general strategies for working “out of core” or what you should do when you run out of memory.
Early computers were most limited by their paltry memory sizes. von Neumann himself commented that even a room full of genius mathematicians would not be capable of much if all they could communicate, think upon or remember were the characters on a single type written page (much more memory than the few hundred words available to the Eniac). The most visible portions of early computers are their external memories or secondary stores: card readers, paper tape readers and tape drives.
SDC 920 computer, Computer History Museum, Mountain View CA
Historically computer scientists have concentrated on streaming or online algorithms (that is algorithms that work with the data in the order it is available and use limited memory). For many problems we have found this an insufficient model and it is much better to assume you can re-order and replicate data (such as scattering data to many processors and re-collecting it to sort). The scatter/gather paradigm is ubiquitous and is the underpinning of large scale sorting, databases and Map Reduce. So in one sense databases and Map Reduce different APIs on top of very related technologies (journaling, splitting and merging). Replicating data (or even delaying duplicate elimination) that is already “too large to handle” may seem counterintuitive; but it is exploiting the primary property of secondary storage: that secondary storage tends to be much larger than primary storage (typically by 2 orders of magnitude, compare a 2 terabyte drive to an 8 gigabyte memory stick). Read more…
We extend the ideas of from Automatic Differentiation with Scala to include the reverse accumulation. Reverse accumulation is a non-obvious improvement to automatic differentiation that can in many cases vastly speed up calculations of gradients. Read more…
Categories: Applications, Coding, Exciting Techniques, Mathematics, Programming, Tutorials Tags: Automatic Differentiation, Conjugate Gradient, Gradient, Mathematical Bedside Reading, Optimization, Reverse Accumulation, Scala
This article is a worked-out exercise in applying the Scala type system to solve a small scale optimization problem. For this article we supply complete Scala source code (under a GPLv3 license) and some design discussion. Read more…
Categories: Applications, Coding, Computer Science, Exciting Techniques, Mathematics, Programming, Tutorials Tags: Automatic Differentiation, Conjugate Gradient, Dual Numbers, Geometric Median, Numeric Methods, Optimization, Scala, Steiner Tree
Readers returning to our blog will know that Win-Vector LLC is fairly “pro-R.” You can take that to mean “in favor or R” or “professionally using R” (both statements are true). Some days we really don’t feel that way. Read more…
One of my research interests is finding the principles that underly the management of information, complexity and uncertainty. When something as simple as a web-form is called “technology” it is time to step back and examine your principles. One principle I am not sure about Postel’s law. It doesn’t hold often enough to be relied on and when it fails I am not sure who to be angry with. Read more…
This article is quick concrete example of how to use the techniques from Survive R to lower the steepness of The R Project for Statistical Computing‘s learning curve (so an apology to all readers who are not interested in R). What follows is for people who already use R and want to achieve more control of the software. Read more…