Association-rule mining has heretofore relied on the condition of high
support to do its work efficiently.  In particular, the well-known
a-priori algorithm is only effective when the only rules of interest
are relationships that occur very frequently.  However, there are
a number of applications, such as data mining, identification of similar
web documents, clustering, and collaborative filtering, where the rules
of interest have comparatively few instances in the data. In these cases,
we must look for highly correlated items, or possibly even causal
relationships between infrequent items. We develop a family of algorithms 
for solving this problem, employing a combination of random sampling
and hashing techniques. We provide analysis of the algorithms developed,
and conduct experiments on real and synthetic data to obtain a comparative
performance analysis.