maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2016-2-195-210mais-329Research ArticleОригинальные статьиArticlesКоллективные потоковые вычисления: реляционные модели и алгоритмыDataflow-Driven Crowdsourcing: Relational Models and AlgorithmsУсталовД. А.UstalovD. A.

аспирант

graduate student

dau@imm.uran.ruИнститут математики и механики им. Н.Н. Красовского Уральского отделения Российской академии наук, ул. Софьи Ковалевской, 16, г. Екатеринбург, 620990 РоссияРоссияN.N. Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Sofia Kovalevskaya str., 16, Yekaterinburg, 620990, RussiaRussian Federation201620042016232195210Copyright © Усталов Д.А., 20162016Усталов Д.А.Ustalov D.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/329

В последнее время краудсорсинг на основе выполения микрозадач получил широкое применение в области анализа неструктурированных данных. Разрабатываются специализированные методики, состоящие из множества этапов обработки исходных данных, требующих согласованности их представления для обеспечения воспроизводимости работы. Данная статья посвящена решению проблемы воспроизводимости и формализации процесса краудсорсинга микрозадачами. Предложена модель коллективных потоковых вычислений на основе расширенной реляционной модели и потоковой модели вычислений. Модель предназначена для обработки исходных данных в виде реляционных отношений путем параллельного выполнения этапов разметки микрозадачами и этапов автоматической синхронизации. Этапы обработки данных и связи между ними записываются с использованием схемы коллективных вычислений, представляющей собой слабо связный ориентированный ациклический граф. Описан синхронный алгоритм выполнения схем коллективных вычислений. Продемонстрированы приложения модели в области компьютерной лингвистики для уточнения лексикализации понятий в электронных тезаурусах и построения родо-видовых отношений между понятиями при помощи краудсорсинга. Процедура «добавить–удалить–подтвердить» позволяет внести в лексикализацию понятий недостающие лексемы и исключить посторонние. Процедура «род–вид–сопоставить» позволяет сформировать гипо-гиперонимические отношения между понятиями на основе соответствующих родо-видовых пар слов. Результаты экспериментов на материалах открытого электронного тезауруса русского языка подтверждают применимость разработанных процедур для развития лексических ресурсов. В экспериментах приняли участие как волонтеры из популярных социальных сетей, так и пользователи бирж краудсорсинга (за вознаграждение в форме микроплатежей). 

Recently, microtask crowdsourcing has become a popular approach for addressing various data mining problems. Crowdsourcing workflows for approaching such problems are composed of several data processing stages which require consistent representation for making the work reproducible. This paper is devoted to the problem of reproducibility and formalization of the microtask crowdsourcing process. A computational model for microtask crowdsourcing based on an extended relational model and a dataflow computational model has been proposed. The proposed collaborative dataflow computational model is designed for processing the input data sources by executing annotation stages and automatic synchronization stages simultaneously. Data processing stages and connections between them are expressed by using collaborative computation workflows represented as loosely connected directed acyclic graphs. A synchronous algorithm for executing such workflows has been described. The computational model has been evaluated by applying it to two tasks from the computational linguistics field: concept lexicalization refining in electronic thesauri and establishing hierarchical relations between such concepts. The “Add–Remove–Confirm” procedure is designed for adding the missing lexemes to the concepts while removing the odd ones. The “Genus–Species–Match” procedure is designed for establishing “is-a” relations between the concepts provided with the corresponding word pairs. The experiments involving both volunteers from popular online social networks and paid workers from crowdsourcing marketplaces confirm applicability of these procedures for enhancing lexical resources. 

