GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction

Yu, Y; Wen, D; Zhang, Y; Qin, L; Zhang, W; Lin, X

GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction

Yu, Y Wen, D

Zhang, Y Qin, L

Zhang, W Lin, X

Permalink

Publisher:: Institute of Electrical and Electronics Engineers (IEEE)
Publication Type:: Conference Proceeding
Citation:: Proceedings - International Conference on Data Engineering, 2022, 2022-May, pp. 552-564
Issue Date:: 2022-01-01

Recently Added

	Filename	Description	Size
	GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction.pdf	Accepted version	736.42 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Open Access

This item is new to OPUS and is not currently available.

Full metadata record

Field	Value	Language
dc.contributor.author	Yu, Y
dc.contributor.author	Wen, D https://orcid.org/0000-0002-0903-1503
dc.contributor.author	Zhang, Y
dc.contributor.author	Qin, L https://orcid.org/0000-0001-6068-5062
dc.contributor.author	Zhang, W
dc.contributor.author	Lin, X
dc.date	2022-05-09
dc.date.accessioned	2023-02-28T00:50:31Z
dc.date.available	2023-02-28T00:50:31Z
dc.date.issued	2022-01-01
dc.identifier.citation	Proceedings - International Conference on Data Engineering, 2022, 2022-May, pp. 552-564
dc.identifier.isbn	9781665408837
dc.identifier.issn	1084-4627
dc.identifier.uri	http://hdl.handle.net/10453/166490
dc.description.abstract	The approximate nearest neighbor (ANN) search in high-dimensional space offers a wide spectrum of applications across many domains such as database, machine learning, multimedia and computer vision. A variety of ANN search algorithms have been proposed in the literature. In recent years, proximity graph-based approaches have attracted considerable attention from both industry and academic settings due to the superior search performance in terms of speed and accuracy. A recent work utilizes a graphics processing unit (GPU) to accelerate the ANN search on proximity graphs. Though significantly reducing the distance computation time by taking advantage of the massive parallelism of GPUs, the algorithm suffers from the high expenses of data structure operations. In this paper, we propose a novel GPU -accelerated algorithm that designs a novel GPU-friendly search framework on proximity graphs to fully exploit the massively parallel processing power of GPUs at key steps of the search. Also, we propose GPU-accelerated proximity graph construction algorithms which can build high-quality representative proximity graphs with efficient parallel implementations. Extensive experiments on benchmark high-dimensional datasets demonstrate the outstanding performance of our proposed algorithms in both ANN search and proximity graph construction.
dc.language	en
dc.publisher	Institute of Electrical and Electronics Engineers (IEEE)
dc.relation	http://purl.org/au-research/grants/arc/DP210101393
dc.relation	http://purl.org/au-research/grants/arc/DP210101347
dc.relation	http://purl.org/au-research/grants/arc/FT200100787
dc.relation.ispartof	Proceedings - International Conference on Data Engineering
dc.relation.ispartof	2022 IEEE 38th International Conference on Data Engineering (ICDE)
dc.relation.isbasedon	10.1109/ICDE53745.2022.00046
dc.rights	info:eu-repo/semantics/restrictedAccess
dc.title	GPU-accelerated Proximity Graph Approximate Nearest Neighbor Search and Construction
dc.type	Conference Proceeding
utslib.citation.volume	2022-May
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
utslib.copyright.status	recently_added	*
dc.date.updated	2023-02-28T00:50:30Z
pubs.finish-date	2022-05-12
pubs.publication-status	Published
pubs.start-date	2022-05-09
pubs.volume	2022-May

Abstract:

The approximate nearest neighbor (ANN) search in high-dimensional space offers a wide spectrum of applications across many domains such as database, machine learning, multimedia and computer vision. A variety of ANN search algorithms have been proposed in the literature. In recent years, proximity graph-based approaches have attracted considerable attention from both industry and academic settings due to the superior search performance in terms of speed and accuracy. A recent work utilizes a graphics processing unit (GPU) to accelerate the ANN search on proximity graphs. Though significantly reducing the distance computation time by taking advantage of the massive parallelism of GPUs, the algorithm suffers from the high expenses of data structure operations. In this paper, we propose a novel GPU -accelerated algorithm that designs a novel GPU-friendly search framework on proximity graphs to fully exploit the massively parallel processing power of GPUs at key steps of the search. Also, we propose GPU-accelerated proximity graph construction algorithms which can build high-quality representative proximity graphs with efficient parallel implementations. Extensive experiments on benchmark high-dimensional datasets demonstrate the outstanding performance of our proposed algorithms in both ANN search and proximity graph construction.

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

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