Exercise 6.3.1: Here is a collection of twelve baskets. Each contains three of t

Question

Exercise 6.3.1: Here is a collection of twelve baskets. Each contains three of the six items 1 through 6. 1,2,3) 2,3,4) 3, 4,5 4,5,6) (1,3,5 2,4,6 1,3,4) 2,4,5) 13,5,6} 1,2,4) 2,3,5) 3,4,6 Suppose the support threshold is 4. On the first pass of the PCY Algorithm we use a hash table with 11 buckets, and the set fi, j) is hashed to bucket i xj mod 11 (a) By any method, compute the support for each item and each pair of items. (b) Which pairs hash to which buckets? (c) Which buckets are frequent? (d) Which pairs are counted on the second pass of the PCY Algorithm?

Explanation / Answer

Answer:

By using ,given data

Here, 12 baskets are given.

Below are the steps or passes for PCY algorithm as follows.

Pass 1:

(i) Determine total number of occurences of allitems called as count.
(ii) For every bucket,consist of items fil; : : :;,hash all pairs to a bucket of hash table,Increment bucket count by 1.
(iii)  Determine ,L1 and the items with the count of atleasts at the end of the pass.
(iv) Determine,buckets with count atleast s at the ende buckets with counts at least s.

Pass 2:

(i) All the frequent items, i.e. L1. holds in main memory.
(ii)  Main memory also holds the bitmap summarizing the results of the hashing from pass 1.
(iii) Main memory also holds a table with all the candidate pairs and their counts.

A pair (x; y) can be a candidate in C2 only if al l of the following are true:

(a). x is in L1.
(b). y is in L1.
(c). (x; y) hashes to a frequent bucket.

(iv) We consider each basket, and each pair of its items and making the test as above.

If all three conditions meets by pair, add to its count in memory, or make an entry for it if one
not yet exist.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.