2

I have a huge (few GBs) file of parent-ID, child-ID pairs. I also have an (incomplete) set of known root nodes.

For each of the known child nodes I need to find a root node, i.e. the one either not having a known further parent-child pair, or belonging to a set of known root nodes. After I find such a root node, I need to write it as a third field to the above set of pairs.

What is most efficient tool(s) and approach for that in command-line environment?

Assume an average node to be ~5-10 levels deep from root; hundreds of leaf nodes peaking at over hundred levels deep.

I need a portability between MacOS (High Sierra) and some Gnu/Linux; I have GNU set of tools on MacOS; free to install further command-line tools both on Mac and Linux. Assume 4GB RAM on both platforms; decent SSD; outdated CPU.

21
  • Are the IDs integers? How big are they?
    – Useless
    Jun 21, 2019 at 14:39
  • Numbers, int or bigint depending on point of view :-) Typically 20 digits each. Jun 21, 2019 at 14:41
  • OK, and how are the pairs formatted? parentID-childID\n or parentID<space>childID\n or something?
    – Useless
    Jun 21, 2019 at 14:45
  • 1
    You may possibly want to look into using tsort. It would be nice to see a small example of your data.
    – Kusalananda
    Jun 21, 2019 at 15:41
  • 3
    @wassrubleff As with most questions here, having a sample of the input data and the expected outcome from transforming that data would help tremendously in answering the question as it would then be possible to test and verify solutions, and also to check that one has actually understood the issue. I, for example, find it much easier to look at the data than to try to make sense of an explanation of the data and the needed transformation.
    – Kusalananda
    Jun 21, 2019 at 20:28

3 Answers 3

3

I'm assuming your file has 2 columns, separated by some character

Looking at the question a little more carefully, a root node will never appear as a child. Keep track of the parents in an array, and increment the count when it's a child. The array keys with zero count will be root nodes.

awk -F, '
   !($1 in p) {p[$1]=0}   # register a parent in the array
   {p[$2]++}              # increment the count when it's seen as a child
   END {for (n in p) if (p[n] == 0) print n}
' bigfile

As @filbranden points out, this only locates the root nodes.

We have a similar situtation at work: in an Oracle db, there's a table that contains parent-child entries. We created a view that would map the child id to the path of ids leading to the parent:

id parent_id
 1 null
 2 1
 3 2
 4 1
 5 null
 6 5

and the view looks like

id id_path
 1 1
 2 1\2
 3 1\2\3
 4 1\4
 5 5
 6 5\6

And this is achieved with this PL/SQL

