Logo image
Back
Two-dimensional indexing to provide one-integrated-memory view of distributed memory for a massively-parallel search engine
Journal article   Peer reviewed

Two-dimensional indexing to provide one-integrated-memory view of distributed memory for a massively-parallel search engine

Tae-Seob Yun, Kyu-Young Whang, Hyuk-Yoon Kwon, Jun-Sung Kim and Il-Yeol Song
World wide web (Bussum), v 22(6), pp 2437-2467
01 Nov 2019
DOI: https://doi.org/10.1007/s11280-018-0647-1

Abstract

Computer Science Computer Science, Information Systems Computer Science, Software Engineering Science & Technology Technology
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 nx 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.

Metrics

8 Record Views
1 citations in Web of Science

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
International collaboration
Web of Science research areas
Computer Science, Information Systems
Computer Science, Software Engineering
Logo image