Merging sorted sequences was the fundamental data processing
framework of the COBOL era, and again of the MapReduce era.
Just to point out some tangential connections:
* boolean operations can also be synthesized by merging in two or
three dimensions, not just linearly. [NAT1990]
* conversely, a sorted sequence is the linear equivalent of a binary
space partition, due to transitivity of ordering. [HP2006]
-Dave
[NAT1990]
Naylor, Amantides, & Thibault, "Merging BSP Trees Yield Polyhedral
Set Operations", 1990
http://www.mcs.csueastbay.edu/~tebo/papers/siggraph90.pdf
[HP2006]
Hinze & Paterson, "Finger trees: a simple general-purpose data
structure", 2006
4.7 Application: ordered sequences
http://www.cs.ox.ac.uk/ralf.hinze/publications/FingerTrees.pdf
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
