Two-dimensional indexing to provide one-integrated-memory view of distributed memory for a massively-parallel search engine (vol 22, pg 2437, 2018)

作     者：Yun, Tae-Seob Whang, Kyu-Young Kwon, Hyuk-Yoon Kim, Jun-Sung Song, Il-Yeol 

作者机构：Korea Adv Inst Sci & Technol Dept Comp Sci Daejeon South Korea Seoul Natl Univ Sci & Technol Dept Global Fus Ind Engn Seoul South Korea Drexel Univ Coll Informat Sci & Technol Philadelphia PA 19104 USA 

出 版 物：《WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS》 (万维网)

年 卷 期：2019年第22卷第6期

页      面：2469-2470页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：This work was supported by the National Research Foundation of Korea(NRF) grant funded by Korean Government(MSIT) (No. 2016R1A2B4015929) 

主　　题：Massively-parallel search engine DB-IR integration Pre-join Multiple-keyword search queries Distributed memory 

摘      要：We propose two-dimensional indexing—a novel in-memory indexing architecture that operates over distributed memory of a massively-parallel search engine. The goal of two-dimensional indexing is to provide a one-integrated-memory view as in a single node system using one large integrated memory. In two-dimensional indexing, we partition the entire index into n× m fragments and distribute them over the memories of multiple nodes in such a way that each fragment is entirely stored in main memory of one node. The proposed architecture is not only scalable as it uses a scaled-out shared-nothing architecture but also is capable of achieving low query response time as it processes queries in main memory. We also propose the concept of the one-memory point, which is the amount of the memory space required to completely store the entire index in main memory providing a one-integrated-memory view. We first prove the effectiveness of two-dimensional indexing with single-keyword queries, and then, extend the notion so as to be able to handle multiple-keyword queries. To handle multiple-keyword queries, we adopt pre-join that materializes a multiple-keyword query a priori as well as a new notion of semi-memory join that obviates extensive communication overhead to perform join across multiple nodes. In experiments using the real-life search query set over a database consisting of 100 million Web documents crawled, we show that two-dimensional indexing can effectively provide a one-integrated-memory view without too much of additional memory compared with the single node system using one large integrated memory. We also show that, with a six-node prototype, in an ideal case, it significantly improves the query processing performance over a disk-based search engine with an equivalent amount of in-memory buffer but without two-dimensional indexing — by up to 535.54 times. This improvement is expected to get larger as the system is scaled-out with a larger number of machines.