1

I have a dataset of the following format. Field 1 lists an identifier, field 3 lists data points, and field 2 counts those data points.

id1      5        E1, E2, E3, E4, E5
id2    4        E3, E4, E5, E6
id3 2        E6, E7
id4    1        E8
id5    2        E1, E8

I need a script that, when limited to X number of identifiers, will be able to tell me which X identifiers will cover the maximum number of data points, non-redundantly (but with a preference for redundant coverage when able, for example id5 will always be chosen over id4 no matter what). Additionally, I'd like to know the fraction of total data points that will be covered and which identifiers will be covered.

I would prefer a perl solution, but if this can be accomplished better in another way then I am not limited.

Here is an example output if I choose X=3 identifiers:

id1, id3, id5    8/8        E1, E2, E3, E4, E5, E6, E7, E8

Or if I take X=2 identifiers:

id1, id3    7/8        E1, E2, E3, E4, E5, E6, E7

id1 will be chosen because it covers the most data points by itself. id2 covers the next most; however, all but one of those data points is already covered by id1. id3 covers the next most data points non-redundantly, so it becomes the second choice. id4 and id5 both add one non-redundant data point; however, id5 additionally adds a redundant data point so it is chosen over id4.

My dataset includes some 12 million identifiers and ~3.5 million non-redundant data points, so crafting the script to run as cleanly as possible will be preferable (some identifiers are associated with upwards of 9 thousand data points). I expect that the actual values I'll use for X will be anywhere between X=12 and X=40.

This is my first question here and it (to me at least) is a rather complicated one, so I hope that I've formatted and explained everything well enough to get my question across. Thanks for the help!

  • What have you tried and what specifically doesn't work? We're not a script-writing service (although some users here might offer consulting services privately/commercially). – roaima Sep 30 at 22:28
  • To be honest, I am unsure how to approach this problem. A partial solution would be picking the identifier associated with the most datapoints and "fixing it." Then removing each of those datapoints from the dataset and repeating the process to find the next identifier that is associated with the most data points from the revised dataset. Doing X iterations of this will give you a reasonable approximation. This is the best solution I've thought of, however, it is very clumsy. – Ryan O'Hara Sep 30 at 22:36
0
#!/usr/bin/perl

use strict;
use Set::Tiny;

my $max = shift;

# A set to hold all unique data_points:
my $all_dps = Set::Tiny->new();
# hash of sets. key is id, val is the set of data_points for that id:
my %ids = ();
# hash containing the number of data_points for each id:
my %counts = ();

# read the input file, parse into %ids
while(<>) {
  chomp;
  my ($id,$count,$dp) = split /\s+/,$_,3;            #/
  $ids{$id} = Set::Tiny->new(split /\s*,\s*/, $dp);  #/
  # The "#/" commentS exists solely to fix U&Ls perl syntax highlighting
  $counts{$id} = $count;

  $all_dps = $all_dps->union($ids{$id});
};

my $total_dps = keys %{ $all_dps };

# array to hold the list of output ids:
my @idlist=();
# set to hold the output data points:
my $data_points = Set::Tiny->new();
# count of output data points:
my $dpcount=0;

# stop when id list is = max. or when the count of output data points is equal
# to he total data points. or when there are no non-empty keys left.
while ((@idlist < $max) && ($dpcount < $total_dps) && (keys %ids > 0)) {

  # sort the counts hash by value.
  my @counts = ( sort { $counts{$b} <=> $counts{$a} } keys %counts );

  # add the sets from the id with the highest count to the output set.
  $data_points = $data_points->union($ids{$counts[0]});
  # and add that id to the output id list
  push @idlist, $counts[0];
  $dpcount = keys %{ $data_points };

  foreach (keys %ids) {
    my $diff = $ids{$_}->difference($data_points);

    if (keys %{$diff} == 0) {
      # delete ids with no difference from the current data_points set.
      delete $ids{$_};
      delete $counts{$_};
    } else {
      # add the intersection count as a decimal fraction so ids with more
      # dupes sort slightly higher.
      my $intersection = $ids{$_}->intersection2($data_points);
      $counts{$_} = (keys %{$diff}) . "." .  (keys %{$intersection});
    };
  };
};

