Neural Trees: Using Neural Networks as an Alternative to Binary Comparison in Classical Search Trees

Authors: 

Douglas Santry, NetApp

Abstract: 

Binary comparison, the basis of the venerable B Tree, is per-haps the most successful operator for indexing data on sec-ondary storage. We introduce a different technique, called Neural Trees, that is based on neural networks. Neural Trees increase the fan-out per byte of a search tree by up to 40% compared to B Trees. Increasing fan-out reduces memory demands and leads to increased cacheability while decreasing height and media accesses. A Neural Tree also permits search path layout policies that divorce a key’s value from its physi-cal location in a data structure. This is an advantage over the total ordering required by binary comparison, which totally determines the physical location of keys in a tree. Previous attempts to apply machine learning to indices are based on learning the data directly, which renders insertion too expen-sive to be supported. The Neural Tree is a hybrid scheme using a hierarchy (tree) of small neural networks to learn search paths instead of the data directly. Neural Trees can efficiently handle a general read/write workload. We evaluate Neural Trees with weeks of traces from production storage traces and SPC1 workloads to demonstrate their viability.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {254272,
author = {Douglas Santry},
title = {Neural Trees: Using Neural Networks as an Alternative to Binary Comparison in Classical Search Trees},
booktitle = {12th {USENIX} Workshop on Hot Topics in Storage and File Systems (HotStorage 20)},
year = {2020},
url = {https://www.usenix.org/conference/hotstorage20/presentation/santry},
publisher = {{USENIX} Association},
month = jul,
}

Presentation Video