Approximate Top-k Inner Product Join with a Proximity Graph

Nakama, Hayato; Amagata, Daichi; Hara, Takahiro

doi:https://doi.org/10.1109/BigData52589.2021.9671858

Approximate Top-k Inner Product Join with a Proximity Graph

Nakama, Hayato; Amagata, Daichi; Hara, Takahiro

Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021, 2021, 4468-4471

Number of Access:642（2025-08-14 10:07 Counts）

Identifier to cite or link to this item: https://hdl.handle.net/11094/92858

Link to primary information

File	Format	Terms of use	Size	Views	Date.Available	Description	information
Proc-IEEEIntConfBigData_4468	pdf	None	343 KB	115	2023.10.31

Item Information

Output File Export EndNote Basic Export Mendeley

Title	Approximate Top-k Inner Product Join with a Proximity Graph
Creator	CreatorName Nakama, Hayato
	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 CreatorName Amagata, Daichi
	NRID 1000020294043 1000020294043 ORCID 0000-0003-4807-3156 0000-0003-4807-3156 researchmap permalink hara-osakau hara-osakau Scopus Author ID 7404213547 7404213547 CreatorName Hara, Takahiro
Subject	approximation algorithm
	high-dimensional vector
	proximity graph
	top-k inner product join
Description	Nakama H., Amagata D., Hara T.. Approximate Top-k Inner Product Join with a Proximity Graph. Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021 , 4468 (2021); https://doi.org/10.1109/BigData52589.2021.9671858.
Abstract	This paper addresses the problem of top-k inner product join, which, given two sets of high-dimensional vectors and a result size k, outputs k pairs of vectors that have the largest inner product. This problem has important applications, such as recommendation, information extraction, and finding outlier correlation. Unfortunately, computing the exact answer incurs an expensive cost for large high-dimensional datasets. We therefore consider an approximate solution framework that efficiently retrieves k pairs of vectors with large inner products. To exploit this framework and obtain an accurate answer, we extend a state-of-the-art proximity graph for inner product search. We conduct experiments on real datasets, and the results show that our solution is faster and more accurate than baselines with state-of-the-art techniques.
Conference Information	Conference Name 2021 IEEE International Conference on Big Data (Big Data) Conference Sequence 2021 Conference Date December 15th to December 18th, 2021 Conference Place Orlando Conference Country United States of America
Publisher	Institute of Electrical and Electronics Engineers Inc.
Source Title	Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021
Page	4468-4471
Date of Issued	2021-12-15
Language	English
Handle URL	https://hdl.handle.net/11094/92858
Relation.isVersionOf	DOI (Publisher Version) https://doi.org/10.1109/BigData52589.2021.9671858
Relation.isPartOf	ISBN 9781665439022
Relation.isPartOf	ISBN 9781665445993
Access Rights	open access
CopyRight	© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
oaire:version	Accepted Manuscript
Category	会議発表論文 Conference Paper

Resource Type	conference paper
Local Type	Conference Paper
DCMI Type	Text
DCTERMS.bibliographicCitation	Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021. 2021, p. 4468-4471
DC.title	Approximate Top-k Inner Product Join with a Proximity Graph
DC.creator	Nakama, Hayato
	Amagata, Daichi
	Hara, Takahiro
DC.publisher	Institute of Electrical and Electronics Engineers Inc.
DC.language' scheme='DCTERMS.RFC1766	English
DC.type' scheme='DCTERMS.DCMIType	Text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2021-12-15
DC.identifier	https://doi.org/10.1109/BigData52589.2021.9671858
DC.subject	approximation algorithm
	high-dimensional vector
	proximity graph
	top-k inner product join
DC.description	Nakama H., Amagata D., Hara T.. Approximate Top-k Inner Product Join with a Proximity Graph. Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021 , 4468 (2021); https://doi.org/10.1109/BigData52589.2021.9671858.
DCTERMS.abstract	This paper addresses the problem of top-k inner product join, which, given two sets of high-dimensional vectors and a result size k, outputs k pairs of vectors that have the largest inner product. This problem has important applications, such as recommendation, information extraction, and finding outlier correlation. Unfortunately, computing the exact answer incurs an expensive cost for large high-dimensional datasets. We therefore consider an approximate solution framework that efficiently retrieves k pairs of vectors with large inner products. To exploit this framework and obtain an accurate answer, we extend a state-of-the-art proximity graph for inner product search. We conduct experiments on real datasets, and the results show that our solution is faster and more accurate than baselines with state-of-the-art techniques.
DC.rights	© 2021 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
DC.format	92858
citation_title	Approximate Top-k Inner Product Join with a Proximity Graph
citation_author	Nakama, Hayato
	Amagata, Daichi
	Hara, Takahiro
citation_publisher	Institute of Electrical and Electronics Engineers Inc.
citation_language	English
citation_date	2021-12-15
citation_journal_title	Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021
citation_firstpage	4468
citation_lastpage	4471
citation_doi	https://doi.org/10.1109/BigData52589.2021.9671858
citation_public_url	https://hdl.handle.net/11094/92858

Approximate Top-k Inner Product Join with a Proximity Graph

Link to primary information

Item Information

Show details