# Indexing a huge dataset (that does not fit into central memory)

The problem.

Let us consider a huge file with billions of lines, each containing a string. There are $$n$$ different strings and $$m$$ lines in the file, with $$m$$ much greater than $$n$$, although both are huge. In particular, neither the entire file nor the list of all distinct strings fit into central memory. The global file may be parsed and/or sorted (in external memory) a few times, though.

The goal is to build the file in which line $$i$$, for $$i=1..m$$, is integer $$k$$ if the string on line $$i$$ in the original file is the $$k+1$$-th distinct string appearing in the original file.

Example.

For instance, if the original file is:

bbb
cccc
cccc
bbb
aaa
ee
aaa
fff
dddd
cccc
bbb
fff


then $$n=6$$, $$m=12$$, and we should obtain:

0
1
1
0
2
3
2
4
5
1
0
4


My approach.

I take benefit of standard unix command-line tools, as follows.

I first build a numbered string occurence file:

zcat input.gz | awk '{print NR-1,$0;}' | gzip -c > occurrences.gz  I use it to build an index file for strings that respects occurence rank, and starts with character '-', lower than any occurence number: zcat occurrences.gz | sort -T. -S1g --stable -k2,2 | awk 'BEGIN{old="none";}{if ($2!=old) print $0; old=$2;}' |
sort -T. -S1g -nk1,1 | awk '{print "-",$2,NR-1;}' | gzip -c > index.gz  I merge the two files and sort the result to ensure that the line with a string index will be just before all other lines containing this string; I then replace each string, sort according to occurence rank, and I am done: zcat occurrences.gz index.gz | sort -T. -S1g -k2,2 -k1,1 | awk '{if ($1=="-") i=$3; else print$1,i;}' |
sort -T. -S1g -nk1,1 |
cut -d" " -f2 |
gzip -c > result.gz


Technical detail: to avoid encoding issues, first set environment variable LC_ALL to C.

Question.

Is it possible to do significantly better than my approach, or to achieve similar performances with a significantly different approach, in practice?

Notice that I am not interested in minor, technical improvements, like using mawk, sed, etc, instead of awk. I am not interested in a purely theoretical solution either, that would be better asymptotically but would turn out to be so complex than no implementation is reasonably feasible.

Instead, my concern is the relevance and overall effectiveness of my approach, or variants.

For instance, would any external memory data structure be faster, while using as little memory, with available implementation?

• Should -k2,2 -k1,1 be -k2,2 -nk1,1? (Not sure if that works with sort.)
– D.W.
Jan 5 '21 at 7:40
• It works on my platform as written in the question, but does not with this change. This sort just has to put identical strings together, with the line starting with '-' first, so numericai sort is not needed, if I am correct. Jan 5 '21 at 7:50
• Warm thanks for the edition, that makes the question much easier to read :) Jan 5 '21 at 7:52
• OK, thank you. It's possible it might be slightly faster with that change (you might have to change - to 0 or -1), if sort is faster on partly sorted files, but maybe not. Anyway: I can see how to speed up the index step (possibly significantly, I don't know, it depends on how sort works) by splitting into temporary files based on a hash of the string, but I can't see how to speed up the merge. I'm guessing the merge is the dominant cost, and if so, speeding up constructing the index won't help much. Let me know if I've misunderstood somehow.
– D.W.
Jan 5 '21 at 7:53
• Good point, replacing '-' by '-1' and sorting numerically may indeed be faster. Right again regarding splitting, but I think this is what sort does, and what makes it so effective. Thanks! Jan 5 '21 at 7:58