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

Number of Access:813（2025-08-15 06:45 Counts）

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

Link to primary information 

File Format Terms of use Size Views Date.Available Description information
SIGIR-ProcIntACMSIGIRConfResDevInfRetr_2379 pdf None 1.06 MB 152 2023.10.17  
Creative Commons : Attribution - NonCommercial

Item Information

Output File Export EndNote Basic Export Mendeley

Title
Simpler is Much Faster: Fair and Independent Inner Product Search
Creator
CreatorName
Aoyama, Kazuyoshi
NRID
1000040770649 1000040770649
researchmap permalink
amgt amgt
Scopus Author ID
55811167300 55811167300
CreatorName
Amagata, Daichi
CreatorName
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
CreatorName
Hara, Takahiro
Subject
fairness
independence
inner product search
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.
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.
Publisher
Association for Computing Machinery, Inc
Source Title
SIGIR 2023 - Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval
Page
2379-2383
Date of Issued
2023-07-19
Language
English
Handle URL
https://hdl.handle.net/11094/92782
Relation.isIdenticalTo
DOI (Publisher Version)
https://doi.org/10.1145/3539618.3592061
Access Rights
open access
CopyRight
This article is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
oaire:version
Version of Record
Category
会議発表論文 Conference Paper