Проблема подсчета различных чисел
Проблема по информатике

В информатике проблема подсчета различных элементов [1] (также известная в прикладной математике как проблема оценки мощности ) — это проблема нахождения количества различных элементов в потоке данных с повторяющимися элементами. Это известная проблема с многочисленными приложениями. Элементы могут представлять IP-адреса пакетов, проходящих через маршрутизатор , уникальных посетителей веб-сайта, элементы в большой базе данных, мотивы в последовательности ДНК или элементы сетей RFID / сенсоров .

Формальное определение

Пример : Рассмотрим поток элементов с повторениями. Пусть обозначает количество отдельных элементов в потоке, а множество отдельных элементов представлено как . х 1 , х 2 , … , х с {\displaystyle x_{1},x_{2},\ldots ,x_{s}} н {\displaystyle n} { е 1 , е 2 , … , е н } {\displaystyle \{e_{1},e_{2},\ldots ,e_{n}\}}
Цель : Найти оценку использования только единиц хранения, где . н ^ {\displaystyle {\widehat {n}}} н {\displaystyle n} м {\displaystyle м} м ≪ н {\displaystyle м\лл н}

Примером экземпляра для задачи оценки мощности является поток: . Для этого экземпляра . а , б , а , с , г , б , г {\displaystyle а,б,а,в,г,б,г} н = | { а , б , с , г } | = 4 {\displaystyle n=|\left\{{a,b,c,d}\right\}|=4}

Наивное решение

Наивное решение проблемы следующее: 

Инициализируйте счетчик c нулевым значением . Инициализируйте эффективную структуру данных словаря D , например, хэш-таблицу или дерево поиска, в котором вставка и членство могут быть выполнены быстро. Для каждого элемента выдается запрос на членство. Если не является членом D ( ) Добавить к D Увеличить c на единицу, в противном случае ( ) ничего не делать. Вывод .    с ← 0   {\displaystyle c\leftarrow 0}      х  я     {\displaystyle x_{i}}      х  я     {\displaystyle x_{i}}       х  я   ∉ Д   {\displaystyle x_{i}\notin D}       х  я     {\displaystyle x_{i}}     с ← с + 1   {\displaystyle c\leftarrow c+1}      х  я   ∈ Д   {\displaystyle x_{i}\in D}     н = с   {\displaystyle n=c}

Пока число отдельных элементов не слишком велико, D помещается в основную память, и точный ответ может быть получен. Однако этот подход не масштабируется для ограниченного хранилища или если вычисления, выполняемые для каждого элемента, должны быть минимизированы. В таком случае было предложено несколько потоковых алгоритмов , которые используют фиксированное число единиц хранения. х я {\displaystyle x_{i}}

Алгоритм HyperLogLog

Алгоритмы потоковой передачи

Для обработки ограниченного ограничения хранилища потоковые алгоритмы используют рандомизацию для получения неточной оценки определенного числа элементов, . Современные оценщики хэшируют каждый элемент в эскиз данных низкой размерности с помощью хэш-функции, . Различные методы можно классифицировать в соответствии с эскизами данных, которые они хранят. н {\displaystyle n} е дж {\displaystyle e_{j}} час ( е дж ) {\displaystyle h(e_{j})}

Эскизы мин/макс

Минимальные/максимальные эскизы [2] [3] хранят только минимальные/максимальные хэшированные значения. Примеры известных оценок минимальных/максимальных эскизов: Chassaing et al. [4] представляет максимальный эскиз, который является минимально-дисперсионной несмещенной оценкой для проблемы. Непрерывная оценка максимальных эскизов [5] является оценкой максимального правдоподобия . Оценкой выбора на практике является алгоритм HyperLogLog . [6]

Интуиция, лежащая в основе таких оценщиков, заключается в том, что каждый эскиз несет информацию о желаемой величине. Например, когда каждый элемент связан с однородным RV , , ожидаемое минимальное значение равно . Хэш-функция гарантирует, что оно идентично для всех появлений . Таким образом, существование дубликатов не влияет на значение статистики экстремального порядка. е дж {\displaystyle e_{j}} час ( е дж ) ∼ У ( 0 , 1 ) {\displaystyle h(e_{j})\sim U (0,1)} час ( е 1 ) , час ( е 2 ) , … , час ( е н ) {\displaystyle h(e_{1}),h(e_{2}),\ldots ,h(e_{n})} 1 / ( н + 1 ) {\displaystyle 1/(n+1)} час ( е дж ) {\displaystyle h(e_{j})} е дж {\displaystyle e_{j}}

