The Case for Learned Index Structures

Authors:
Tim Kraska; Alex Beutel; Ed H. Chi; Jeffrey Dean; Neoklis Polyzotis

 Name:
Kayala Sai Kumar.

 Motivation:
With rapid growth of data, need for fast and efficient database access has become indispensable.This paper proposes a machine learning approach that can potentially replace popular indexing data structures like B-trees.

 Positive Points:

 (1) Previous learned indexes used a neural network as a hash function for indexing [1,2,3] while the proposed algorithm uses neural network as a continuous function for describing the pattern in the data (CDF) to index.

 (2) The mixture of experts is proposed for learning substantially large databases since a neural network capacity to learn more data is limited by its parameters. This paper leverages this state-of-the-art technique to reduce the error by sub-setting the database and reducing the overall complexity in terms of computation which is an interesting approach.

 (3) Minimizing the min error of the recursive model by building a B-tree (has a min err=0) on top of that can be seen as a virtual B-tree with very fast look up time and efficient memory storage.

 (4) Size of the B-Tree index limits the data that can reside in cache memory for large database when compared to the recursive model that utilize less than 3MB which  can be stored in cache reducing cache faults and increasing cache efficiency (without considering the GPU latency).


Negative Points:

(1) Despite all the advantages discussed in the paper for the recursive model, it further increases hyper-parameters like number of stages and number of models in each stage. This increase in number of hyper-parameters makes the hyper-parameter tuning difficult since training this network is very expensive.

(2) The proposed method do not support any insertions, deletions or updates, since any change in database would require re-training of the model which is not desired considering the fact that training even a single neural network is still not possible within a few cycles with the available computing power.

Comments

  1. jon_weissmanFebruary 5, 2019 at 7:20 AM

    Good discussion of negative points. I also think complexity is an issue.

    ReplyDelete

Post a Comment

Popular posts from this blog

A Machine Learning Approach to Live Migration Modeling

Dynamic management of resources in data centers improves data center utilization in terms of energy consumption and device utilization. Virtual machines are among techniques to achieve this goal. To enable the VM to adapt to dynamic fluctuations of workloads, Live Migrated virtual machines are introduced, which stands for moving a VM from one physical host to another while the VM keeps running. Live migration enables load balancing, fault tolerance, ease maintenance, etc. However, live migration is costly in terms of data traffic. Having an understanding of performance metrics of different live migration algorithms is important so that one can rely on an efficient algrothm to migrate a running VM is important. Therefore, this work uses a Machine Learning (ML) approach to predict key metrics of different live migration algorithms, and then find the best suitable choice for live migration. Indeed, given resource usage as well as the characteristics of VM work load, this paper predict...
Read more

StormDroid: A Streaminglized Machine Learning-Based System for Detecting Android Malware

Introduction: The paper approaches the problem of Malware Detection using machine learning approach. In this paper, the authors propose considering new type of features along with two traditionally used set of features for developing techniques for malware detection. Along with this proposal, the paper makes other contributions as well. The authors provide a new framework which is able to process information from large data sets as streams, and efficiently perform malware detection. Motivation: Android is an open platform for development. It has certainly made easy for everyone to develop and publish apps.  The number of apps published on Google store is in millions. However, it has also made easier for hackers to reach out to a larger population for malicious attacks. Additionally, with surge in the number of attacks on devices, more data is available for analysis which can be used by the machine learning models to identify malicious apps. This is motivation to use machine ...
Read more

CrystalBall: Statically Analyzing Runtime Behavior via Deep Sequence Learning

Image
Author:  Stephen Zekany, Daniel Rings, Nathan Harada, Michael A. Laurenzano, Lingjia Tang, Jason Mars Intro: Understanding the runtime behavior of the software is critical in many aspects of program development. A conventional approach to this problem is using dynamic profiling, meaning we have to run the program multiple times with environments that representative enough for the actual working situation. Besides that, a dynamic profiling approach has other weakness such as cannot profiling a subset of functions or paths very economically and requires re-profiling each time any changes is applied to the code. This paper presents a statically profiling method, harnessing the ability of RNN to discover the hidden information of hot path in the code. Also, since the training process uses intermediate representation as input, the result will have better generalization power. Methodology: The dataset is in the form of a basic block feature; each sequence of basic blocks repr...
Read more