学術雑誌論文

学術雑誌論文

text

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

Cardinality Estimation in Inner Product Space

Institute of Electrical and Electronics Engineers Inc.

英語

text

2022-10-01

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

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.

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.

This article is licensed under a Creative Commons Attribution 4.0 International License.

92833

Cardinality Estimation in Inner Product Space

Institute of Electrical and Electronics Engineers Inc.

英語

2022-10-01

IEEE Open Journal of the Computer Society

3

208

216

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

https://hdl.handle.net/11094/92833