краудсорсингпотоковые вычисленияреляционная моделькомпьютерная лингвистикаcrowdsourcingdataflow modelrelational modelcomputational linguisticsReferencesEstell ́es-Arolas E., Gonz ́alez-Ladr ́on-de Guevara F., “Towards an integrated crowdsourcing definition”, Journal of Information Science, 38:2 (2012), 189–200, http://jis.sagepub.com/content/38/2/189.Estell ́es-Arolas E., Gonz ́alez-Ladr ́on-de Guevara F., “Towards an integrated crowdsourcing definition”, Journal of Information Science, 38:2 (2012), 189–200, http://jis.sagepub.com/content/38/2/189.The People’s Web Meets NLP, eds. Gurevych I., Kim J., Springer Berlin Heidelberg, 2013, http://dx.doi.org/10.1007/978-3-642-35085-6.The People’s Web Meets NLP, eds. Gurevych I., Kim J., Springer Berlin Heidelberg, 2013, http://dx.doi.org/10.1007/978-3-642-35085-6.Bocharov V., Alexeeva S., Granovsky D. et al., “Crowdsourcing morphological annotation”, Computational Linguistics and Intellectual Technologies: papers from the Annual conference “Dialogue”, 2013, 109–124, http://www.dialog21.ru/digests/dialog2013/materials/pdf/BocharovVV.pdf.Bocharov V., Alexeeva S., Granovsky D. et al., “Crowdsourcing morphological annotation”, Computational Linguistics and Intellectual Technologies: papers from the Annual conference “Dialogue”, 2013, 109–124, http://www.dialog21.ru/digests/dialog2013/materials/pdf/BocharovVV.pdf.Pronoza E., Yagunova E., “Comparison of Sentence Similarity Measures for Russian Paraphrase Identification”, Proceedings of the AINL-ISMW FRUCT, 2015, 74–82, http://dx.doi.org/10.1109/AINL-ISMW-FRUCT.2015.7382973.Pronoza E., Yagunova E., “Comparison of Sentence Similarity Measures for Russian Paraphrase Identification”, Proceedings of the AINL-ISMW FRUCT, 2015, 74–82, http://dx.doi.org/10.1109/AINL-ISMW-FRUCT.2015.7382973.Braslavski P., Ustalov D., Mukhin M., “A Spinning Wheel for YARN: User Interface for a Crowdsourced Thesaurus”, Proceedings of the Demonstrations at the 14th Conference of the European Chapter of the Association for Computational Linguistics, 2014, 101–104, http://www.aclweb.org/anthology/E/E14/E14-2026.pdf.Braslavski P., Ustalov D., Mukhin M., “A Spinning Wheel for YARN: User Interface for a Crowdsourced Thesaurus”, Proceedings of the Demonstrations at the 14th Conference of the European Chapter of the Association for Computational Linguistics, 2014, 101–104, http://www.aclweb.org/anthology/E/E14/E14-2026.pdf.Шуровьески Дж., Мудрость толпы, Манн, Иванов и Фербер, 2013, http://www.mannivanov-ferber.ru/books/paperbook/the-wisdom-of-crowds/; [Surowiecki J., The Wisdom of Crowds, Doubleday, 2004, (in Russian).]Шуровьески Дж., Мудрость толпы, Манн, Иванов и Фербер, 2013, http://www.mannivanov-ferber.ru/books/paperbook/the-wisdom-of-crowds/; [Surowiecki J., The Wisdom of Crowds, Doubleday, 2004, (in Russian).]Gadiraju U., Kawase R., Dietze S. et al., “Understanding Malicious Behavior in Crowdsourcing Platforms: The Case of Online Surveys”, Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 2015, 1631–1640, http://dx.doi.org/10.1145/2702123.2702443.Gadiraju U., Kawase R., Dietze S. et al., “Understanding Malicious Behavior in Crowdsourcing Platforms: The Case of Online Surveys”, Proceedings of the 33rd Annual ACM Conference on Human Factors in Computing Systems, 2015, 1631–1640, http://dx.doi.org/10.1145/2702123.2702443.Kittur A., Smus B., Khamkar S., et al., “CrowdForge: Crowdsourcing Complex Work”, Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology, 2011, 43–52, http://dx.doi.org/10.1145/2047196.2047202.Kittur A., Smus B., Khamkar S., et al., “CrowdForge: Crowdsourcing Complex Work”, Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology, 2011, 43–52, http://dx.doi.org/10.1145/2047196.2047202.Franklin M.J., Kossmann D., Kraska T. et al., “CrowdDB: Answering Queries with Crowdsourcing”, Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 2011, 61–72, http://dx.doi.org/10.1145/1989323.1989331.Franklin M.J., Kossmann D., Kraska T. et al., “CrowdDB: Answering Queries with Crowdsourcing”, Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, 2011, 61–72, http://dx.doi.org/10.1145/1989323.1989331.Kucherbaev P., Daniel F., Tranquillini S. et al., “Crowdsourcing Processes: A Survey of Approaches and Opportunities”, IEEE Internet Computing, 20:2 (2016), 50–56, http://dx.doi.org/10.1109/MIC.2015.96.Kucherbaev P., Daniel F., Tranquillini S. et al., “Crowdsourcing Processes: A Survey of Approaches and Opportunities”, IEEE Internet Computing, 20:2 (2016), 50–56, http://dx.doi.org/10.1109/MIC.2015.96.Johnston W. M., Hanna J. R. P., Millar R. J., “Advances in Dataflow Programming Languages”, ACM Comput. Surv., 36:1 (2004), 1–34, http://dx.doi.org/10.1145/1013208.1013209.Johnston W. M., Hanna J. R. P., Millar R. J., “Advances in Dataflow Programming Languages”, ACM Comput. Surv., 36:1 (2004), 1–34, http://dx.doi.org/10.1145/1013208.1013209.Стрельцов Н.В., “Архитектура и реализация мультиклеточных процессоров”, Труды V Международной научной конференции «Параллельные вычисления и задачи управления» (Москва, 26–28 октября 2010 г.), 2010, 1087–1104; [Streltsov N.V., “Arkhitektura i realizatsiya multikletochnykh protsessorov”, Trudy V Mezhdunarodnoy nauchnoy konferentsii “Parallelnye vychisleniya i zadachi upravleniya” (Moskva, 26–28 oktyabrya 2010 g.), 2010, 1087–1104, (in Russian).]Стрельцов Н.В., “Архитектура и реализация мультиклеточных процессоров”, Труды V Международной научной конференции «Параллельные вычисления и задачи управления» (Москва, 26–28 октября 2010 г.), 2010, 1087–1104; [Streltsov N.V., “Arkhitektura i realizatsiya multikletochnykh protsessorov”, Trudy V Mezhdunarodnoy nauchnoy konferentsii “Parallelnye vychisleniya i zadachi upravleniya” (Moskva, 26–28 oktyabrya 2010 g.), 2010, 1087–1104, (in Russian).]Kittur A., Khamkar S., Andr ́e P., “CrowdWeaver: Visually Managing Complex Crowd Work”, Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work, 2012, 1033–1036, http://dx.doi.org/10.1145/2145204.2145357.Kittur A., Khamkar S., Andr ́e P., “CrowdWeaver: Visually Managing Complex Crowd Work”, Proceedings of the ACM 2012 Conference on Computer Supported Cooperative Work, 2012, 1033–1036, http://dx.doi.org/10.1145/2145204.2145357.Giang N.K., Blackstock M., Lea R. et al., “Distributed Data Flow: A Programming Model for the Crowdsourced Internet of Things”, Proceedings of the Doctoral Symposium of the 16th International Middleware Conference, 4:1–4:4, http://dx.doi.org/10.1145/2843966.2843970.Giang N.K., Blackstock M., Lea R. et al., “Distributed Data Flow: A Programming Model for the Crowdsourced Internet of Things”, Proceedings of the Doctoral Symposium of the 16th International Middleware Conference, 4:1–4:4, http://dx.doi.org/10.1145/2843966.2843970.Kahn G., “The semantics of a simple language for parallel programming”, Information Processing, 74 (1974), 471–475.Kahn G., “The semantics of a simple language for parallel programming”, Information Processing, 74 (1974), 471–475.Murata T., “Petri Nets: Properties, Analysis and Applications”, Proceedings of the IEEE, 77:4 (1989), 541–580, http://dx.doi.org/10.1109/5.24143.Murata T., “Petri Nets: Properties, Analysis and Applications”, Proceedings of the IEEE, 77:4 (1989), 541–580, http://dx.doi.org/10.1109/5.24143.Bernstein M. S., Little G., Miller R. C. et al., “Soylent: A Word Processor with a Crowd Inside”, Proceedings of the 23Nd Annual ACM Symposium on User Interface Software and Technology, 2010, 313–322, http://dx.doi.org/10.1145/1866029.1866078.Bernstein M. S., Little G., Miller R. C. et al., “Soylent: A Word Processor with a Crowd Inside”, Proceedings of the 23Nd Annual ACM Symposium on User Interface Software and Technology, 2010, 313–322, http://dx.doi.org/10.1145/1866029.1866078.Noronha J., Hysen E., Zhang H. et al., “PlateMate: Crowdsourcing Nutritional Analysis from Food Photographs”, Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology, 2011, 1–12, http://dx.doi.org/10.1145/2047196.2047198.Noronha J., Hysen E., Zhang H. et al., “PlateMate: Crowdsourcing Nutritional Analysis from Food Photographs”, Proceedings of the 24th Annual ACM Symposium on User Interface Software and Technology, 2011, 1–12, http://dx.doi.org/10.1145/2047196.2047198.Wang J., Kraska T., Franklin M. J. et al., “CrowdER: Crowdsourcing Entity Resolution”, Proc. VLDB Endow., 5:11 (2012), 1483–1494, http://dx.doi.org/10.14778/2350229.2350263.Wang J., Kraska T., Franklin M. J. et al., “CrowdER: Crowdsourcing Entity Resolution”, Proc. VLDB Endow., 5:11 (2012), 1483–1494, http://dx.doi.org/10.14778/2350229.2350263.Biemann C., “Creating a system for lexical substitutions from scratch using crowdsourcing”, Language Resources and Evaluation, 47:1 (2013), 97–122, http://dx.doi.org/10.1007/s10579-012-9180-5.Biemann C., “Creating a system for lexical substitutions from scratch using crowdsourcing”, Language Resources and Evaluation, 47:1 (2013), 97–122, http://dx.doi.org/10.1007/s10579-012-9180-5.Schek H.-J., Scholl M.H., “The relational model with relation-valued attributes”, Information Systems, 11:2 (1986), 137–147, http://dx.doi.org/10.1016/03064379(86)90003-7.Schek H.-J., Scholl M.H., “The relational model with relation-valued attributes”, Information Systems, 11:2 (1986), 137–147, http://dx.doi.org/10.1016/03064379(86)90003-7.Garcia-Molina H., Ullman J. D., Widom J., Database Systems: The Complete Book, 2nd edition, Prentice Hall Press, 2008.Garcia-Molina H., Ullman J. D., Widom J., Database Systems: The Complete Book, 2nd edition, Prentice Hall Press, 2008.Zhao G., Huang W., Liang S. et al., “Modeling MongoDB with Relational Model”, Emerging Intelligent Data and Web Technologies (EIDWT), 2013 Fourth International Conference on, 2013, 115–121, http://dx.doi.org/10.1109/EIDWT.2013.25.Zhao G., Huang W., Liang S. et al., “Modeling MongoDB with Relational Model”, Emerging Intelligent Data and Web Technologies (EIDWT), 2013 Fourth International Conference on, 2013, 115–121, http://dx.doi.org/10.1109/EIDWT.2013.25.Panchenko A., Loukachevitch N. V., Ustalov D. et al., “RUSSE: The First Workshop on Russian Semantic Similarity”, Computational Linguistics and Intellectual Technologies: papers from the Annual conference “Dialogue”, 2 (2015), 89–105, http://www.dialog21.ru/digests/dialog2015/materials/pdf/PanchenkoAetal.pdf.Panchenko A., Loukachevitch N. V., Ustalov D. et al., “RUSSE: The First Workshop on Russian Semantic Similarity”, Computational Linguistics and Intellectual Technologies: papers from the Annual conference “Dialogue”, 2 (2015), 89–105, http://www.dialog21.ru/digests/dialog2015/materials/pdf/PanchenkoAetal.pdf.McCartney W.P., Sridhar N., “Abstractions for Safe Concurrent Programming in Networked Embedded Systems”, Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, 2006, 167–180, http://dx.doi.org/10.1145/1182807.1182825.McCartney W.P., Sridhar N., “Abstractions for Safe Concurrent Programming in Networked Embedded Systems”, Proceedings of the 4th International Conference on Embedded Networked Sensor Systems, 2006, 167–180, http://dx.doi.org/10.1145/1182807.1182825.Ustalov D., Kiselev Y., Cleansing”, Application of (AICT), 2015 IEEE 9th http://dx.doi.org/10.1109/ICAICT.2015.7338534. “Add-Remove-Confirm: Crowdsourcing Synset Information and Communication Technologies International Conference on, 2015, 143–147,Ustalov D., Kiselev Y., Cleansing”, Application of (AICT), 2015 IEEE 9th http://dx.doi.org/10.1109/ICAICT.2015.7338534. “Add-Remove-Confirm: Crowdsourcing Synset Information and Communication Technologies International Conference on, 2015, 143–147,Ustalov D., “Crowdsourcing Synset Relations with Genus-Species-Match”, Proceedings of the AINL-ISMW FRUCT, 2015, 118–124, http://dx.doi.org/10.1109/AINL-ISMWFRUCT.2015.7382980.Ustalov D., “Crowdsourcing Synset Relations with Genus-Species-Match”, Proceedings of the AINL-ISMW FRUCT, 2015, 118–124, http://dx.doi.org/10.1109/AINL-ISMWFRUCT.2015.7382980.Ustalov D., “A Crowdsourcing Engine for Mechanized Labor”, Proceedings of the Institute for System Programming, 27:3 (2015), 351–364, http://dx.doi.org/10.15514/ISPRAS2015-27(3)-25.Ustalov D., “A Crowdsourcing Engine for Mechanized Labor”, Proceedings of the Institute for System Programming, 27:3 (2015), 351–364, http://dx.doi.org/10.15514/ISPRAS2015-27(3)-25.Kiselev Y., Ustalov D., Porshnev S., “Eliminating Fuzzy Duplicates in Crowdsourced Lexical Resources”, Proceedings of the Eighth Global Wordnet Conference, 2016, 161– 167, http://gwc2016.racai.ro/procedings.pdf.Kiselev Y., Ustalov D., Porshnev S., “Eliminating Fuzzy Duplicates in Crowdsourced Lexical Resources”, Proceedings of the Eighth Global Wordnet Conference, 2016, 161– 167, http://gwc2016.racai.ro/procedings.pdf.Fleiss J.L., Levin B., Paik M.C., Statistical Methods for Rates and Proportions, 3rd edition, John Wiley & Sons, 2003.Fleiss J.L., Levin B., Paik M.C., Statistical Methods for Rates and Proportions, 3rd edition, John Wiley & Sons, 2003.Powers D.M.W., “The Problem with Kappa”, Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, 2012, 345–355, http://aclweb.org/anthology/E12-1035.Powers D.M.W., “The Problem with Kappa”, Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, 2012, 345–355, http://aclweb.org/anthology/E12-1035.Ляшевская О.Н., Шаров С.А., Частотный словарь современного русского языка (на материалах Национального корпуса русского языка), Азбуковник, 2009; [Lyashevskaya O. N., Sharoff S. A., Chastotnyy slovar sovremennogo russkogo yazyka (na materialakh Natsionalnogo korpusa russkogo yazyka), Azbukovnik, 2009, (in Russian).]Ляшевская О.Н., Шаров С.А., Частотный словарь современного русского языка (на материалах Национального корпуса русского языка), Азбуковник, 2009; [Lyashevskaya O. N., Sharoff S. A., Chastotnyy slovar sovremennogo russkogo yazyka (na materialakh Natsionalnogo korpusa russkogo yazyka), Azbukovnik, 2009, (in Russian).]Healy G.F., Gurrin C., Smeaton A.F., “Informed Perspectives on Human Annotation Using Neural Signals”, MultiMedia Modeling: 22nd International Conference, Proceedings, Part II, Lecture Notes in Computer Science, 9517, 2016, 315–327, http://dx.doi.org/10.1007/978-3-319-27674-8 28.Healy G.F., Gurrin C., Smeaton A.F., “Informed Perspectives on Human Annotation Using Neural Signals”, MultiMedia Modeling: 22nd International Conference, Proceedings, Part II, Lecture Notes in Computer Science, 9517, 2016, 315–327, http://dx.doi.org/10.1007/978-3-319-27674-8 28.Ignatov D.I., Kaminskaya A.Yu., Bezzubtseva A.A. et al., “FCA-Based Models and a Prototype Data Analysis System for Crowdsourcing Platforms”, Conceptual Structures for STEM Research and Education, Lecture Notes in Computer Science, 7735, 2013, 173– 192, http://dx.doi.org/10.1007/978-3-642-35786-2 13.Ignatov D.I., Kaminskaya A.Yu., Bezzubtseva A.A. et al., “FCA-Based Models and a Prototype Data Analysis System for Crowdsourcing Platforms”, Conceptual Structures for STEM Research and Education, Lecture Notes in Computer Science, 7735, 2013, 173– 192, http://dx.doi.org/10.1007/978-3-642-35786-2 13.

The authors declare that there are no conflicts of interest present.