4 ms·

I'm certain I'm re-inventing the wheel with this approach, but I obviously haven't been researching in the right places, since I hadn't run across this approach

I'm certain I'm re-inventing the wheel with this approach, but I obviously haven't been researching in the right places, since I hadn't run across this approach before I cobbled it together. I'm expecting an education on what I'm missing from the HN community!

hga 17y ago
I got the impression from some of what I was reading in the run up to Y2K that this sort of approach was common in the mainframe world. Obviously, many sites had lots of data (often a lot stored on tape) and limited main memory (especially back in the days in which it was core). You might start here: http://en.wikipedia.org/wiki/Mainframe_sort_merge http://en.wikipedia.org/wiki/Mainframe_sort_merge ("It is very frequently used; often the most commonly used application program in a mainframe shop.") Show the old dogs that new dogs can learn old tricks ^_^.
andrewcooke 17y ago
is http://en.wikipedia.org/wiki/Merge_sort#Merge_sorting_tape_drives http://en.wikipedia.org/wiki/Merge_sort#Merge_sorting_tape_d... what you were remembering? that's what immediately sprung to my mind on reading the article, but i don't know if you're expecting something more specific.
deleted 17y ago
[deleted]
fhars 17y ago
The "external sorting" chapter of TAoCP might also be interresting in this context (5.4 in Vol. 3), even though Knuth thought that "the once-crucial topic of patterns for tape merging has become of limited relevance to currnt needs" (p. 251) due to the rapid development of disks in the 80s and 90s, so that his exposition might "be their last grabd appearance before they acept a final curtain call." Little did he know that disk would soon become the new tape... To his credit, he ended the introduction to the chapter with the citation "for all we know now, these techniques may well become crucial again."
zzleeper 17y ago
Column stores (http://en.wikipedia.org/wiki/Column-oriented_DBMS http://en.wikipedia.org/wiki/Column-oriented_DBMS) have been designed specially for this case. There are a few ones (monet, cstore) but the really good ones are sadly $$$. That said, their ideas are quite straightforward and you could look them up quickly (I forgot the blog I was thinking about, but check also here: http://www.vldb.org/ http://www.vldb.org/ ).
barrkel 17y ago
I've had a similar problem when dealing with a relatively large data set (in a consumer PC context) that really really needed random access. I was using sorted text files with indexes (flat array of line start offsets), but eventually I redesigned to use a (Patricia) trie, so that I could store all the data in memory. Crunching the data down in size to make it both small yet low-cost to extract was then the challenge. I started out with sorted text files on the order of 550MB, and ended up with memory dumps of efficiently packed tries on the order of 95MB, with further scope for compression possible through huffman encoding of markov chains (encoding letter transition probabilities with a path through a huffman binary tree), that I didn't need to implement because I had already achieved my goals. The trivial parallelization available through sorting massive text files is hard to beat, though, especially as you can write ad-hoc bash scripts to do work with sort, uniq, sed, etc.

hga 17y ago

I got the impression from some of what I was reading in the run up to Y2K that this sort of approach was common in the mainframe world. Obviously, many sites had lots of data (often a lot stored on tape) and limited main memory (especially back in the days in which it was core). You might start here: http://en.wikipedia.org/wiki/Mainframe_sort_merge http://en.wikipedia.org/wiki/Mainframe_sort_merge ("It is very frequently used; often the most commonly used application program in a mainframe shop.") Show the old dogs that new dogs can learn old tricks ^_^.

andrewcooke 17y ago

is http://en.wikipedia.org/wiki/Merge_sort#Merge_sorting_tape_drives http://en.wikipedia.org/wiki/Merge_sort#Merge_sorting_tape_d... what you were remembering? that's what immediately sprung to my mind on reading the article, but i don't know if you're expecting something more specific.

deleted 17y ago

[deleted]

fhars 17y ago

The "external sorting" chapter of TAoCP might also be interresting in this context (5.4 in Vol. 3), even though Knuth thought that "the once-crucial topic of patterns for tape merging has become of limited relevance to currnt needs" (p. 251) due to the rapid development of disks in the 80s and 90s, so that his exposition might "be their last grabd appearance before they acept a final curtain call." Little did he know that disk would soon become the new tape... To his credit, he ended the introduction to the chapter with the citation "for all we know now, these techniques may well become crucial again."

zzleeper 17y ago

Column stores (http://en.wikipedia.org/wiki/Column-oriented_DBMS http://en.wikipedia.org/wiki/Column-oriented_DBMS) have been designed specially for this case. There are a few ones (monet, cstore) but the really good ones are sadly $$$. That said, their ideas are quite straightforward and you could look them up quickly (I forgot the blog I was thinking about, but check also here: http://www.vldb.org/ http://www.vldb.org/ ).

barrkel 17y ago

I've had a similar problem when dealing with a relatively large data set (in a consumer PC context) that really really needed random access. I was using sorted text files with indexes (flat array of line start offsets), but eventually I redesigned to use a (Patricia) trie, so that I could store all the data in memory. Crunching the data down in size to make it both small yet low-cost to extract was then the challenge. I started out with sorted text files on the order of 550MB, and ended up with memory dumps of efficiently packed tries on the order of 95MB, with further scope for compression possible through huffman encoding of markov chains (encoding letter transition probabilities with a path through a huffman binary tree), that I didn't need to implement because I had already achieved my goals. The trivial parallelization available through sorting massive text files is hard to beat, though, especially as you can write ad-hoc bash scripts to do work with sort, uniq, sed, etc.