Существуют и другие методы оценки, отличные от min/max эскизов. Первая статья по оценке по количеству различий [7] описывает алгоритм Flajolet–Martin , эскиз битового шаблона. В этом случае элементы хэшируются в битовый вектор, а эскиз содержит логическое ИЛИ всех хэшированных значений. Первый асимптотически оптимальный по пространству и времени алгоритм для этой задачи был предложен Daniel M. Kane , Jelani Nelson и David P. Woodruff. [8]

Нижний-мэскизы

Эскизы Bottom -m [9] являются обобщением эскизов min, которые поддерживают минимальные значения, где . Теоретический обзор алгоритмов оценки с учетом различий см. в работе Cosma et al. [2] , а практический обзор со сравнительными результатами моделирования — в работе Metwally [10] . м {\displaystyle м} м ≥ 1 {\displaystyle m\geq 1}

Реализация алгоритма CVM Кнута на языке Python

определение  алгоритма_d ( поток ,  с ): m  =  len ( stream )  # Мы предполагаем, что это дано нам заранее. t  =  - 1  # Обратите внимание, что Кнут индексирует поток с 1. р  =  1 а  =  0 буфер  =  [] пока  t  <  ( m  -  1 ): т  +=  1 а  =  поток [ т ] u  =  равномерный ( 0 , 1 ) буфер  =  список ( фильтр ( лямбда  x  :  x [ 1 ]  !=  a ,  буфер ))  если  и  <  р : если  ( len ( буфер )  <  s ): буфер . добавить ([ u ,  a ]) еще : буфер  =  сортированный ( буфер ) p  =  макс ( буфер [ - 1 ][ 0 ], u ) буфер . поп () буфер . добавить ([ u ,  a ]) вернуть  len ( буфер )  /  p

Алгоритм CVM

По сравнению с другими алгоритмами приближения для проблемы подсчета различных элементов алгоритм CVM [11] (названный Дональдом Кнутом в честь инициалов Соурава Чакраборти, Н. В. Винодчандрана и Кулдипа С. Мила) использует выборку вместо хеширования. Алгоритм CVM обеспечивает несмещенную оценку количества различных элементов в потоке [12] в дополнение к стандартным гарантиям (ε-δ). Ниже представлен алгоритм CVM, включая небольшую модификацию Дональда Кнута. [12]

 Инициализация    п ← 1   {\displaystyle p\leftarrow 1}  Инициализация максимального размера буфера , где Инициализация пустого буфера, B Для каждого элемента в потоке данных размером выполните: Если есть в B , то Удалить из B случайное число в Если , то Если , то вставить в B    с   {\displaystyle с}     с ≥ 1   {\displaystyle s\geq 1}       а  т     {\displaystyle a_{t}}     А   {\displaystyle А}     н   {\displaystyle n}     (  а  т   , ты ) , ∀ ты   {\displaystyle (a_{t},u),\forall u}      (  а  т   , ты )   {\displaystyle (a_{t},u)}      ты ←   {\displaystyle u\leftarrow}     [ 0 , 1 )   {\displaystyle [0,1)}      ты < п   {\displaystyle и<п}       |  Б  |  < с   {\displaystyle |B|<s}     (  а  т   , ты )   {\displaystyle (a_{t},u)}  еще     (  а ′  ,  ты ′  )   {\displaystyle (а',u')} такой, что /* чье максимально в B */     ты ′  = макс {  ты ″  : (  а ″  ,  ты ″  ) ∈ Б , ∀  а ″  }   {\displaystyle u'=\max\{u'':(a'',u'')\in B,\forall a''\}}     (  а ′  ,  ты ′  )   {\displaystyle (а',u')}      ты ′    {\displaystyle u'}  Если тогда     ты >  ты ′    {\displaystyle u>u'}     п ← ты   {\displaystyle p\leftarrow u}  еще Заменить на End для возврата .    (  а ′  ,  ты ′  )   {\displaystyle (а',u')}     (  а  т   , ты )   {\displaystyle (a_{t},u)}      п ←  ты ′    {\displaystyle p\leftarrow u'}        |  Б  |   /  п   {\displaystyle |B|/p}

Предыдущая версия алгоритма CVM улучшена с помощью следующей модификации Дональда Кнута, которая добавляет цикл while для обеспечения сокращения B. [12]

 Инициализация    п ← 1   {\displaystyle p\leftarrow 1}  Инициализация максимального размера буфера , где Инициализация пустого буфера, B Для каждого элемента в потоке данных размером выполните: Если есть в B, то Удалить из B случайное число в If , то Вставить в B, пока затем Удалить каждый элемент из B с помощью End While If, ​​то    с   {\displaystyle с}     с ≥ 1   {\displaystyle s\geq 1}       а  т     {\displaystyle a_{t}}     А   {\displaystyle А}     н   {\displaystyle n}      а  т     {\displaystyle a_{t}}       а  т     {\displaystyle a_{t}}      ты ←   {\displaystyle u\leftarrow}     [ 0 , 1 )   {\displaystyle [0,1)}      ты ≤ п   {\displaystyle u\leq p}     (  а  т   , ты )   {\displaystyle (a_{t},u)}       |  Б  |  = с ∧ ты < п   {\displaystyle |B|=s\wedge u<p}     (  а ′  ,  ты ′  )   {\displaystyle (а',u')}      ты ′  >   п 2     {\displaystyle u'>{\frac {p}{2}}}      п ←   п 2     {\displaystyle p\leftarrow {\frac {p}{2}}}      ты < п   {\displaystyle и<п}  Вставьте в конец B для возврата .    (  а  т   , ты )   {\displaystyle (a_{t},u)}        |  Б  |   /  п   {\displaystyle |B|/p}

Проблема взвешенного количества-различения

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

Экземпляр : Поток взвешенных элементов с повторениями и целое число . Пусть будет числом различных элементов, а именно , и пусть эти элементы будут . Наконец, пусть будет весом . х 1 , х 2 , … , х с {\displaystyle x_{1},x_{2},\ldots ,x_{s}} м {\displaystyle м} н {\displaystyle n} н = | { х 1 , х 2 , … , х с } | {\displaystyle n=|\left\{{x_{1},x_{2},\ldots ,x_{s}}\right\}|} { е 1 , е 2 , … , е н } {\displaystyle \left\{{e_{1},e_{2},\ldots ,e_{n}}\right\}} w j {\displaystyle w_{j}} e j {\displaystyle e_{j}}
Цель : Найти оценку использования только единиц хранения, где . w ^ {\displaystyle {\widehat {w}}} w = ∑ j = 1 n w j {\displaystyle w=\sum _{j=1}^{n}w_{j}} m {\displaystyle m} m ≪ n {\displaystyle m\ll n}

Примером экземпляра для задачи с весом является: . Для этого экземпляра , веса равны и . a ( 3 ) , b ( 4 ) , a ( 3 ) , c ( 2 ) , d ( 3 ) , b ( 4 ) , d ( 3 ) {\displaystyle a(3),b(4),a(3),c(2),d(3),b(4),d(3)} e 1 = a , e 2 = b , e 3 = c , e 4 = d {\displaystyle e_{1}=a,e_{2}=b,e_{3}=c,e_{4}=d} w 1 = 3 , w 2 = 4 , w 3 = 2 , w 4 = 3 {\displaystyle w_{1}=3,w_{2}=4,w_{3}=2,w_{4}=3} ∑ w j = 12 {\displaystyle \sum {w_{j}}=12}

В качестве примера приложения могут быть IP- пакеты, полученные сервером. Каждый пакет принадлежит одному из IP-потоков . Вес может быть нагрузкой, налагаемой потоком на сервер. Таким образом, представляет собой общую нагрузку, налагаемую на сервер всеми потоками, к которым принадлежат пакеты. x 1 , x 2 , … , x s {\displaystyle x_{1},x_{2},\ldots ,x_{s}} n {\displaystyle n} e 1 , e 2 , … , e n {\displaystyle e_{1},e_{2},\ldots ,e_{n}} w j {\displaystyle w_{j}} e j {\displaystyle e_{j}} ∑ j = 1 n w j {\displaystyle \sum _{j=1}^{n}{w_{j}}} x 1 , x 2 , … , x s {\displaystyle x_{1},x_{2},\ldots ,x_{s}}

Решение проблемы взвешенного количества-различения

Любая оценка экстремальной статистики порядка (минимум/максимум эскизов) для невзвешенной задачи может быть обобщена до оценки для взвешенной задачи. [13] Например, взвешенная оценка, предложенная Коэном и др. [5], может быть получена при расширении непрерывной оценки максимальных эскизов для решения взвешенной задачи. В частности, алгоритм HyperLogLog [6] может быть расширен для решения взвешенной задачи. Расширенный алгоритм HyperLogLog обеспечивает наилучшую производительность с точки зрения статистической точности и использования памяти среди всех других известных алгоритмов для взвешенной задачи.

Смотрите также

Ссылки

  1. ^ Уллман, Джефф ; Раджараман, Ананд; Лесковец, Юре . «Потоки данных майнинга» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  2. ^ ab Cosma, Ioana A.; Clifford, Peter (2011). "Статистический анализ вероятностных алгоритмов подсчета". Scandinavian Journal of Statistics . arXiv : 0801.3552 .
  3. ^ Жируар, Фредерик; Фьюзи, Эрик (2007). Труды Четвертого семинара по аналитической алгоритмике и комбинаторике (ANALCO) 2007 г. С.  223–231 . CiteSeerX 10.1.1.214.270 . doi :10.1137/1.9781611972979.9. ISBN  978-1-61197-297-9.
  4. ^ Chassaing, Philippe; Gerin, Lucas (2006). "Эффективная оценка мощности больших наборов данных". Труды 4-го коллоквиума по математике и информатике . arXiv : math/0701347 . Bibcode :2007math......1347C.
  5. ^ ab Cohen, Edith (1997). «Структура оценки размера с приложениями к транзитивному замыканию и достижимости». J. Comput. Syst. Sci . 55 (3): 441– 453. doi : 10.1006/jcss.1997.1534 .
  6. ^ ab Flajolet, Philippe ; Fusy, Eric; Gandouet, Olivier; Meunier, Frederic (2007). "HyperLoglog: анализ алгоритма оценки мощности, близкого к оптимальному" (PDF) . Анализ алгоритмов .
  7. ^ Флажоле, Филипп ; Мартин, Г. Найджел (1985). «Вероятностные алгоритмы подсчета для приложений баз данных» (PDF) . J. Comput. Syst. Sci . 31 (2): 182– 209. doi :10.1016/0022-0000(85)90041-8.
  8. ^ Кейн, Дэниел М .; Нельсон, Джелани ; Вудрафф, Дэвид П. (2010). «Оптимальный алгоритм для проблемы отдельных элементов». Труды 29-го ежегодного симпозиума ACM по принципам систем баз данных (PODS) .
  9. ^ Коэн, Эдит ; Каплан, Хаим (2008). «Более точная оценка с использованием нижних k-скетчей» (PDF) . PVLDB .
  10. ^ Метвалли, Ахмед; Агравал, Дивьякант; Аббади, Амр Эль (2008), Зачем использовать логарифмическую систему, если можно использовать линейную?: На пути к эффективному отчетливому подсчету поискового трафика , Труды 11-й международной конференции по расширению технологий баз данных: достижения в технологии баз данных, стр.  618–629 , CiteSeerX 10.1.1.377.4771 
  11. ^ Чакраборти, Сурав; Винодчандран, Невада; Мил, Калдип С. (2022). «Отдельные элементы в потоках: алгоритм для (текстовой) книги». Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 6 страниц, 727571 байт. arXiv : 2301.10191 . doi : 10.4230/LIPIcs.ESA.2022.34 . ISSN  1868-8969. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  12. ^ abc Кнут, Дональд (май 2023 г.). «Алгоритм CVM для оценки отдельных элементов в потоках» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  13. ^ Коэн, Реувен ; Кацир, Лиран; Йехезкель, Авив (2014). «Унифицированная схема обобщения оценок мощности для суммирования». Information Processing Letters . 115 (2): 336– 342. doi :10.1016/j.ipl.2014.10.009.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Count-distinct_problem&oldid=1270619970"