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

Question

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?

Answer 1

The other approach that I can think of is the obvious one: process the file one line at a time, and consult a dictionary of "seen" lines. What may not be obvious is how to represent the dictionary.

There are plenty of on-disk data structures that would work, and this is a well-researched area given that this is what databases do for a living. Some variant of B-trees, or a hash table (e.g. extensible hashing) would work. Consider Berkeley DB if you need something off the shelf.

If that is too slow, you could use a Bloom filter as an in-memory cache. Then, you need only consult the on-disk data structure if you get a hit in the Bloom filter.