I/O Efficient Algorithm for c-Approximate Furthest Neighbor Search in High-Dimensional Space

Liu, W; Wang, H; Zhang, Y; Qin, L; Zhang, W

I/O Efficient Algorithm for c-Approximate Furthest Neighbor Search in High-Dimensional Space

Liu, W

Wang, H Zhang, Y

Qin, L Zhang, W

Permalink

Publisher:: Springer International Publishing
Publication Type:: Conference Proceeding
Citation:: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, 12114 LNCS, pp. 221-236
Issue Date:: 2020-01-01

Closed Access

	Filename	Description	Size
	Liu2020_Chapter_IOEfficientAlgorithmForC-Appro (1).pdf	Accepted version	785.92 kB	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	Liu, W https://orcid.org/0000-0002-8529-855X
dc.contributor.author	Wang, H
dc.contributor.author	Zhang, Y https://orcid.org/0000-0002-2674-1638
dc.contributor.author	Qin, L
dc.contributor.author	Zhang, W
dc.contributor.editor	Nah, Y
dc.contributor.editor	Cui, B
dc.contributor.editor	Lee, S-W
dc.contributor.editor	Yu, JX
dc.contributor.editor	Moon, Y-S
dc.contributor.editor	Whang, SE
dc.date.accessioned	2020-11-03T01:48:25Z
dc.date.available	2020-11-03T01:48:25Z
dc.date.issued	2020-01-01
dc.identifier.citation	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, 12114 LNCS, pp. 221-236
dc.identifier.isbn	9783030594183
dc.identifier.issn	0302-9743
dc.identifier.issn	1611-3349
dc.identifier.uri	http://hdl.handle.net/10453/143720
dc.description.abstract	© 2020, Springer Nature Switzerland AG. Furthest Neighbor search in high-dimensional space has been widely used in many applications such as recommendation systems. Because of the “curse of dimensionality” problem, c-approximate furthest neighbor (C-AFN) is a substitute as a trade-off between result accuracy and efficiency. However, most of the current techniques for external memory are only suitable for low-dimensional space. In this paper, we propose a novel algorithm called reverse incremental LSH based on Indyk’s LSH scheme to solve the problem with theoretical guarantee. Unlike the previous methods using hashing scheme, reverse incremental LSH (RI-LSH) is designed for external memory and can achieve a good performance on I/O cost. We provide rigorous theoretical analysis to prove that RI-LSH can return a-AFN result with a constant possibility. Our comprehensive experiment results show that, compared with other-AFN methods with theoretical guarantee, our algorithm can achieve better I/O efficiency.
dc.language	en
dc.publisher	Springer International Publishing
dc.relation.ispartof	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.relation.ispartofseries	Lecture Notes in Computer Science
dc.relation.isbasedon	10.1007/978-3-030-59419-0_14
dc.rights	info:eu-repo/semantics/closedAccess
dc.subject.classification	Artificial Intelligence & Image Processing
dc.title	I/O Efficient Algorithm for c-Approximate Furthest Neighbor Search in High-Dimensional Space
dc.type	Conference Proceeding
utslib.citation.volume	12114 LNCS
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
pubs.organisational-group	/University of Technology Sydney
utslib.copyright.status	closed_access	*
dc.date.updated	2020-11-03T01:48:15Z
pubs.publication-status	Published
pubs.volume	12114 LNCS

Abstract:

© 2020, Springer Nature Switzerland AG. Furthest Neighbor search in high-dimensional space has been widely used in many applications such as recommendation systems. Because of the “curse of dimensionality” problem, c-approximate furthest neighbor (C-AFN) is a substitute as a trade-off between result accuracy and efficiency. However, most of the current techniques for external memory are only suitable for low-dimensional space. In this paper, we propose a novel algorithm called reverse incremental LSH based on Indyk’s LSH scheme to solve the problem with theoretical guarantee. Unlike the previous methods using hashing scheme, reverse incremental LSH (RI-LSH) is designed for external memory and can achieve a good performance on I/O cost. We provide rigorous theoretical analysis to prove that RI-LSH can return a-AFN result with a constant possibility. Our comprehensive experiment results show that, compared with other-AFN methods with theoretical guarantee, our algorithm can achieve better I/O efficiency.

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

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