首页|I/O Efficient Approximate Nearest Neighbour Search based on Learned Functions
I/O Efficient Approximate Nearest Neighbour Search based on Learned Functions
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NETL
IEEE
Approximate nearest neighbour search (ANNS) in high dimensional space is a fundamental problem in many applications， such as multimedia database， computer vision and information retrieval。 Among many solutions， data-sensitive hashing-based methods are effective to this problem， yet few of them are designed for external storage scenarios and hence do not optimized for I/O efficiency during the query processing。 In this paper， we introduce a novel data-sensitive indexing and query processing framework for ANNS with an emphasis on optimizing the I/O efficiency， especially， the sequential I/Os。 The proposed index consists of several lists of point IDs， ordered by values that are obtained by learned hashing (i。e。， mapping) functions on each corresponding data point。 The functions are learned from the data and approximately preserve the order in the high-dimensional space。 We consider two instantiations of the functions (linear and non-linear)， both learned from the data with novel objective functions。 We also develop an I/O efficient ANNS framework based on the index。 Comprehensive experiments on six benchmark datasets show that our proposed methods with learned index structure perform much better than the state-of-the-art external memory-based ANNS methods in terms of I/O efficiency and accuracy。
Mingjie Li、Ying Zhang、Yifang Sun、Wei Wang、Ivor W. Tsang、Xuemin Lin
展开 >
Zhejiang Gongshang University,China
University of New South Wales,School of Computer Science and Engineering,Australia
University of Technology,CAI, School of Computer Science,Sydney,Australia
IEEE International Conference on Data Engineering
Dallas(US)
2020 IEEE 36th International Conference on Data Engineering
NETL
IEEE
