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

アクセス数:647件（2025-08-25 23:41 集計）

固定URL: https://hdl.handle.net/11094/92858

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
Proc-IEEEIntConfBigData_4468	pdf	なし	343 KB	115	2023.10.31

論文情報

ファイル出力 EndNote Basic出力 Mendeley出力

タイトル	Approximate Top-k Inner Product Join with a Proximity Graph
著者	著者名 Nakama, Hayato
	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 著者名 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 著者名 Hara, Takahiro
キーワード等	approximation algorithm
	high-dimensional vector
	proximity graph
	top-k inner product join
内容	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.
抄録	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.
会議情報	会議名 2021 IEEE International Conference on Big Data (Big Data) 回次 2021 開催期間 December 15th to December 18th, 2021 開催地 Orlando 開催国アメリカ合衆国
出版者	Institute of Electrical and Electronics Engineers Inc.
収録物名	Proceedings - 2021 IEEE International Conference on Big Data, Big Data 2021
ページ	4468-4471
刊行年月	2021-12-15
言語	英語
ハンドルURL	https://hdl.handle.net/11094/92858
関連情報 (isVersionOf)	DOI (出版社版) https://doi.org/10.1109/BigData52589.2021.9671858
関連情報 (isPartOf)	ISBN 9781665439022
関連情報 (isPartOf)	ISBN 9781665445993
アクセス権	open access
権利情報	© 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.
出版タイプ	Accepted Manuscript
カテゴリ	会議発表論文 Conference Paper

資源タイプ	会議発表論文
ローカル資源タイプ	会議発表論文
DCMI資源タイプ	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	英語
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	英語
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

閲覧可能ファイル

論文情報

論文詳細を表示