Az Apriori volt az egyik legelső algoritmus, amely sikeresen kezelte a gyakori elemhalmaz ok számának exponenciális növekedését. Ezt az apriori-elv alkalmazásával éri el, mely az exponenciális keresési teret csökkenti le. A jelentős teljesítményjavulás ellenére az algoritmust visszafogják a jelentős mennyiségű I/O műveletek, hiszen az algoritmusnak többször is végig kell olvasnia a tranzakció s adatbázist. Ezen túl, ahogy azt 6.2.5. szakaszban láttuk, az Apriori algoritmus teljesítménye jelentősen visszaeshet sűrű adathalmazok esetén a tranzakció k növekvő szélessége miatt. Számos alternatív módszer készült ezen korlátozások kiküszöbölésére, illetve az Apriori algoritmus teljesítményének növelésére. A továbbiakban ezen módszerek áttekintő bemutatása következik.

Az elemhalmazháló bejárása

A gyakori elemhalmazok keresése elvileg az elemhalmazháló bejárásaként is tekinthető (lásd a 6.1. ábrát). Az algoritmus által választott keresési stratégia meghatározza a hálóstruktúra bejárását a gyakori elemhalmazok előállítása során. Bizonyos keresési stratégiák jobbak, ez a hálóban található gyakori elemhalmazok szerkezetétől függ. A továbbiakban ezeket a stratégiákat tekintjük át.

Az elemhalmazhálót azonban mélységi kereséssel is be lehet járni, ahogy az a 6.21. (b) illetve a 6.22. ábrákon látható. Az algoritmus kezdheti például a 6.22. ábrán az a csomóponttal. Az algoritmus kiszámítja a csúcs támogatottságát annak eldöntése érdekében, hogy gyakori-e. Ha gyakori, akkor az algoritmus fokozatosan továbblép a következő szintekre: ab , abc , stb. Ha az algoritmus egy nem gyakori csúcsot talál ( például abcd ), akkor visszalép egy másik ágra ( például abce ), s onnan folytatja a keresést.

A mélységi keresést gyakran a maximális gyakori mintákat kereső algoritmusok használják. Ezzel a keresési stratégiával gyorsabban fel lehet fedezni a gyakori elemhalmazok határát, mint a szélességi kereséssel. Amint találtunk egy maximális gyakori mintázatot, a részhalmazain jelentős ritkítást tudunk végezni. Ha például a 6.22. ábrán a bcde csúcs maximális gyakori, akkor az algoritmusnak nem kell végigjárnia a bd , be , c , d és e csúcsokból induló részfákat, ugyanis ezekben egyetlen maximális gyakori elemhalmaz sem lesz. Ha azonban abc maximális gyakori, akkor csak az ac és bc csúcsok nem maximális gyakoriak (viszont az ac és bc részfái tartalmazhatnak maximális gyakori elemhalmazokat). A mélységi keresés egy másfajta nyesési módszert is lehetővé tesz, amely az elemhalmazok támogatottságára épít. Tegyük fel például , hogy az {a,b,c} támogatottsága azonos az {a,b} támogatottságával. Ekkor az abd és abe csúcsok részfáit ki lehet hagyni, mivel biztosan nincsenek bennük maximális gyakori elemhalmazok. Ennek a bizonyítását gyakorlásképpen meghagyjuk az Olvasó számára.

Tranzakciós adatbázisok reprezentációja

Egy tranzakció s adathalmazt többféleképpen is lehet reprezentálni. A választott reprezentációhatással lehet az I/O költségekre az elemhalmazjelöltek támogatottságának a kiszámításakor. A 6.23. ábrán a bevásárlókosár-tranzakciók kétféle reprezentációja látható. A bal oldali reprezentációt az adatok horizontális elrendezésének nevezzük. Számos asszociációs szabály okat kereső algoritmus alkalmazza ezt az elrendezést, például az Apriori is. Egy másik lehetőség a tranzakció azonosítók listájának (TID-lista) tárolása a megfelelő attribútum okkal együtt. Ezt a reprezentációt az adatok vertikális elrendezésének nevezzük. Egy elemhalmazjelölt támogatottsága ekkor úgy számítható ki, hogy vesszük az elemhalmazjelölt részhalmazaihoz tartozó TID-listák metszetét. A nagyobb méretű elemhalmazok felé haladva a TID-listák hossza csökken. Van azonban egy probléma ezzel a megközelítéssel: a kezdeti TID-listák halmaza túl nagy lehet ahhoz, hogy beférjen a memóriába (RAM), így kifinomultabb módszerekre lehet szükség a TID-listák tömörítéséhez. A következő szakaszban egy másik hatékony módszert mutatunk be az adatok reprezentációjára.