AMS Sketch: Оцінка нахилу потоку в уривку пам’яті

Що насправді вимірює другий момент частоти

Для потоку даних, нехай m_i позначає кількість разів, якби елемент i з'явився до кінця потоку. Нульовий момент частоти, F0, рахує кількість унікальних елементів. Перший момент частоти, F1, просто довжина потоку, оскільки він сумує всі частоти до першої степені. Другий момент частоти, F2, обчислюється як сума квадратів частот кожного елемента: це сума по всіх унікальних елементах m_i в квадраті. Піднесення частот до квадрату перед підрахунком має вражаючий ефект: воно винагороджує концентрацію та карає розповсюдження. Розглянемо два потоки однакової загальної довжини. В одному мільйон елементів з'являються рівно один раз, тому F2 дорівнює мільйону. А в іншому один елемент з'являється мільйон разів, а все інше мовчазне, отже F2 дорівнює мільйони квадратні, трильйонам. Обидва потоки мають однакову довжину, але F2 відрізняються у шість порядків величини, тому що F2 чутливий до того, наскільки нерівномірно розподілена маса потоку між елементами. Це саме тому F2 називають мірою нахилу або концентрації: ділення F2 на F1 в квадраті або порівняння F2 з тим, що виробляє ідеально рівномірний розподіл, дає нормалізоване відчуття того, наскільки викривленими є частоти елементів. Статистики розпізнають F2 як тісно пов’язаний із Індексом Герінга-Біршамана, який використовується в економіці для вимірювання концентрації ринку, і з поняттям ймовірності зіткнення в теорії інформації, оскільки F2 поділена на квадрат довжини потоку дорівнює ймовірності того, що два випадково вибрані елементи з потоку є одним і тим самим елементом. Оскільки F2 сильно винагороджує кілька великих частот, він діє як раннє попередження: коли мережа зазвичай розповсюджує пакети через тисячі потоків, а F2 раптово стрибає, це сильний кількісний натяк на те, що невелика кількість потоків, можливо, атака відмови в обслуговуванні або несправне застосування, почала домінувати в трафіку, навіть перш ніж хтось вручну перевірить журнали на рівні потоків.

Чому це важливо

Цей ефект пояснює X. Він особливо важливий у випадках, коли потрібно оцінити нахил потоку даних без необхідності обчислювати точну кількість окремих елементів. Це актуально для мережевих технологій, баз даних та систем виявлення шахрайства, де аналіз розподілу даних має вирішальне значення для оптимізації продуктивності та забезпечення безпеки. Наприклад, CDN використовує F2 для визначення, чи концентруються запити на певні файли, що впливає на стратегію кешування. Оптимізатори запитів баз даних використовують F2 для оцінки селективності з'єднань, а системи виявлення шахрайства відстежують F2 у часі, щоб виявити незвичайні спади активності.

Прийом випадкового знаку: як один лічильник оцінює F2

Серце AMS Sketch є хибним у своїй простоті. Перш ніж потік почнеться, зафіксуйте випадкову функцію, яка відображає кожен можливий елемент або на плюс одну, або на мінус одну, причому кожний результат однаково ймовірний, і ключово, що будь-які чотири з цих знаків є взаємонезалежними, властивість, яку називають взаємозалежністю чотирьох частин. Така функція може бути згенерована та компактно збережена за допомогою невеликого поліноміального хешу замість таблиці пошуку для кожного можливого елемента, що дозволяє зберегти схему пам'яттю-ефективною. Підтримуйте один запущений лічильник, назвемо його Z, ініціалізований до нуля. Коли приходить будь-який елемент у потік, шукайте його знак за допомогою хеш-функції та додайте цей знак до Z. Після того, як весь потік пройде, обчислюйте Z квадрат як оцінку. Чому це працює? Розгорніть Z як суму всіх різних елементів, помножену на частоту кожного елемента та його випадковий знак, а потім піднесіть цю суму до квадрата. Піднесення суми знаків до квадрата створює два типи членів: квадратні члени, де елемент множиться проти себе, і перехресні члени, де два різних елементи множаться разом. Кожен квадратний член вносить точно частоту кожного елемента до квадратного, оскільки знак плюс один або мінус один підноситься до квадрата точно один раз, незалежно від того, який знак було вилучено. Кожен перехресний член вносить добуток частот двох різних елементів, помножений на добуток їхніх двох незалежних випадкових знаків, і оскільки ці два знаки незалежні та кожна з них однаково ймовірно є плюс один або мінус один, очікуване значення їхнього добутку становить точно нуль. Взявши очікуване значення Z квадрат над випадковістю знаків, перехресні члени зникають і залишаються лише квадратні члени, що дає точно суму частот кожного елемента в квадраті, що відповідає F2 за визначенням. Саме тому алгоритм називається упередженим: в середньому, через випадковість хеш-функції, один число Z квадратне дорівнює F2 точно, навіть якщо будь-який окремий пробіг буде вище або нижче справжньої величини через випадкове коливання.

