Files in this item

FilesDescriptionFormat

application/pdf

application/pdfmain.pdf (689kB)
Main ArticlePDF

Description

Title:Fast Compaction Algorithms for NoSQL Databases
Author(s):Ghosh, Mainak; Gupta, Indranil; Gupta, Shalmoli; Kumar, Nirman
Subject(s):compaction
nosql
np-hard
greedy
Abstract:Compaction plays a crucial role in NoSQL systems to ensure a high overall read throughput. In this work, we formally define compaction as an optimization problem that attempts to minimize disk I/O.We prove this problem to be NPHard. We then propose a set of algorithms and mathematically analyze upper bounds on worst-case cost. We evaluate the proposed algorithms on real-life workloads. Our results show that our algorithms incur low I/O costs and that a compaction approach using a balanced tree is most preferable.
Issue Date:2015-04-27
Genre:Technical Report
Type:Text
Language:English
URI:http://hdl.handle.net/2142/75865
Sponsor:NSF CNS 1319527, NSF CCF 0964471, AFOSR/AFRL FA8750-11-2-0084, NSF CCF 1319376, NSF CCF 1217462, NSF CCF 1161495 and a DARPA grant
Date Available in IDEALS:2015-04-26


This item appears in the following Collection(s)

Item Statistics