Cardinality Estimation in Inner Product Space

Hirata, Kohei; Amagata, Daichi; Hara, Takahiro

doi:https://doi.org/10.1109/OJCS.2022.3215206

Cardinality Estimation in Inner Product Space

Hirata, Kohei; Amagata, Daichi; Hara, Takahiro

IEEE Open Journal of the Computer Society, 2022, 3, 208-216

Number of Access:598（2025-08-15 10:59 Counts）

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

Link to primary information

File	Format	Terms of use	Size	Views	Date.Available	Description	information
IEEEOpenJComputSoc_3_208	pdf	None	803 KB	57	2023.10.24

Creative Commons : Attribution

Item Information

Output File Export EndNote Basic Export Mendeley

Title	Cardinality Estimation in Inner Product Space
Creator	CreatorName Hirata, Kohei
	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	Cardinality estimation
	high-dimensional data
	inner product search
Description	Hirata K., Amagata D., Hara T.. Cardinality Estimation in Inner Product Space. IEEE Open Journal of the Computer Society 3, 208 (2022); https://doi.org/10.1109/OJCS.2022.3215206.
Abstract	This article addresses the problem of cardinality estimation in inner product spaces. Given a set of high-dimensional vectors, a query, and a threshold, this problem estimates the number of vectors such that their inner products with the query are not less than the threshold. This is an important problem for recent machine-learning applications that maintain objects, such as users and items, by using matrices. The important requirements for solutions of this problem are high efficiency and accuracy. To satisfy these requirements, we propose a sampling-based algorithm. We build trees of vectors via transformation to a Euclidean space and dimensionality reduction in a pre-processing phase. Then our algorithm samples vectors existing in the nodes that intersect with a search range on one of the trees. Our algorithm is surprisingly simple, but it is theoretically and practically fast and effective. We conduct extensive experiments on real datasets, and the results demonstrate that our algorithm shows superior performance compared with existing techniques.
Publisher	Institute of Electrical and Electronics Engineers Inc.
Source Title	IEEE Open Journal of the Computer Society
Volume (Issue)	3
Page	208-216
Date of Issued	2022-10-01
Language	English
Handle URL	https://hdl.handle.net/11094/92833
eISSN	26441268
Relation.isIdenticalTo	DOI (Publisher Version) https://doi.org/10.1109/OJCS.2022.3215206
Access Rights	open access
CopyRight	This article is licensed under a Creative Commons Attribution 4.0 International License.
oaire:version	Version of Record
Category	学術雑誌論文 Journal Article

Resource Type	journal article
Local Type	Journal Article
DCMI Type	Text
DCTERMS.bibliographicCitation	IEEE Open Journal of the Computer Society. 2022, 3, p. 208-216
DC.title	Cardinality Estimation in Inner Product Space
DC.creator	Hirata, Kohei
	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	2022-10-01
DC.identifier	https://doi.org/10.1109/OJCS.2022.3215206
DC.subject	Cardinality estimation
	high-dimensional data
	inner product search
DC.description	Hirata K., Amagata D., Hara T.. Cardinality Estimation in Inner Product Space. IEEE Open Journal of the Computer Society 3, 208 (2022); https://doi.org/10.1109/OJCS.2022.3215206.
DCTERMS.abstract	This article addresses the problem of cardinality estimation in inner product spaces. Given a set of high-dimensional vectors, a query, and a threshold, this problem estimates the number of vectors such that their inner products with the query are not less than the threshold. This is an important problem for recent machine-learning applications that maintain objects, such as users and items, by using matrices. The important requirements for solutions of this problem are high efficiency and accuracy. To satisfy these requirements, we propose a sampling-based algorithm. We build trees of vectors via transformation to a Euclidean space and dimensionality reduction in a pre-processing phase. Then our algorithm samples vectors existing in the nodes that intersect with a search range on one of the trees. Our algorithm is surprisingly simple, but it is theoretically and practically fast and effective. We conduct extensive experiments on real datasets, and the results demonstrate that our algorithm shows superior performance compared with existing techniques.
DC.rights	This article is licensed under a Creative Commons Attribution 4.0 International License.
DC.format	92833
citation_title	Cardinality Estimation in Inner Product Space
citation_author	Hirata, Kohei
	Amagata, Daichi
	Hara, Takahiro
citation_publisher	Institute of Electrical and Electronics Engineers Inc.
citation_language	English
citation_date	2022-10-01
citation_journal_title	IEEE Open Journal of the Computer Society
citation_volume	3
citation_firstpage	208
citation_lastpage	216
citation_doi	https://doi.org/10.1109/OJCS.2022.3215206
citation_public_url	https://hdl.handle.net/11094/92833

Cardinality Estimation in Inner Product Space

Link to primary information

Item Information

Show details