RIANN: Real-time Incremental Learning with Approximate Nearest Neighbor on Mobile Devices

Authors: 

Jiawen Liu and Zhen Xie, University of California, Merced; Dimitrios Nikolopoulos, Virginia Tech; Dong Li, University of California, Merced

Abstract: 

Approximate nearest neighbor (ANN) algorithms are the foundation for many applications on mobile devices. Real-time incremental learning with ANN on mobile devices is emerging. However, incremental learning with current ANN algorithms on mobile devices is difficult, because data is dynamically and incrementally generated on mobile devices and as a result, it is difficult to reach high timing and recall requirements on indexing and search. Meeting the high timing requirements is critical on mobile devices because of short user response time and low battery lifetime.

We introduce an indexing and search system for graph-based ANN on mobile devices called RIANN. By constructing ANN with dynamic ANN construction properties, RIANN enables high flexibility for ANN construction to meet the high timing and recall requirements in incremental learning. To select an optimal ANN construction property, RIANN incorporates a statistical prediction model. RIANN further offers a novel analytical performance model to avoid runtime overhead and interaction with mobile devices. In our experiments, RIANN significantly outperforms the state-of-the-art ANN (2.42x speedup) on Samsung S9 mobile phone without compromising search time or recall. Also, for incrementally indexing 100 batches of data, the state-of-the-art ANN satisfies 55.33% batches on average while RIANN can satisfy 96.67% with minimum impact on recall.

OpML '20 Open Access Sponsored by NetApp

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 {256634,
author = {Jiawen Liu and Zhen Xie and Dimitrios Nikolopoulos and Dong Li},
title = {{RIANN}: Real-time Incremental Learning with Approximate Nearest Neighbor on Mobile Devices},
booktitle = {2020 {USENIX} Conference on Operational Machine Learning (OpML 20)},
year = {2020},
url = {https://www.usenix.org/conference/opml20/presentation/liu},
publisher = {{USENIX} Association},
month = jul,
}

Presentation Video 
Teaser
Full