Разница между выходным алгоритмом AMS Sketch и Count Sketch

Question

Я пытаюсь понять различия между эскизом AMS и алгоритмами Count Sketch.Насколько я понимаю, обе их цели / результаты должны возвращать эскиз , то есть частотный вектор.Это содержит частоты элементов в проходящем паре.В чем разница между ними?

Интуитивно понятно, что алгоритм AMS показывает только, прошел ли элемент или нет, и фактически не считает сколько раз.Хотя я не уверен, что это правильно.

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

Надеюсь, что это имеет смысл.Спасибо

Answer 1

Обе являются попытками решить проблемы, связанные с сохранением количества элементов, которое вы фактически не можете поместить в свой словарь.Вы не можете сделать это, но вы можете решить связанные проблемы с некоторой частотой ошибок.

Эскиз AMS пытается решить проблему правильной оценки различных статистических статистических данных.Например, сумма квадратов частот.

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

Эскиз отсчета минут похож на эскиз подсчета, за исключением того, что он дает верхнюю границу того, сколько раз вы его видели.(«Мин» относится к мин, которую вы берете внутри алгоритма.)