Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement

Li, W; Zhang, Y; Sun, Y; Wang, W; Zhang, W; Lin, X

Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement

Li, W Zhang, Y

Sun, Y Wang, W Zhang, W Lin, X

Permalink

Publisher:: Institute of Electrical and Electronics Engineers
Publication Type:: Journal Article
Citation:: IEEE Transactions on Knowledge and Data Engineering, 2020, 32, (8), pp. 1475-1488
Issue Date:: 2020-08-01

Closed Access

	Filename	Description	Size
	Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement.pdf	Published Version	2.45 MB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Li, W
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Sun, Y
dc.contributor.author	Wang, W
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.date.accessioned	2021-05-21T02:28:43Z
dc.date.available	2021-05-21T02:28:43Z
dc.date.issued	2020-08-01
dc.identifier.citation	IEEE Transactions on Knowledge and Data Engineering, 2020, 32, (8), pp. 1475-1488
dc.identifier.issn	1041-4347
dc.identifier.issn	1558-2191
dc.identifier.uri	http://hdl.handle.net/10453/149034
dc.description.abstract	Approximate Nearest neighbor search (ANNS) is fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Although many algorithms have been continuously proposed in the literature in the above domains each year, there is no comprehensive evaluation and analysis of their performances. In this paper, we conduct a comprehensive experimental evaluation of many state-of-the-art methods for approximate nearest neighbor search. Our study (1) is cross-disciplinary (i.e., including 16 algorithms in different domains, and from practitioners) and (2) has evaluated a diverse range of settings, including 20 datasets, several evaluation metrics, and different query workloads. The experimental results are carefully reported and analyzed to understand the performance results. Furthermore, we propose a new method that achieves both high query efficiency and high recall empirically on majority of the datasets under a wide range of settings.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers
dc.relation	http://purl.org/au-research/grants/arc/FT170100128
dc.relation	http://purl.org/au-research/grants/arc/DP180103096
dc.relation.ispartof	IEEE Transactions on Knowledge and Data Engineering
dc.relation.isbasedon	10.1109/TKDE.2019.2909204
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject	08 Information and Computing Sciences
dc.subject.classification	Information Systems
dc.title	Approximate Nearest Neighbor Search on High Dimensional Data — Experiments, Analyses, and Improvement
dc.type	Journal Article
utslib.citation.volume	32
utslib.for	08 Information and Computing Sciences
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - AAII - Australian Artificial Intelligence Institute
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology/School of Computer Science
utslib.copyright.status	closed_access	*
pubs.consider-herdc	true
dc.date.updated	2021-05-21T02:28:41Z
pubs.issue	8
pubs.publication-status	Published
pubs.volume	32
utslib.citation.issue	8

Abstract:

Approximate Nearest neighbor search (ANNS) is fundamental and essential operation in applications from many domains, such as databases, machine learning, multimedia, and computer vision. Although many algorithms have been continuously proposed in the literature in the above domains each year, there is no comprehensive evaluation and analysis of their performances. In this paper, we conduct a comprehensive experimental evaluation of many state-of-the-art methods for approximate nearest neighbor search. Our study (1) is cross-disciplinary (i.e., including 16 algorithms in different domains, and from practitioners) and (2) has evaluated a diverse range of settings, including 20 datasets, several evaluation metrics, and different query workloads. The experimental results are carefully reported and analyzed to understand the performance results. Furthermore, we propose a new method that achieves both high query efficiency and high recall empirically on majority of the datasets under a wide range of settings.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/149034