print join(",",@idlist) .  "\t$dpcount/$total_dps\t" .
  join(",",(sort keys %{ $data_points })) .  "\n";

This script first reads in the entire input file and uses the perl Set::Tiny module to build a "set" (i.e. a perl hash) and a hash containing the count of set elements for each id. Set::Tiny is available from the CPAN link above, or it may already packaged for your distribution (e.g. on Debian: sudo apt-get install libset-tiny-perl).

Then, it repeatedly tries to build the largest output set possible by:

  • sorting the current %counts hash by value
  • adding the largest set to the output set (i.e a union)
  • deleting all sets (and associated counts) which don't have any data points that aren't already in the output set.
  • updating the counts hash for the ids that weren't deleted to be equal to the number of data points NOT in the output set plus a decimal fraction equal to the number of data points that ARE in the output set (so that ids with more redundant data points sort higher than those with fewer or none).

This is essentially the algorithm you described as "clumsy" in your comment. I prefer to think of it as "straight-forward" or "brute-force" :-)

I tried a few different ways of optimising this, but I was unable to find a more efficient method. That doesn't necessarily mean there isn't one. It just means I couldn't find it. The primary difficulty is the requirement to prioritise ids with more redundant data points.

Anyway, I don't have an input file with millions of entries, so I was unable to do any timing tests. I'd be interested to know how fast it runs with a full data set. and also how well it performs if you use MLDBM or similar as mentioned below.

This script is going to use a lot of of RAM. If you have 12 million IDs, it'll use approximately 12 MB * (the average id string length + the average data points length per id). This could be a problem if you have less than 32GB or perhaps even 64GB of RAM available.

If the script does exceed your your available RAM and causes swap thrashing, you could use the MLDBM module or one of the Tie:: modules to store the %ids hash (and maybe the %counts hash too) in a database rather than in memory. e.g. Tie::DBI to use a sqlite or mysql or postgresql etc database.

