Author name cluster

Yusuke Matsui

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

1 author row

TMLR Journal 2025 Journal Article

PCF Learned Sort: a Learning Augmented Sort Algorithm with $\mathcal{O}(n \log\log n)$ Expected Complexity

Atsuki Sato
Yusuke Matsui

Sorting is one of the most fundamental algorithms in computer science. Recently, Learned Sorts, which use machine learning to improve sorting speed, have attracted attention. While existing studies show that Learned Sort is empirically faster than classical sorting algorithms, they do not provide theoretical guarantees about its computational complexity. We propose Piecewise Constant Function (PCF) Learned Sort, a theoretically guaranteed Learned Sort algorithm. We prove that the expected complexity of PCF Learned Sort is $\mathcal{O}(n \log \log n)$ under mild assumptions on the data distribution. We also confirm empirically that PCF Learned Sort has a computational complexity of $\mathcal{O}(n \log \log n)$ on both synthetic and real datasets. This is the first study to theoretically support the empirical success of Learned Sort, and provides evidence for why Learned Sort is fast.

PDF Details

NeurIPS Conference 2023 Conference Paper

Fast Partitioned Learned Bloom Filter

Atsuki Sato
Yusuke Matsui

A Bloom filter is a memory-efficient data structure for approximate membership queries used in numerous fields of computer science. Recently, learned Bloom filters that achieve better memory efficiency using machine learning models have attracted attention. One such filter, the partitioned learned Bloom filter (PLBF), achieves excellent memory efficiency. However, PLBF requires a $\mathcal{O}(N^3k)$ time complexity to construct the data structure, where $N$ and $k$ are the hyperparameters of PLBF. One can improve memory efficiency by increasing $N$, but the construction time becomes extremely long. Thus, we propose two methods that can reduce the construction time while maintaining the memory efficiency of PLBF. First, we propose fast PLBF, which can construct the same data structure as PLBF with a smaller time complexity $\mathcal{O}(N^2k)$. Second, we propose fast PLBF++, which can construct the data structure with even smaller time complexity $\mathcal{O}(Nk\log N + Nk^2)$. Fast PLBF++ does not necessarily construct the same data structure as PLBF. Still, it is almost as memory efficient as PLBF, and it is proved that fast PLBF++ has the same data structure as PLBF when the distribution satisfies a certain constraint. Our experimental results from real-world datasets show that (i) fast PLBF and fast PLBF++ can construct the data structure up to 233 and 761 times faster than PLBF, (ii) fast PLBF can achieve the same memory efficiency as PLBF, and (iii) fast PLBF++ can achieve almost the same memory efficiency as PLBF. The codes are available at [this https URL](https: //github. com/atsukisato/FastPLBF).

PDF Details

AAAI Conference 2021 Conference Paper

Towards Fully Automated Manga Translation

Ryota Hinami
Shonosuke Ishiwatari
Kazuhiko Yasuda
Yusuke Matsui

We tackle the problem of machine translation (MT) of manga, Japanese comics. Manga translation involves two important problems in MT: context-aware and multimodal translation. Since text and images are mixed up in an unstructured fashion in manga, obtaining context from the image is essential for its translation. However, it is still an open problem how to extract context from images and integrate into MT models. In addition, corpus and benchmarks to train and evaluate such models are currently unavailable. In this paper, we make the following four contributions that establish the foundation of manga translation research. First, we propose a multimodal context-aware translation framework. We are the first to incorporate context information obtained from manga images. It enables us to translate texts in speech bubbles that cannot be translated without using context information (e. g. , texts in other speech bubbles, gender of speakers, etc.). Second, for training the model, we propose the approach to automatic corpus construction from pairs of original manga and their translations, by which a large parallel corpus can be constructed without any manual labeling. Third, we created a new benchmark to evaluate manga translation. Finally, on top of our proposed methods, we devised a first comprehensive system for fully automated manga translation.

PDF Details

AAAI Conference 2019 Conference Paper

Efficient Image Retrieval via Decoupling Diffusion into Online and Offline Processing

Fan Yang
Ryota Hinami
Yusuke Matsui
Steven Ly
Shin’ichi Satoh

Diffusion is commonly used as a ranking or re-ranking method in retrieval tasks to achieve higher retrieval performance, and has attracted lots of attention in recent years. A downside to diffusion is that it performs slowly in comparison to the naive k-NN search, which causes a non-trivial online computational cost on large datasets. To overcome this weakness, we propose a novel diffusion technique in this paper. In our work, instead of applying diffusion to the query, we precompute the diffusion results of each element in the database, making the online search a simple linear combination on top of the k-NN search process. Our proposed method becomes 10∼ times faster in terms of online search speed. Moreover, we propose to use late truncation instead of early truncation in previous works to achieve better retrieval performance.

PDF Details