Simpler is Much Faster: Fair and Independent Inner Product Search

Aoyama, Kazuyoshi; Amagata, Daichi; Fujita, Sumio; Hara, Takahiro

doi:https://doi.org/10.1145/3539618.3592061

Simpler is Much Faster: Fair and Independent Inner Product Search

Aoyama, Kazuyoshi; Amagata, Daichi; Fujita, Sumio et al.

SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2023, 2379-2383

アクセス数:372件（2025-06-17 14:51 集計）

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

閲覧可能ファイル

ファイル	フォーマット	利用条件	サイズ	閲覧回数	利用開始日	説明	information
SIGIR-ProcIntACMSIGIRConfResDevInfRetr_2379	pdf	なし	1.06 MB	137	2023.10.17

Creative Commons : 表示 - 非営利

論文情報

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

タイトル	Simpler is Much Faster: Fair and Independent Inner Product Search
著者	著者名 Aoyama, Kazuyoshi
	NRID 1000040770649 1000040770649 researchmap permalink amgt amgt Scopus Author ID 55811167300 55811167300 著者名 Amagata, Daichi
	著者名 Fujita, Sumio
	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
キーワード等	fairness
	independence
	inner product search
内容	Aoyama K., Amagata D., Fujita S., et al. Simpler is Much Faster: Fair and Independent Inner Product Search. SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval , 2379 (2023); https://doi.org/10.1145/3539618.3592061.
抄録	The problem of inner product search (IPS) is important in many fields. Although maximum inner product search (MIPS) is often considered, its result is usually skewed and static. Users are hence hard to obtain diverse and/or new items by using the MIPS problem. Motivated by this, we formulate a new problem, namely the fair and independent IPS problem. Given a query, a threshold, and an output size k, this problem randomly samples k items from a set of items such that the inner product of the query and item is not less than the threshold. For each item that satisfies the threshold, this problem is fair, because the probability that such an item is outputted is equal to that for each other item. This fairness can yield diversity and novelty, but this problem faces a computational challenge. Some existing (M)IPS techniques can be employed in this problem, but they require O(n) or o(n) time, where n is the dataset size. To scale well to large datasets, we propose a simple yet efficient algorithm that runs in O(logn + k) expected time. We conduct experiments using real datasets, and the results demonstrate that our algorithm is up to 330 times faster than baselines.
出版者	Association for Computing Machinery, Inc
収録物名	SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval
ページ	2379-2383
刊行年月	2023-07-19
言語	英語
ハンドルURL	https://hdl.handle.net/11094/92782
関連情報 (isIdenticalTo)	DOI (出版社版) https://doi.org/10.1145/3539618.3592061
アクセス権	open access
権利情報	This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
出版タイプ	Version of Record
カテゴリ	会議発表論文 Conference Paper

資源タイプ	会議発表論文
ローカル資源タイプ	会議発表論文
DCMI資源タイプ	text
DCTERMS.bibliographicCitation	SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval. 2023, p. 2379-2383
DC.title	Simpler is Much Faster: Fair and Independent Inner Product Search
DC.creator	Aoyama, Kazuyoshi
	Amagata, Daichi
	Fujita, Sumio
	Hara, Takahiro
DC.publisher	Association for Computing Machinery, Inc
DC.language' scheme='DCTERMS.RFC1766	英語
DC.type' scheme='DCTERMS.DCMIType	text
DCTERMS.issued' scheme='DCTERMS.W3CDTF	2023-07-19
DC.identifier	https://doi.org/10.1145/3539618.3592061
DC.subject	fairness
	independence
	inner product search
DC.description	Aoyama K., Amagata D., Fujita S., et al. Simpler is Much Faster: Fair and Independent Inner Product Search. SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval , 2379 (2023); https://doi.org/10.1145/3539618.3592061.
DCTERMS.abstract	The problem of inner product search (IPS) is important in many fields. Although maximum inner product search (MIPS) is often considered, its result is usually skewed and static. Users are hence hard to obtain diverse and/or new items by using the MIPS problem. Motivated by this, we formulate a new problem, namely the fair and independent IPS problem. Given a query, a threshold, and an output size k, this problem randomly samples k items from a set of items such that the inner product of the query and item is not less than the threshold. For each item that satisfies the threshold, this problem is fair, because the probability that such an item is outputted is equal to that for each other item. This fairness can yield diversity and novelty, but this problem faces a computational challenge. Some existing (M)IPS techniques can be employed in this problem, but they require O(n) or o(n) time, where n is the dataset size. To scale well to large datasets, we propose a simple yet efficient algorithm that runs in O(logn + k) expected time. We conduct experiments using real datasets, and the results demonstrate that our algorithm is up to 330 times faster than baselines.
DC.rights	This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
DC.format	92782
citation_title	Simpler is Much Faster: Fair and Independent Inner Product Search
citation_author	Aoyama, Kazuyoshi
	Amagata, Daichi
	Fujita, Sumio
	Hara, Takahiro
citation_publisher	Association for Computing Machinery, Inc
citation_language	英語
citation_date	2023-07-19
citation_journal_title	SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval
citation_firstpage	2379
citation_lastpage	2383
citation_doi	https://doi.org/10.1145/3539618.3592061
citation_public_url	https://hdl.handle.net/11094/92782

Simpler is Much Faster: Fair and Independent Inner Product Search

閲覧可能ファイル

論文情報

論文詳細を表示