In this unit, we're going to look at
several algorithms that improve upon A-Priori.
One direction is to use the portion of main memory that
the A-Priori algorithm doesn't need on the first pass,
because all it's doing is counting singleton item sets.
That is the PCY or Park-Chen-Yu-Algorithm.
We'll talk also about further extensions called multistage and multihash.
All these extensions to A-Priori have the goal of minimizing the number of
pairs that actually have to be counted on the second pass.
Then we'll go in another direction.
We'll accept that the result might not be accurate, that is,
we'll allow the algorithm to fail to identify some of the frequent item sets.
But we want to finish quickly.
Preferably in only one pass or perhaps one pass and a little more.
Several approaches of this type will also be dis, discussed.
Now, the essence of the PCY algorithm is to take advantage of
the fact that if the set of items is modest in size.
We have lots of space during the first pass that we don't seem to need.
We can in fact do some counting that will give us the smaller candidate
set of pairs.
That will help us on the second pass where the main memory is
often the critical resource, since we don't have to store as many counts.
Okay, what Park Chen Yu suggested was that we
can hash all pairs into a large number of buckets.
However, these buckets do not hold the pairs himself,
just the count of how many baskets contain pairs that hash to that bucket.
Thus, the space needed for a bucket is small.
Four bytes is surely sufficient, and
we might get away two bytes if this four threshold is less than 2 to the 16th.
Notice that it is not possible to store in main memory all the pairs themselves.
We're trying to avoid having to use some space for
every possible pair in main memory.
So, on the first pass when we read a basket we not only increment the count for
each of it's items as we did for the first pass of A-Priori.
We also hash each pair that is contained in the basket.
And for each resulting bucket, we increment it's count by one.
Now, let's call a bucket frequent if after the first pass we
find that its count is at least equal to the support threshold.
A bucket could become frequent simply because many pairs each
contribute a little its total count.
We can't tell if that's the case, because we only had room to remember the total,
not the count of each individual pair that contributed to the bucket.
But in the opposite case, we win.
If a bucket is not frequent,
then no pair that hashes to it could possibly be frequent.
So, on the second pass, we only need to,
need to count pairs that hash to a frequent bucket.
And of course, we use, the usual A-Priori trick works too,
we only have to count the pair if both its, its members are, are frequent items.
So, here's the picture of PC Y that I'd like you to have.
Okay, on the first pass we use a little space to count the items and
the rest of the space is devoted to these bucket counts.
On the second pass, we keep a table of frequent items, that's,
that's that just, just as we did for A-Priori.
But we also summarize the results of hashing pairs on the first pass,
by what we'll call a bitmap.
That's, that's this.
For each bucket,
the bitmap has one pair that says whether the bucket is frequent or nice, not.
So this is a bucket and if it has a count, let's say that it's s plus one.
It's pa, it's, it's frequent.
Then it corresponds to some bit here that's a 1.
Okay.
Another bucket that has a count, let's say s minus 100 that's not frequent,
so it would get, its corresponding bit would be a, a 0.
Okay, if the bucket says four bytes, then we get a 32.1 com,
to 32 to 1 compression and yet we have all the information we need for
the second pass, which is, is the bucket frequent or not.
Thus we have almost as much space on the second pass that
count candidate pairs as we would for A-Priori.
That's of course this, this area, but we hope that because the bucket accounts will
eliminate most of the candidates that A-Priori would have to handle.
There will be many fewer pairs to count on the second pass.
If that is the case, then the PCY algorithm might be able to
operate main memory on the second pass while A-Priory would run out of space or
have to use disk.
On pass one, we use what space we need to count the occurrences of each item,
just as A-Priory does.
Typically four bytes per item will do nicely.
But the difference is that whatever space we do not need for
counting items is given over to as large a hash table as we can.
For each bucket is a count, typically a 4-byte integer as well.
So, here's the pseudo code for the first pass of the PCY Algorithm.
We, read each basket once, as we would on any pass of any algorithm.
Well, we look at each item in the basket and add one to its count.
Okay, that of course, is just what A-Priory does.
The additional work on the first pass of, of PCY, is we have to look at each pair of
items and hash the pair to some bucket and increment the count for that bucket.
I want to remind you of two important observations about the buckets.
Okay.
first, if a pair is frequent, then the bucket, it hashes to is,
is surely frequent.
Thus on the second pass, the bit, in the bit map for
that bucket will be one, and we will surely maintain a count for this pair.
Unfortunately, there may be many infrequent pairs that hash to
the same bucket.
These might be counted as second passes as well.
Okay, we can hope that at least one member of the pairs is not a frequent item
because that will inhabit us from counting the pair to the second pass.
But sometimes, you'll have a pair that is not frequent, but both of its,
its items are frequent and it hashes through a frequent bucket.
That pair will be counted on the second pass even though it is not frequent.
It is also possible that a bucket will be, be frequent but
there is no frequent pair hashing to that bucket.
Remember each bucket's count is the sum of the counts of all of
the pairs that hash to it.
But the only time that we have to count a pair in the second pass, and
that pair turns out to not to be frequent,
is when the pair consists of two frequent items and for one of
the two reasons I've just mentioned it's, it's bucket turns out to be frequent.
However, we get a lot of leverage when a bucket is not frequent.
In that case, we do not have to count any of the pairs that count for
that bucket even if that pair consist of two frequent items.
After pass one, we set up pass two by doing the following first we construct
the bitmap from the buckets.
This bitmap has one bit for each bucket in order.
So, we can easily look up the bit that corresponds to a given hash value.
One means the bucket was frequent, zero means it was not.
And as discussed, if the buckets are 4-byte integers,
we get it's 32 to 1 compression when we, replace the buckets by the bitmap.
And as in the A-Priori algorithm,
we need to create a list of the frequent items to use on the second pass.
Actually on, on pass two is to count the candidate pairs.
In the PCY algorithm, in order to be a candidate pair, I,
J must satisfy two different conditions.
Okay.
First of all, both I and J must have been found frequent on the first pass.
For A-Priori, this is the only condition, and
all pairs satisfying it are candidates.
But the new condition is that the pair itself must hash to
a bucket that was found frequent in the first pass.
It is easy to see that if the pair i,j is really frequent,
then both these conditions will be satisfied.
So, this pair will be counted.
Condition one follows from monotanicity and condition two is satisfied because
the count of the bucket is the sum of the counts of all the pairs that hash to it.
That count cannot be smaller than any of the individual counts.
We expect that each bucket requires only a small number of bytes.
Four is almost sure to be enough, and in many cases,
we can get by with two bytes per bucket.
Okay. The reason is that it
is sufficient to count after this poor threshold S, even though we said we
should always increment the count, when a pair hashes to the bucket.
What we really want to do is, if the current count is less than S, and
increment the count, otherwise leave the count at S.
The number of buckets, will be some reason or
fraction of the size of main memory, typically almost half or a quarter.
The only time that would not be true is if there were so
many different items, that we needed all of most of main memory just to count them.
In that case we could not use the PCY algorithm.
When we count pairs on the second pass, we have to use the tabular method.
The problem is that the pairs that are eliminated because they hash to
an infrequent bucket, are scattered all over the place, and cannot be or, or,
organized into a nice triangular array.
As a result, we should not use PCY unless we can eliminate at least two-thirds of
the candidate pairs when compared with A-Priori.
We're now going to introduce an improvement on PCY called multistage.
This algorithm actually uses more than two passes to find frequent pairs.
We'll concentrate on the three pass version.
The benefit of the extra pass is that on the final pass,
when we have to count the candidate pairs, we've eliminated many of
the candidates that PCY would count but that turn out not to be frequent.
The three stage version begins with the first pass of PCY.
The second pass however,
is a repeat of the first pass of PCY with a different hash function.
The third pass has a stringent requirement for candidacy.
The pair not only must hash to a frequent bucket on the first pass, but
must also hash to a frequent bucket on the second pass.
And on the second pass we don't increment the bucket counts with just any pair.
Rather we only implement the count when the pair meets the criteria to
be a candidate on the second pass of PCY.
That is it must consist of two frequent items and
it must have hashed to a frequent bucket.
As a result on the second pass, we get two benefits.
First the total count of all the buckets will be less,
because there's some excludes, some of the pairs that appear in the data.
That means that it is less likely that a bucket will be frequent on
the second pass unless it includes a frequent pair.
But also in the case that a pair is not frequent,
it will only become a candidate if it accidentally hashed to
a frequent bucket on both passes not just one pass as for PCY.
So, here's a picture of the three stage algorithm as I
said before the first passage is PCY.
Okay, the second pass involves features from both passages of PCY.
On this pass, we store the frequent items that's this.
And we summarize the buckets in a bib, bitmap as before.
We use both these features to establish which pairs are candidates on
the second pass.
But in the multistage algorithm we don't count
pairs just because they're candidates.
We just hash the candidates to another hash table,
using a different hash function.
This has, hash table is approximately as large as the hash table in the first pass,
depending upon whether the bitmap plus the list of frequent items takes up more or
less, or less space than the counts of all the items on the first pass.
Okay, for the third pass,
we, we maintain the list of frequent items and the first bit map.
But we also summarize the buckets of the second hash table by a second bit map.
And now, we count all the candidate pairs, where to be a candidate you have to
satisfy three conditions on the next slide.
On the third pass, the, the candidate pairs are defined as follows.
There's both items are frequent by themselves,
this is the A-Priori condition for candidacy.
And then according to the hash function used for
the first pass, the pair hashes to a frequent bucket.
These first two conditions are the PCY conditions for candidacy.
And finally, according to the hash function used on the second pass,
the pair also hashes to a frequent bucket.
Here are two points about multistage that we should bear in mind.
Okay, the first,
the hash functions used at each stage need to be independent of one another.
Otherwise, each would report the same frequent buckets, and
we wouldn't get any benefit from the additional stage.
A common question about this algorithm is, why we need the second condition that
the pair hashes through a frequent bucket on the first pass?
Afterall, unless a par,
a pair meets the second condition it's not hashed to a bucket on the second pass.
But if we don't enforce the second condition along with the other two
conditions on the third pass, then we can get another, an unnecessary candidate for
the third pass.
So consider a pair i,j where i and j are frequent, but the pair is not frequent.
Okay. Moreover,
the pair hashes to an infrequent bucket on the first pass.
Now, it is possible that i,j hashes to a frequent bucket on the second pass.
True.
The, in the multistage algorithm, i,j is not hashed on the second pass, and
doesn't contribute to the count of its bucket.
But there's still some bucket that wou,
it would have hashed to had we hashed it on the second pass.
And that bucket might be frequent for
reasons that have nothing to do with i and j.
so, we must test condition two along with the other conditions.
Next, we're going to look at an approach called mulithash.
This algorithm is similar to PCY, except that on the first pass, the available
space is divided into several hash functions and this idea could be insane.
Remember that PCI works if the average count of a bucket is much less than
the support threshold S.
That way most buckets are infrequent, then we could eliminate a lot
of pairs from the candidate set for the second pass.
If we have the number of buckets, we double the average count.
So, suppose the average count for
both hash tables is going to be over the threshold.
Then, almost all buckets are frequent and
you, and you eliminate almost nothing on the second pass.
But let's be optimistic.
Okay, if PCY gives you an average count of 1 tenth of the support threshold,
then you can use five hash tables instead.
Have an average count of half the threshold, and
each hash table will have mostly infrequent buckets.
But now, you have five chances to eliminate a pair that is
not actually frequent.
And the chances are very high that at least one of the hash functions will
send it to an infrequent bucket.
In that case, we get much of the benefit of five stages in
the multi-stage algorithm, but we only, use only two passes, and not six.
So, here's a picture of multihash.
We'll use two hash tables on the first pass.
And the general idea when more than two tables are used should be obvious.
On the second pass, the item counts are summarized as a list of
frequent items just as in PCY or multistage.
But also, the hash table from the first pass is summarized by a mid,
bitmap as in PCY.
Notice that the number of buckets created on the first pass is the same whether we
use one hash table as in, as in PCY or two or any number.
Thus, the sum of the lengths of the bit maps is the same for
multihash, as it is for PCY.
And less than it would be for multi-stage.
On the second pass, we count the candidate pairs as always.
The requirements for a pair i, j to be a candidate pair is what you should expect.
I and j must both be frequent items and for
each hash table, the pair must hash to a frequent bucket.