Massively Parallel Memory-Based Parsing

Abstract

This paper discusses a radically new scheme of natural language processing called massively parallel memorybased parsing. Most parsing schemes are rule-based or principle-based which involves extensive serial rule application. Thus, it is a time consuming task which requires a few seconds or even a few minutes to complete th e parsing of one sentence. Also, the degree of parallelism attained by mapping such a scheme on parallel computers is at most medium, so that the existing scheme can not take advantage of massively parallel computing. The massively parallel memory-basedparsing takes a radical departure from the traditional view. It views parsing as a memory-intensive process which can be sped up by massively parallel computing. Although we know of some studies in this direction, we have seen no report regarding implementation strategies on actual massively parallel machines, on performance, or on practicality accessment based on actual data. Thus, this paper focuses on discussion of the feasibility and problems of the approach based on actual massively parallel implementation using real data. The degree of parallelism attained in our model reaches a few thousands, and the performance of a few milliseconds per sentence has been accomplished. In addition, parsing time grows only linearly (or sublinearly) to th e length of the input sentences. The experimental results show the approach is promising for real-time parsing and bulk text processing.