Обновление числа "больших" предметов - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

Алгоритм для обновления дан на рис.6. Для каждого предмета е в t отыскивается Hashi. Если е найдено хэше кластера, то увеличиваем на 1 его sup в Btreei. Если е не найдено, то вставляем е с sup = 1 в Hashi и Btreei. Это показано в строках (4) - (9).

    1. |Ci| ++; /* размер кластера увеличивается на 1*/ 2. OldMinSupi = MinSupi; 3. MinSupi = и * |Ci|;

/* обновление поддержки предметов в t */

    4. foreach item e in t do /* для каждого предмета е в транзакции t выполнить */; 5. look up Hashi for e /* отыскать Hashi для предмета е */; 6. if e is found then /* если е найден, то */; 7. Inc(Ci, e) /* */ 8. else 9. insert e into Hashi and Btreei with sup = 1

/* малые предметы становятся большими */

    10. if MinSupi = = OldMinSupi then 11. search Btreei for the items e with sup = MinSupi; 12. foreach returned item e do /*для каждого возвращенного предмета е выполнить*/ 13. if e is in t then |Largei| ++; /* если е находится в t, то увеличить число больших предметов в кластере Ci на 1*/;

/* большие предметы становятся малыми */

    14. if MinSupi = = OldMinSupi + 1 then 15. search Btreei for the items e with sup = OldMinSupi; 16. foreach item e returned do /* для каждого возвращенного предмета е выполнить */ 17. if e is not in t then |Largei| - -; /*если е нет в t, то уменьшить число больших предметов в кластере на 1 */;

Малые предметы становятся большими: малый предмет е становится большим, если (а) MinSupi = OldMinSupi, (b) е находится в t, и (с) sup = MinSupi. Этот случай отслеживается в строках (10) - (13).

Большие предметы становятся малыми: большой предмет становится малым, если (а) MinSupi = OldMinSupi + 1, (b) е не находится в t, и (с) sup = OldMinSupi. Этот случай отслеживается в строках (14) - (17).

Для обновления числа элементов в множествах |ki=1Smalli| и |ki=1Largei|

Используются две хэш-таблицы LargeHash и SmallHash, чтобы сохранять число кластеров с большими и малыми предметами. Когда малый предмет е становится большим в кластере, его число в SmallHash уменьшается на 1, а его число в LargeHash увеличивается на 1, т. е. эти числа изменяются согласованно. Как только это число достигает 0 в хэш-таблице, соответствующая ячейка удаляется из этой таблицы. Как только новый предмет е добавляется в кластер, новая ячейка с начальным значением 1 вставляется в LargeHash или SmallHash, в зависимости от того, является ли е большим или малым предметом в этом кластере. Когда транзакция t присоединяется к кластеру, изменение числа |ki=1Smalli| (или |ki=1Largei| соответственно) заключается в числе новых вставляемых ячеек минус число ячеек, удаляемых в SmallHash (или LargeHash, соответственно).

В действительной реализации обновление структур данных выполняется только после того, как протестированы все возможные варианты адресации кластеров.

Подобные рассуждения применимы к случаю удаления транзакции из кластера.

Похожие статьи




Обновление числа "больших" предметов - Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата

Предыдущая | Следующая