How to limit my input data for Jaccard item-item similarity calculation? I'm trying to compute item-item similarity using Jaccard (specifically Tanimoto) on a large list of data in the format
(userid, itemid)

An item is considered as rated if i have a userid-itemid pair. I have about 800k users and 7900 items, and 3.57 million 'ratings'.  I've restricted my data to users who have rated at least n items(usually 10).  However, I'm wondering if I should place an upper limit on number of items rated.  When users rate 1000 or more items, each user generates 999000 pairwise-combinations of items to use in my calc, assuming the calculation
n! / (n-r)!

Adding this much input data slows the calculating process down tremendously, even when the workload is distributed(using hadoop).  I'm thinking that the users who rate many, many items are not my core users and might be diluting my similarity calculations.  
My gut tells me to limt the data to customers who have rated between 10 and 150-200 items but I'm not sure if there is a better way to statistically determine these boundaries.
Here are some more details about my source data's distribution.  Please feel free to enlighten me on any statistical terms that I might have butchered!
The distribution of my users' itemCounts:
alt text http://www.neilkodner.com/images/littlesnapper/itemsRated.png
> summary(raw)
   itemsRated      
 Min.   :   1.000  
 1st Qu.:   1.000  
 Median :   1.000  
 Mean   :   4.466  
 3rd Qu.:   3.000  
 Max.   :2069.000  

> sd(raw)
itemsRated 
  16.46169 

If I limit my data to users who have rated at least 10 items:
> above10<-raw[raw$itemsRated>=10,]
> summary(above10)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  10.00   13.00   19.00   34.04   35.00 2069.00 
> sd(above10)
[1] 48.64679
> length(above10)
[1] 64764

If I further limit my data to users who have rated between 10 and 150 items:
> above10less150<-above10[above10<=150]
> summary(above10less150)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  10.00   13.00   19.00   28.17   33.00  150.00 
> sd(above10less150)
[1] 24.32098
> length(above10less150)
[1] 63080

Edit: I dont think this is an issue of outliers as much as the data is positively skewed. 
 A: I'm confused: shouldn't you only need the 7900^2 item similarities, for which you use ratings from all users, which is still quite sparse?
UPDATE
I still think there's a more efficient way to do this, but maybe I'm just being dense. Specifically, consider item A and item B. For item A, generate a U-dimensional vector of 0's and 1's, where U is the number of users in your data set, and there's a 1 in dimension i if and only if user i rated item A. Do the same thing for item B. Then you can easily generate the AB, A and B terms for your equation from these vectors. Importantly, these vectors are very sparse, so they can produce a very small data set if encoded properly.


*

*Iterate over the item ID's to generate their cross product: (ItemAID, ItemBID)

*Map this pair to this n-tuple: (ItemAID, ItemBID, ItemAVector, ItemBVector)

*Reduce this n-tuple to your similarity measure: (ItemAID,ItemBID,SimilarityMetric)


If you set up a cache of the ItemXVector's at the start, this computation should be very fast.
A: I've solved similar problem with MinHash which is specifically designed to approximate Jaccard distance.
Idea is simple using MinHash probabilistic features you group your data into smaller groups (with same hash(s)) and then evalaute pairwise distance inside group (kind of block structure of matrix). The final answer is not exact but you can control how close it to exact by changing depth and amount of hashes.
