Generating Supplementary Index Records Using Morphological Analysis for High-speed Partial Matching

GENERATING SUPPLEMENTARY INDEX RECORDS USING MORPHOLOGICAL ANALYSIS FOR HIGH-SPEED PARTIAL MATCHING Masahiro Oku NTT Affiliated Business Headquarters 20-2 Nishi-shinjuku 3-Chome Shinjuku-ku, Tokyo 163-1419 Japan E-mail: oku@nbd.hqs.ntt.co.jp and Ryousuke Noda and Ryoji Nagai NTT Information and Communication Systems Laboratories 1-1, Hikari-no-oka, Yokosuka-shi, Kanagawa 239-0847 Japan E-mail: {noda, nagai)@isl.ntt.co.jp ABSTRACT The telephone directory retrieval task requires high-speed partial matching, and many processes run concurrently so there is a need to reduce resource requirements such as CPU power. To real- ize the high-speed partial matching that satisfies these requirements, this paper proposes a method for generating supplementary index records. This method enables us to retrieve all candidates in- cluding all words within strings input by users from a DB without applying morphological analysis to the input strings on the fly. Moreover, this paper describes the results of evaluation ex- periments. The experimental results show that the proposed method requires about 60% less CPU power and 80% less logical disk I/0 than the simple partial matching, and that the proposed method takes less than about 5 seconds when fewer than 100 records are retrieved. Namely, the experimental results show that the proposed method satisfies the requirements mentioned above quite well. This means that the proposed method is practical when applied to the telephone direc- tory retrieval task. 1. INTRODUCTION Higashida [4] has been developing a fully automated Japanese telephone directory assistance system using touch-tone telephones as input devices [3] [4]. In the written Japanese language, there are no spaces between words. Therefore, Japanese morphological analysis is necessary to recognize word boundaries for input strings. However, since morphological analysis requires high-cost processing, it is not suitable for the telephone directory retrieval task in which processing speed is very important. Let' s consider that a company name is input as the retrieving keyword by a telephone directory user. If the user knows and inputs the complete company name, the system can exactly match the keywords input against the index records in the DB. However, many users know only part of the com- pany name. In this case, a partial string of the company name is input as the retrieving keyword. Namely, it is unusual for there to be an exact match between retrieving keywords and index records and partial matching is the fundamental operation for the telephone directory retrieval task. Consequently, the requirements for telephone directory retrieval task are as follows: • High-speed partial matching: In the telephone directory retrieval task, it is necessary to obtain retrieval results from incomplete in- put strings. In order to satisfy this requirement, we have to perform partial matching. In the tele- phone directory retrieval task, the number of records in the subject DB is of the order of several mil- lion. Therefore, we have to develop an extremely high-speed partial matching method. • Supporting many processes concurrently by reducing resource requirements: Since many tasks must be handled at the same time in the telephone directory retrieval task, the sys- tem must invoke many processes concurrently. Therefore, it is indispensable …

Content truncated to 500 words