CREATE OR REPLACE VIEW "SCHEMA"."ITEM_PATHS" ("ID", "ID_PATH") AS
SELECT 
    pci."ID",
    substr(SYS_CONNECT_BY_PATH(pci.id, '\'), 2)  AS ID_PATH
  FROM schema.parent_child_items pci
    START WITH parent_id IS NULL
    CONNECT BY prior id = parent_id;

So, even in a db, it's not a trivial problem. However, I believe the db is better equipped to deal with larger datasets.

3
  • Question says "for each of the known child nodes I need to find a root node", so while this should find all root nodes, it doesn't provide that mapping...
    – filbranden
    Jun 21, 2019 at 17:38
  • @filbranden You are right, I already have most of the root nodes; finding root nodes alone is much easier problem than labelling each node with its root node. Jun 21, 2019 at 17:58
  • Yeah this is definitely a good problem for a DB, especially if your data set is much larger than memory...
    – filbranden
    Jun 21, 2019 at 17:59
1

My suggestion is that you use an iterative approach that will go one level deeper on each step until no further progress is possible, at which point you have found the root. So the first step would take a parent child pair and find the first ancestor, outputting a grandparent child pair, the second step would then output a great-grandparent child pair, and so on.

You can implement that using join(1), where you can match the first field of one file to the second field of the other file, therefore replacing a node with its parent. join(1) requires that the files are sorted and that can be easily accomplished using sort(1).

You can accomplish that using the script below. It assumes input file nodes.txt has one pair of whitespace separated parent child nodes on each line. It will produce a resulting roots.txt with lines that have root child pairs on each line.

export LC_COLLATE=C
sort -k 2 nodes.txt -o nodes.bychild
: >roots.txt
sort -k 1 nodes.txt -o nodes.0
depth=0
while [[ -s nodes.0 ]]; do
  echo "Depth: $((depth++)) - $(date)"
  join -1 2 -2 1 -o '1.1 2.2' nodes.bychild nodes.0 | sort -k 1 -o nodes.1
  # Nodes not present in nodes.1 have
  # their root in nodes.0 already:
  join -1 2 -2 1 -v 2 -o '2.1 2.2' nodes.bychild nodes.0 >>roots.txt
  # Next step:
  mv nodes.1 nodes.0
done
rm nodes.0 nodes.bychild
sort -k 2 roots.txt -o roots.txt

You can try it online for a small sample input.

This approach requires that you have roughly 5 times the size of the dataset of free space in your hard drive (one for the index nodes.bychild, two for nodes.0 and nodes.1 which for some time exist at the same time, one for sorting and one for the resulting roots.txt file.)

There are two calls of join(1) on each iteration, one of them to go one level deeper and another one (using -v) to find the cases where a match does not exist, which is used to detect when a root node has been found. This starts exposing some of the shortcomings of join(1), having a more flexible tool would be able to get both those tasks done in a single step. Another advantage of a more flexible tool would be to keep the path from child all the way to the root, which is not that obvious to do with join(1) alone. Replacing join(1) with a simple tool written in a higher level language such as Python would probably go a long way in making this script a lot more powerful.


Complexity analysis

The join(1) tool is a good one to use since it uses O(1) space and takes O(n) time. Since it requires the files to be sorted, it considers only one line of each file at a time, advancing the one that's behind (or both at the same time when they match), therefore constant space. Since it only reads each line of each file once, it executes in linear time.

So the important factor in the complexity of the loop is sort(1), which takes O(n log n) time. The implementation of Unix sort(1) uses temporary files to store temporary results when the input is significantly large, so it's possible to sort a dataset much larger than memory. The temporary diskspace used by sort(1) uses O(n) space (already mentioned on disk requirements above.)

Since each loop iteration takes O(n log n) time, the total runtime will be proportionate to running this loop as many times as there are levels between children and their roots. The pathological worst case is when there's a single chain from a child all the way to the root, in which case depth will be n and the algorithm will take O(n² log n), but in most practical cases it's expected that depth will be much lower than n so the time complexity is much smaller than that.

Furthermore, as you start getting into the long tail of nodes with larger depth, n will typically be getting smaller quite faster, so in your case it's probably easier to consider a factor of 5-10 (typical depth) rather than 100 (worst case depth for the long tail.)

An obvious improvement here would be to consider the output from previous steps in calculating the current step. For instance, if I have established a (3->2->1) relationship and a (5->4->3) relationship, I should be able to go directly to (5->1) rather than (5->2). The further steps will go exponentially quicker as well (e.g. 9->5 and 5->1 going to 9->1, which would take 8 steps with the current approach but only 3 with the optimized one.) This would take the pathological case to a O(n log² n) complexity (since the depth is now exponential, it only takes O(log n) steps to get to the maximum) and would probably be quite helpful on the normal case as well.

It's probably possible to implement that using join(1), but as mentioned before, a more flexible script written in a higher level language would probably be much better for such an approach (for example, merging lines from multiple sources intelligently, that is tailored for the specific algorithm.)

If this is a common use case of yours, maybe spend time implementing such a smarter approach. If it's a one-off, then the quick-and-dirty script above might be enough...

(If it's an important use case, use a database instead!)

1

IF I understood well your description and requirements, it seems you have to rebuild a tree from a set of hierarchically related nodes.

I second all other people's comments about the fact that this is a job for a proper DB engine, but if you must do with standard command-line tools, then one other alternative might be using the filesystem as a "database", namely as an index for your nodes.

Getting to the final result would thus require 2 passes of all your nodes:

  • first pass from the input data-set to create a representation of it on the filesystem, where each single node would be a directory containing a symlink to its parent node/directory
  • second pass to traverse all nodes upwards to their roots and then display each node along with its parent and root as you requested

As conceptually simple as this is, it absolutely does have some notable down-sides.

The main down-side is basically that you'd be dependent on the features of the filesystem you use, and that you'd very likely need to prepare a dedicated filesystem crafted for this purpose by taking into consideration:

  • filesystem's performance in dealing with millions of directories contained in one single directory: ext4 for example is not very good at this as it degrades a lot after just a few tens of thousands; xfs is better than ext4, but maybe the best choices for this aspect would be reiserfs (probably the best) or btrfs (a bit less quick than reiserfs); however, with the figures you mentioned, even with btrfs or reiserfs you'd still need to partition the amount of nodes/directories into several intermediate (sub-levels of) sub-directories so that you never let more than ~1M directories in any one single directory
  • filesystem's compactness (disk space required) in storing so many nodes/directories where each would contain just one symlink and (after the second pass) one very small file: here you should afford a big waste of disk space because filesystems' standard configurations typically allocate 4k per each directory or file, making a total of 8-12k per each node, and although filesystems allow some tuning for this at formatting time, specifically the minimum allocation size, I would expect no less than 2-3k per each node; you might get more compact than that by storing nodes' parents and roots in extended attributes instead of symlinks and files, but still would make probably not less than 1k per each node

Another down-side might be what language you use to handle all this: using a shell script would be very slow for the first pass because each single node would require an mkdir and a ln -s (or a setfattr on Linux, xattr on MacOS) to link to its parent, which means 2 forks-and-execs multiplied by tens of millions of times. This fork-and-exec thing could be neutralized if you can develop the entire first pass in a language that allows you to use the involved system-calls directly, which are mkdir(2) and symlink(2)/setxattr(2).

Concretely, a simple example script for the first pass (mostly as a pseudo-code just to show the basic operations to apply) might be:

while read -r child parent; do
    # here I use '-p' only for 'no error if existing'
    mkdir -p $child $parent  # <-- note lack of quotes for once, so to ignore empty $parent
    [ $parent ] && (cd $child && ln -s ../${parent} parent)
done

The script assumes each child/parent pair is separated by space and on a line on its own, and expects the already known roots as a line each with just one ID (i.e. no parent), everything provided on stdin.

For simplicity of demonstration, the script does not use intermediate subdirectories, i.e. it creates all nodes/dirs in one (actually current) directory. As said, this is a no-no when having more than 1M nodes.

Providing one (or more) sublevel(s) of directories requires knowledge of the nodes' IDs characteristics, in order to choose the best partitioning approach. For example, if the actual address-space used by your 20-digits IDs is evenly distributed, you might go with a simple modulo operation, possibly repeated at additional levels of sub-directories. The important point is that any sub-level can be computed from the ID, which means for example that you cannot use a mere increasing counter at each node added.

Should you come out still alive (;-)) from the first pass, the second pass might even be a breeze, even with just a shell script like the one below:

#!/bin/bash

# make sure $PWD has physical dir
cd -P .
fs="${1:-$PWD}"

# for each node
while read -r node; do
    cd "$node"
    # check that node does not already have a root: if it does, read that and do not enter the loop
    while ! { [ -e myroot ] && read -r root < myroot; }; do
        # remember visited node
        traversed+=("$node")
        # if node does not have parent it is a root, so quit loop
        [ -L parent ] || { root="$node" && parents+=() && break; }
        # go up to parent, which becomes node to consider
        cd -P parent
        node="$PWD"
        # add to visited parents
        parents+=("$node")
    done
    # cd back to the root of this filesystem
    cd "$fs"
    for ((i=0; i < ${#traversed[@]}; i++)) ; do
        # for each traversed node (if any) set its root and display it
        echo "$root" > "${traversed[i]}/myroot"
        echo "${traversed[i]##*/}" "${parents[i]##*/}" "${root##*/}"
    done
    traversed=()
    parents=()
done < <(find "$fs" -mindepth "$((${2:-0}+1))" -type d)

Note though that a compiled language could naturally be quicker, and would certainly be a lot quicker if you store parents and roots in each node/dir's extended attributes instead of in symlinks and files

This script never needs to fork-and-exec, and marks parents encountered while traversing nodes upwards so to never traverse a branch more than once. It also allows any fixed number of intermediate subdirectories containing the actual nodes, and it expects the filesystem's root and the number of intermediate subdirectories as arguments, so you would run it like in:

traverse.sh /mnt/dataset-on-filesystem 3

where 3 would mean 3 levels of subdirectories before the nodes own directories.

The procedure used by this script would greatly benefit from receiving the deepest chains first, provided that they are also shared by many other shallower chains, because that would mark many parents at an early stage so that many following chains would need much less traversing and thus the script would consume all nodes much more quickly.

After running this, besides having the full desired output on stdout, you'd also have each node's root stored in the node's dir's myroot file, which you could then just cat at will any time.

Finally, note that many details of this solution can have room for optimizations besides the filesystem's features, e.g. by doing some caching during the two passes, or depending on whether (or how) your IDs can be packed besides being 20 digits long, or depending on their actual address-space and its sparseness, and of course depending on how already (un-)ordered the input data-set is.

11
  • Could you give an estimation of disk space used? Jun 21, 2019 at 22:31
  • @wassrubleff at a purely logical level, one dir for each single child node. Then it depends on what filesystem you use. You might incur in inodes number limits because every dir is an inode. Physical space occupied for each directory again depends on the filesystem used. Then each symlink would be as big as the number of characters of the ID used plus ../
    – LL3
    Jun 21, 2019 at 22:34
  • For the purposes of my specific situation, let's assume it's MacOS, APFS, 2 TB SSD (1.76TB to be precise), High Sierra 10.13.6. Jun 21, 2019 at 22:40
  • @wassrubleff I'm not at all expert on MacOS, even less on APFS, but it is reported to accept as many as 2^63 number of files [ en.wikipedia.org/wiki/Apple_File_System ]. So basically no limits there. Wrt to space occupied, you mentioned 20 digits each ID, plus 3 for the ../, multiplied by the total number of single IDs would make a good estimate for disk space required
    – LL3
    Jun 21, 2019 at 22:52
  • So what would be your rough estimate for disk space required? Jun 21, 2019 at 22:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .