• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Мероприятия

Семинар лаборатории теоретической информатики: "L0-сэмплирование и эскизы графов". Докладчик: В. Гринберг

Мероприятие завершено
На очередном семинаре лаборатории теоретической информатики в среду 14 февраля состоится доклад 
Вадима Гринберга
"L0-сэмплирование и эскизы графов".
Время проведения:18:10 - 19:30
Адрес мероприятия: Кочновский проезд, д. 3, ауд. 503
Заказ пропуска: evavilova@hse.ru

Аннотация
В задачах стриминга широкое применение находят так называемые "эскизы" (sketches) —- преобразование входных данных, понижающее их размерность, так, что по эскизу мы сможем восстановить некоторую информацию о потоке.
 
Эскизы являются адаптивной структурой — могут изменяться по мере поступления новых данных, и делать это быстро. Я собираюсь рассказать об L0-сэмплерах — линейных эскизах (то есть, являющихся линейными отображениями), позволяющих за малую память по образу вектора получить какую-то его ненулевую координату (если таковые есть). Кроме того, будет рассказано об эффективном по памяти  потоковом алгоритме (также эскизе), основанном на L0-сэмплерах, который по графу, заданному в виде потока рёбер (запросы "добавить ребро", "удалить ребро"), восстанавливает список его компонент связности и остовный лес.