Контроль Варіативності: Повторення та Медіана З Міжквартильного Розсіювання

Неупереджений оцінювач, який є правильним лише в середньому, ще не корисний, оскільки окреме виконання Z квадрат може бути дуже відрізнятися від F2 через варіативність, і цілком можливо, щоб перехресні члени повністю не скасовувалися при будь-якому випадковому витягування. AMS Sketch контролює це в два етапи, які зазвичай описуються як усереднення та подальше обчислення медіани, також відомої як медіана з міжквартильного розсіювання. На першому етапі запускається багато незалежних копій базового оцінювача паралельно, кожна з власною незалежно витягнутою функцією хешування чотирикутних значень та власним лічильником, і їхні квадратичні значення усереднюються разом. Усереднення набору незалежних, однаково розподілених неупереджених оцінювачів не змінює очікуване значення, оскільки математичне сподівання середнього дорівнює середньому арифметичному математичних сподівань, але воно зменшує дисперсію у пропорції до кількості копій, які усереднюються, оскільки дисперсія середнього незалежних величин ділиться на кількість. Вибір кількості паралельних копій пропорційно одному поділу на квадрат бажаної відносної похибки епсилон в квадраті, використовуючи нерівність Чебишева, гарантує, що усереднена оцінка потрапляє в межах невеликої відносної похибки F2 з розумною ймовірністю, зазвичай розглядається як щонайменше сімдесяти п’ять відсотків довіри. Другий етап підвищує цю впевненість майже до абсолютної без будь-яких значних витрат пам'яті: створюються кілька незалежних груп, кожна з яких усереднюється вищезазначеним способом, і повідомляється медіана між цими групами. Оскільки середнє значення кожної групи правильне принаймні на три чверті, ймовірність того, що більшість груп одночасно неправильні, швидко зменшується зі зростанням кількості груп, за допомогою межі Черозфа, тому подвоєння або потрійне збільшення кількості груп знижує ймовірність невдачі до незначного значення, при цьому загальний обсяг пам'яті множиться на цей самий невеликий фактор.

Чому це важливо

Визначним є підкресленням методу AMS Sketch полягає в тому, що його розмір пам’яті не залежить від n, кількості унікальних елементів, які можуть з’явитися в потоці, що може бути астрономічно великим, а залежить лише від бажаної точності та рівня впевненості. Кожен окремий лічильник Z є одним цілим числом, і оскільки це сума плюс-мінус-один, яка збільшується протягом потоку довжиною m, його значення ніколи не перевищує m, тому для його представлення потрібно лише O(log m) біт, тобто кількість бітів логарифмічна відносно довжини потоку, а не лінійна від кількості унікальних елементів. Функція чотиривимірного незалежного хешування, необхідна для генерації знаків, не потребує зберігання явного таблиці з одним записом на кожен можливий елемент; замість цього її можна побудувати за допомогою многочлена низького степеня над кінцевим полем, визначеним невеликою кількістю випадково обраних коефіцієнтів, тому вся хеш-функція описується O(1) словами пам’яті на копію, незалежно від кількості унікальних елементів, які існують. Множення на кількість паралельних лічильників, необхідних для досягнення бажаної відносної похибки епсилон, та на кількість груп, необхідних для досягнення бажаного рівня впевненості дельта, дає розмір пам’яті O(1 / epsilon квадрат * log(1 / delta) * log m) біт, який визначається лише ціллю щодо точності, ціллю щодо впевненості та логарифмом довжини потоку, без будь-якої залежності від кількості унікальних елементів n. Це робить використання простору справді надплинним, фактично постійним відносно n: чи містить потік тисячу окремих потоків або мільярди, пам’ять займає точно таку ж кількість біт, на відміну від точного таблиці частот, розмір якої зростає лінійно з кількістю унікальних елементів, які дійсно спостерігаються. Цей компроміс між простором і точністю, суворо формалізований в оригінальному документі AMS 1996 року, запустив ширшу галузь алгоритмів потоку та схецьінгу, і та сама ідея випадкових знаків з’являється в більш складних схеках, таких як Count-Sketch та будівельні блоки AMS для виявлення домінуючих елементів.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте AMS Sketch: Estimating Stream Skew in a Sliver of Memory і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.