Using MLDBM or a Tie:: module may not be any faster (although it might, because it won't thrash RAM and swap), but a) the script is far less likely to die before finishing due to out-of-memory condition, and b) it will be far less harmful to other processes running on your system (which may otherwise end up being killed due to lack of memory).

e.g. add the following immediately after the my %ids=() and my %counts=() lines to use a Berkeley DB file for %ids:

       use MLDBM qw(DB_File Storable);
       use Fcntl;
       my $id_db = tie %ids, 'MLDBM', './ids.db', O_CREAT|O_RDWR, 0640 or die $!;

and maybe this too, to tie the %counts hash to a DB database:

       my $count_db = tie %counts, 'MLDBM', './counts.db', O_CREAT|O_RDWR, 0640 or die $!;

Sample output:

I saved this script as ryan.pl, made it executable with chmod +x ryan.pl and ran it as:

$ ./ryan.pl 1 input.txt
id1     5/8   E1,E2,E3,E4,E5

$ ./ryan.pl 2 input.txt
id1,id3 7/8   E1,E2,E3,E4,E5,E6,E7

$ ./ryan.pl 3 input.txt
id1,id3,id5     8/8   E1,E2,E3,E4,E5,E6,E7,E8

It's hard to see here on U&L but the output is tab-separated.


Some preliminary testing (with a 145MB input file with 1 million lines, each containing from 1 to 20 random dictionary words as the data_points) showed that my original guess about memory usage was completely wrong.

Loading the sets into RAM took around 23 minutes (and that's just to load the data file without processing it), and consumed 1GB RAM on my Phenom II 1090T (with 32GB RAM installed but only about 8GB free).

Using MLDBM took about 21 minutes to load the data file. It created an ids.db file of 323MB and counts.db of 78MB. It used a constant 9.3MB of RAM while doing so.

So, I'm guessing that your data file is at least 10-20 times that size, so is unlikely to fit in RAM. Use MLDBM, preferably on an NVME SSD for best performance.


Since you requested it, here's an updated version of the script. Maybe you can extract some usable ideas from it.

It's at least twice as fast as the previous version. It took only 15 minutes to not only read in my 145MB test file but also process it and produce a result for 12 identifiers - the best I could get with other optimisation attempts was about 33 minutes.

It is, IMO, still entirely unsuitable for extremely large data sets such as the 104GB file you mentioned.

If you still want to try it, though, I'd recommend splitting it into two scripts. One to populate the .db files (everything up to and including the while (<>) loop), and a second script (everything before that while (<>) loop but without the unlink statements of course, and then pretty much everything after it) to work on a COPY of the .db files.

That's because at least half the run-time is in reading your text file and storing it in the .db files. For multiple runs, it will be much faster to just copy the .db files and process the copy than to generate them from scratch on every run.

(copies are needed because the script modifies and deletes entries in the %ids and %counts hashes as it processes the data. working on a copy allows you to quickly reset the .db files back to starting conditions)

#!/usr/bin/perl

use strict;
use Set::Tiny;

# The first arg is the maximum number of identifiers we want.
# Any remaining args (and stdin) are input.
my $max = shift;

# hash of sets. key is id, val is the set of data_points for that id:
my %ids = ();

# hash containing the number of data_points for each id:
my %counts = ();

# The following two arrays exist to minimise memory usage, so that datapoints
# which appear in multiple IDs are stored in %id by reference rather than
# value.
#
# Array containing each datapoint indexed numerically
my @dp=();
# Hash containing each datapoint indexed by value
my %seen=();

use BerkeleyDB ;
use MLDBM qw(BerkeleyDB::Btree Storable);

# delete the .db files
unlink './ids.db';
unlink './counts.db';
unlink './seen.db';
unlink './dp.db';

# use MLDBM for the %ids hash - we need to serialise the Set::Tiny
# data structures.
tie %ids,    'MLDBM', -Filename => 'ids.db',    -Flags => DB_CREATE or die "Cannot open database 'ids.db': $!\n";

# It's faster to use BerkeleyDB directly for the other arrays (they
# contain scalar values, so there is no need for serialisation)
tie %counts, 'BerkeleyDB::Btree', -Filename => 'counts.db', -Flags => DB_CREATE or die "Cannot open database 'counts.db': $!\n";
tie %seen,   'BerkeleyDB::Btree', -Filename => 'seen.db',   -Flags => DB_CREATE or die "Cannot open database 'seen.db': $!\n";
tie @dp,     'BerkeleyDB::Recno', -Filename => 'dp.db',     -Flags => DB_CREATE or die "Cannot open database 'dp.db': $!\n";

my $total_dps=0;
# read the input file, parse into %ids
while(<>) {
  chomp;
  # split input line on spaces with max of 3 fields.
  my ($id,$count,$data) = split(/\s+/,$_,3);   #/

  # split $data by commas
  my @data = split(/\s*,\s*/, $data);          #/
  my $data_count = @data;
  my @data_by_idx = ();

  # convert @data to  @data_by_idx
  for (0..$#data) {
    if (!defined($seen{$data[$_]})) {
      # We haven't seen this datapoint before, so add it to both @dp
      # and %seen.
      $dp[++$total_dps] = $data[$_];
      $seen{$data[$_]}=$total_dps;
    };
    # add the datapoint's index number to @data_by_idx
    push @data_by_idx, $seen{$data[$_]};
  };
  $ids{$id} = Set::Tiny->new(@data_by_idx);

  $counts{$id} = $count;
};

# array to hold the list of output ids:
my @idlist=();
# set to hold the output data points:
my $data_points = Set::Tiny->new();
# count of output data points:
my $dpcount=0;

my $biggest_id='unknown';
my $biggest_count=0;

# stop when id list is = max. or when the count of output data points
# is equal to he total data points. or when there are no non-empty
# keys left.
while ((@idlist < $max) && ($dpcount < $total_dps) && (keys %ids > 0)) {

  # find the id with the most data points without using sort().
  if ($biggest_id eq 'unknown') {
    foreach (keys %counts) {
      if ($counts{$_} > $biggest_count) {
        $biggest_count = $counts{$_};
        $biggest_id = $_;
      };
    };
  };

  # add the sets from the id with the highest count to the output set.
  $data_points = $data_points->union($ids{$biggest_id});
  # and add that id to the output id list
  push @idlist, $biggest_id;
  $dpcount = keys %{ $data_points };

  $biggest_count=0;

  foreach (keys %ids) {
    my $diff = $ids{$_}->difference($data_points);

    if (keys %{$diff} == 0) {
      # delete ids with no difference from the current data_points set.
      delete $ids{$_};
      delete $counts{$_};
    } else {
      # add the intersection count as a decimal fraction so ids with more
      # dupes sort slightly higher.
      my $intersection = $ids{$_}->intersection2($data_points);
      $counts{$_} = (keys %{$diff}) . "." .  (keys %{$intersection});
      # find the new id with the most data points.
      if ($counts{$_} > $biggest_count) {
        $biggest_count = $counts{$_};
        $biggest_id = $_;
      };
    };
  };
};

print join(",",@idlist) .  "\t$dpcount/$total_dps\t";
print join (",", (map $dp[$_], keys %{ $data_points })), "\n";

As for your other question in the comment (i.e. how to split the data for multi-core processing on a cluster), I have no idea.

I don't think this IS a task amenable to sharding the data, processing the shards in parallel, and then combining the results because AFAICT any such process would need access to the entire dataset to produce any meaningful output.

This task is I/O-bound, rather than CPU-bound anyway - it's not computationally difficult or "expensive", it just takes a lot of time (and memory) to read and process the enormous data set.

Don't take my word for that, thought. I know almost nothing about your data or what you're trying to do. Someone who a) understands your dataset better and b) knows what you're trying to get out of it may be able to shard your data effectively and still be able to combine the result sets.

  • Hi, thanks so much for the detailed response and I apologize for replying so slowly. I was hoping to have a little more to update you on but all I can say is that I'm currently running the original script (on a super computer node) and that it's been running for about 3 and a half days with x set to 20. Some info about my input file, it's ~104Gb and the top id is associated with ~164,000 datapoints, the next id has ~152,000 datapoints, etc etc down to 1. One question I did have was how does the script handle ids with identical numbers of datapoints associated to them? Again, thank you so much. – Ryan O'Hara Oct 11 at 19:20
  • I actually continued working on that script for a while, testing how well it performed with various optimisation attempts. The best optimisation I found was to NOT use sort() to find the ids with the most datapoints (because that massively inflates memory usage), but to use a loop to find them instead. The second best optimisation was to use BerkelyDB::Btree and Storable with MLDBM (rather than the defaults of SDBM and Data::Dumper). The bad news, though, is that it's going to use an enormous amount of RAM and/or time no matter what you do. – cas Oct 12 at 1:18
  • I can add an updated version of my script, but like my original above, it is barely usable with an input file of 145 MB. It would be entirely unsuitable for 100+ GB input. – cas Oct 12 at 1:20
  • BTW, to answer your question - it doesn't do anything special to handle ids with the same number of data points, it just uses the first one it sees with the largest number of data points. And since sorting the keys will cause RAM usage to blow out and perl hashes are inherently unordered, the first id it sees is semi-random. – cas Oct 12 at 1:22
  • Any updated script you have would be much appreciated. Is there any way to further optimize the script to split the workload under the assumption that I'll be executing the script on a supercomputer (each node has around 30-40 CPUs and I can have access to up to 16 nodes at any given time). – Ryan O'Hara Oct 15 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.