Problem You've spent over half your post describing your solution for a minimal version of your problem, that doesn't scale. But you haven't actually state what the problem is.

For example. You've told us that you've a 2d array of integers; that those integers range between 1 & 3e6 (twice) ; and there are ~50000 in each inner array.

But you fail to say how big the main array is?

Or what you need to look up. Ie. what do you start with; and what information do you need to end up with?

Or how many lookups you need to do?

And will you do these lookups once? Or once a week? Or once an hour?

Fair enough

"But you fail to say how big the main array is? "

not that big, the size of the main array is 3000. n is 500-1000 (the number of inner arrays from which i need to pick)

"Or what you need to look up. Ie. what do you start with; and what information do you need to end up with?"

i start with my query array which is 500-1000 different ints between 0 and 2999 and i need to end up with the int value from inner arrays that is the most prevalent on those picked 500-1000 arrays. (intersect that has the highest number of elements)

"Or how many lookups you need to do? "

about 15000000 per hour.

"Or how many lookups you need to do? " about 15000000 per hour.

That's 4000 per second or 1 every 1/4 of a millisecond.

In that time you want to intersect 500 to 1000 (from 3,000) sets of 50,000 integers and extract the single most populous integer across them all.

Do you have a 3000 machine cluster available to throw at this problem?

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

A problem rather similar to Comparing two arrays, don't you think? Sparse matrix again, this time 3k by 3M booleans, density 1/60. Exact same solution is viable, too: pack your int-vectors as "l/l", merge-sort n query vectors and scan. Perhaps an 8-core machine to achieve 4k queries per sec.

Speed vs memory trade-off is also possible. Pairwise intersections of your 3000 vectors amount to 4.5M vectors of size ~833. Lookup with small n==4 is 6 combinations ie merge 6*833 == 5k elements instead of 4*50k == 200k elements. About 30-fold speed-up at the cost of 14 GB of memory.

GPU-based solution would be quite interesting, but for that you really ought to ask another forum.

Perhaps an 8-core machine to achieve 4k queries per sec.

Prove it :)

---

With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

See the referenced thread. I later implemented a partial SSE version as well (merge using SSE, scan not optimized). Result:

Total 301068 elements in 30 vectors
timethis for 5:  5 wallclock secs ( 5.31 usr +  0.00 sys =  5.31 CPU) 
+@ 439.36/s (n=2333)
[download]

Update:

Total 200752 elements in 4 vectors
timethis for 5:  6 wallclock secs ( 5.28 usr +  0.00 sys =  5.28 CPU) 
+@ 1326.33/s (n=7003)
[download]

Update2: Right you are, BrowserUk, I was considering small n case only.

Total 50063728 elements in 1000 vectors
timethis for 5:  6 wallclock secs ( 6.32 usr +  0.00 sys =  6.32 CPU) 
+@  0.63/s (n=4)
[download]