I'm stewing on a particular task that is likely to reappear from time to time. I'd like to find an efficient way to do this work so it can scale up in future.

In summary, I have Keys and Sources. A Key may come from one or many Sources, a Source may generate one or more Keys. What is the minimal list of Sources which cover the Keys?

I have data in the format "Key|Source", /^[0-9A-F]{40}\|[0-9a-f]{40}$/ 

0000002D9D62AEBE1E0E9DB6C4C4C7C16A163D2C|2f214516cdcab089e83f3e5094928
+fe9611f2f51
000000A9E47BD385A0A3685AA12C2DB6FD727A20|2adeac692d450c54f8830014ee6cb
+e3a958c1e60
00000142988AFA836117B1B572FAE4713F200567|04bb7bbed62376f9aaec15fe6f18b
+89b27a4c3d8
00000142988AFA836117B1B572FAE4713F200567|6935a8fc967a6ffc20be0f07f2bb4
+a46072a397e
00000142988AFA836117B1B572FAE4713F200567|8c88f4f3c4b1aff760a026759ae80
+7af6c40e015
00000142988AFA836117B1B572FAE4713F200567|974c820f53aded6d6e57ca8de2c33
+206e2b5f439
00000142988AFA836117B1B572FAE4713F200567|b05be3e17bb9987ffb368696ee916
+dd9b9c2f9b3
000001BCBC3B7C8C6E5FC59B686D3568132D218C|0d4c09539f42165bb8b1ab890fe6d
+c3d3ca838b3
000001BCBC3B7C8C6E5FC59B686D3568132D218C|9fd421d4e020788100c289d21e4b9
+297acaaff62
000001BCBC3B7C8C6E5FC59B686D3568132D218C|d09565280ebae0a37ca9385bc39c0
+a777a446554
000001E4975FA18878DF5C0989024327FBE1F4DF|55b8ece03f4935f9be667e332d52f
+7db3e17b809
000001EF1880189B7DE7C15E971105EB6707DE83|cd15550344b5b9c2785a13ef95830
+15f267ad667
000002F2D7CB4D4B548ADC623F559683D6F59258|36bed8bdb6d66fb67f409166f5db6
+4b02199812f
0000034C9033333F8F58D9C7A64800F509962F3A|3c4b0a3c1acf6e03111805a0d8b4e
+879df112b7a
000003682106A4CB4F9D3B1B6E5C08820FCFD1B2|cd15550344b5b9c2785a13ef95830
+15f267ad667
00000368B9CFE1B4CF9F3D38F3EFD82840BA280D|50edd315b9217345b1728c38b0265
+7df42043197
000003A16A5A1C6CCDDBE548E85261422489A458|691845459c0ad35b28cce4dffc0e3
+ee8912fb0f5
0000046FD530A338D03422C7D0D16A9EE087ECD9|13e213f346ce624e9be99b356ab91
+25af563a375
0000046FD530A338D03422C7D0D16A9EE087ECD9|67c0da2da88a23a803733cea951e8
+4974b34d029
00000472E2B96A6CD0CBE8614779C5C8197BB42D|0c5e6cdb06c52160ded398d173922
+46269165e0a

[download]

I am now dealing with a 190,000,000+ set of Key|Source pairs. There are 30,000,000 unique Key values and 20,000 unique Source values. There are 23,800,000 Keys that appear only once, so I know I must have at least their Sources in the final set I want. I need to find the smallest set of Sources that cover the 6,200,000 remaining Keys.

I can think of a brute-force iteration method to do this, but there should be a more elegant (and hopefully more efficient) way to find the smallest coverage set of Sources over the 6,200,000 Keys.

My data is usually sorted by Key value, and how I'm used to thinking of it. If I sort on Source value, I might have an inspiration.

So I'm stewing on this...

UPDATE 2014-08-12

I have shrunk the problem set by identifying the keys which only come from single sources. I am now left only to consider the set of many-many key-source relationships. That is 9,197,129 relations, between 1,890 sources and 3,692,089 keys. I was able reduce the key signatures from 40 char to 11 char and source signatures from 40 char to 6 char, to buy myself some space.

Off to bang on this a while...

Complete 170 MB data in 50MB zip file : data_locks_keys.zip
format: key|source

In reply to Contemplating some set comparison tasks by dwhite20899

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.