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

Допустим, что MinSupi = и * |Ci|. Поддержка данного предмета в Ci характеризует число транзакций в этом кластере, которые содержат этот предмет. Поэтому предмет является большим в кластере Ci, если и только если его поддержка в этом кластере больше или равна MinSupi. Для каждого кластера Ci необходимо сохранять две структуры данных в памяти: хэш-таблицу Hashi и бинарное дерево Btreei. Эти структуры являются стандартными методами индексации для больших БД.

Hashi: Хэш-таблица для Ci с предметами в виде их индексных ключей. Для каждого предмета e в Ci имеется вход в форме < e, tree_addr > в Hashi, где tree_addr есть адрес соответствующего листового входа для e в Btreei (см. ниже). Hashi обеспечивает доступ к пути, чтобы вставлять, удалять или обновлять поддержку данного предмета.

Btreei: Это бинарное дерево B-tree с поддержкой предметов в Ci в виде индексных ключей. Для каждого предмета e в Ci имеется листовой вход в форме < sup, Hash_addr > в Btreei, где sup есть поддержка e в Ci, а hash_addr есть адрес соответствующего входа для e в Hashi. Btreei обеспечивает доступ к пути для нахождения всех предметов, имеющих данную поддержку.

Минимальная поддержка MinSupi разделяет листовые входы Btreei на входы для больших предметов Largei (в правом поддереве) и входы для малых предметов Smalli (в левом поддереве). Особый интерес вызывают предметы, находящиеся вблизи границы раздела: малые предметы, имеющие поддержку (MinSupi - 1), и большие предметы, имеющие поддержку MinSupi. Когда транзакция помещается в кластер или перемещается в другой кластер, поддержка некоторых предметов будет увеличиваться или уменьшаться на 1. Следовательно, эти предметы могут пересекать границу. Эффективное сохранение следа таких изменений является главной задачей сопровождения. Во-первых, мы определяем две операции.

Мы определяем Inc(Ci, e) как операцию, которая увеличивает поддержку данного предмета e в Ci на 1.

Некоторые шаги включают в себя следующее содержание:

    1. Отыскать Hashi для входа < e, tree_addr >. допустим, что < sup, hash_addr > является листовым входом в btreei, на который указывает tree_addr. 2. Увеличить поддержку sup на 1 в < sup, hash_addr >. 3. Переместить < sup, hash_addr > направо, чтобы пройти все листовые входы

< sup', hash_addr' > при условии sup' < sup.

    4. Для каждого входа < sup', hash_addr' >, перемещенного в (с), обновить адреса в дереве, содержащем соответствующие входы в hashi. 5. Обновить предыдущие входные индексы в < sup, hash_addr > чтобы отразить изменение поддержки, если необходимо.

Когда транзакция t присоединяется к кластеру Ci, MinSupi, поддержка каждого предмета, содержащегося в транзакции, увеличивается на 1. Допустим, что OldMinSupi и MinSupi обозначают минимальную поддержку для Ci перед и после присоединения транзакции к кластеру.

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




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

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