П.В. Голубцов - От последовательной к распределенной параллельной обработке данных

Это видео заблокировано на Rutube. From sequential to distributed parallel data processing: Information algebras in big data problems Peter Golubtsov Lomonosov Moscow State University; National Research University Higher School of Economics In big data problems, it is often impossible to collect all the relevant data on one place before processing. As a result, there emerges a need to transform existing algorithms to a “parallel” form. The corresponding data analysis algorithm must, working on many computers in parallel, extract from each set of source data some intermediate compact “information”, gradually combine and update it and, finally, use the accumulated information to produce the result. Upon the arrival of new pieces of data, it should be able to add the information extracted from them to the accumulated information in real time and, eventually, update the result. Usually it is not obvious, how to design such completely parallel and ultimately scalable version of an existing algorithm. In this study, we will approach this problem gradually, by starting with a sequential algorithm and then transforming it to a completely parallel one. Procedures of sequential updating of information are important for “big data streams” processing because they avoid accumulating and storing large data sets. As a model of information accumulation, we study the Bayesian updating procedure for linear experiments. Analysis and gradual transformation of the original processing scheme in order to increase its efficiency lead to certain mathematical structures - information spaces. We show that processing can be simplified by introducing a special intermediate form of information representation. Thanks to the rich algebraic properties of the corresponding information space, it allows unifying and increasing the efficiency of the information updating. It also leads to various parallelization options for inherently sequential Bayesian procedure, which are suited for distributed data processing platforms, such as MapReduce. Besides, we will see how certain formalization of the concept of information and its algebraic properties can arise simply from adopting data processing to big data demands. Developed approaches and concepts allow to increase efficiency and uniformity of data processing and present a systematic approach to transforming sequential processing into parallel. От последовательной к распределенной параллельной обработке данных: информационные алгебры в задачах больших данных П.В. Голубцов Московский государственный университет им. М.В. Ломоносова; Национальный исследовательский университет Высшая школа экономики В задачах больших данных часто невозможно собрать все необходимые данные в одном месте перед обработкой. В результате возникает необходимость преобразования существующих алгоритмов в «параллельную» форму. Соответствующий алгоритм анализа данных должен, работая на множестве компьютеров параллельно, извлекать из каждого набора исходных данных некоторую промежуточную компактную «информацию», постепенно комбинировать и обновлять ее и, наконец, использовать накопленную информацию для получения результата. По прибытии новых частей данных он должен иметь возможность добавлять информацию, извлеченную из них, к накопленной информации в реальном времени и, в конечном итоге, обновлять результат. Обычно не очевидно, как разработать такую полностью параллельную и в конечном итоге масштабируемую версию существующего алгоритма. В этом исследовании мы подойдем к этой проблеме постепенно, начав с последовательного алгоритма, а затем преобразовав его в полностью параллельный. Процедуры последовательного обновления информации важны для обработки «больших потоков данных», поскольку они позволяют избежать накопления и хранения больших наборов данных. В качестве модели накопления информации мы рассмотрим процедуру байесовского обновления для линейных экспериментов. Анализ и постепенное преобразование исходной схемы обработки с целью повышения ее эффективности приводят к определенным математическим структурам - информационным пространствам. Мы покажем, что обработку можно упростить, введя специальную промежуточную форму представления информации. Благодаря богатым алгебраическим свойствам соответствующего информационного пространства, это позволяет унифицировать и повысить эффективность обновления информации. Это также приводит к различным вариантам распараллеливания для изначально последовательной байесовской процедуры, которые подходят для платформ распределенной обработки данных, таких как MapReduce. Кроме того, мы увидим, как определенная формализация концепции информации и ее алгебраических свойств может возникнуть просто в результате адаптации обработки данных к требованиям больших данных. Разработанные подходы и концепции позволяют повысить эффективность и единообразие обработки данных и представляют системный подход к