Какой конкретный тип «Хэш-дерева» относится к этой статье?

Question

Я реализую алгоритм из бумаги, и часть его требует использования «дерева хэширования». Поскольку я никогда не слышал об этой структуре данных I looked it up. Оказывается, дерево хэша имени неоднозначно и может использоваться для обозначения трех разных типов структур данных. К ним относятся:

• Hashed Array Tree
• Hash tree (persistent data structure), an implementation strategy for sets and maps
• Merkle Tree

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

Данная статья относится к Fast Algorithms for Mining Association Rules, а конкретный раздел, на который я имею в виду, приведен на стр. 4 в разделе 2.1.2.

Я процитировал раздел соответствующего текста ниже.

Кандидаты Ck хранятся в хэштри. Узел хэш-дерева либо содержит список наборов элементов (листовой узел), либо хеш-таблицу a (внутренний узел). Во внутреннем узле каждое ведро хэш-таблицы указывает на другой узел. Корень дерева хэшей определяется на глубине 1. Внутренний узел на глубине d указывает на узлы на глубине d + 1. Элементы хранятся в листьях. Когда мы добавляем набор предметов c, мы начинаем с корня и спускаемся по дереву, пока не достигнем листа. На внутреннем узле на глубине d мы решаем, какую ветвь следовать, применяя хэш-функцию к d-му элементу набора предметов. Все узлы изначально создаются как листовые узлы. Когда количество элементов в листовом узле превышает заданный порог, листовой узел преобразуется во внутренний узел.

Следует также отметить, что эта конкретная структура данных упоминаются в других работах интеллектуального анализа данных, которые основаны от алгоритма априорного, например, в this документе по правилам циклических объединений. Поскольку это часто используемая структура данных, я бы хотел больше узнать об этом, чем просто два абзаца в нескольких статьях.

Answer 1

Дерево хэша и дерево Merkle - это то же самое. Поэтому, если в документе упоминается хэш-дерево, это дерево Merkle и наоборот. Чтобы прояснить концепцию алгоритма Apriori, используемый хэш или дерево Merkle, см. Страницы 344 & 345: https://www-users.cs.umn.edu/~kumar/dmbook/ch6.pdf.