5 citations · 7 across the 9 of their papers we have counts for
8 papers · 1 filter
NP-Completeness for the Space-Optimality of Double-Array Tries
Hideo Bannai, Keisuke Goto, Shunsuke Kanda +1
Indexing a set of strings for prefix search or membership queries is a fundamental task with many applications such as information retrieval or database systems. A classic abstract…
Computing NP-hard Repetitiveness Measures via MAX-SAT
Hideo Bannai, Keisuke Goto, Masakazu Ishihata +3
Repetitiveness measures reveal profound characteristics of datasets, and give rise to compressed data structures and algorithms working in compressed space. Alas, the computation o…
Engineering faster double-array Aho-Corasick automata
Shunsuke Kanda, Koichi Akabe, Yusuke Oda
Multiple pattern matching in strings is a fundamental problem in text processing applications such as regular expressions or tokenization. This paper studies efficient implementati…
An Optimal-Time RLBWT Construction in BWT-runs Bounded Space
Takaaki Nishimoto, Shunsuke Kanda, Yasuo Tabei
The compression of highly repetitive strings (i.e., strings with many repetitions) has been a central research topic in string processing, and quite a few compression methods for t…
Dynamic Similarity Search on Integer Sketches
Shunsuke Kanda, Yasuo Tabei
Similarity-preserving hashing is a core technique for fast similarity searches, and it randomly maps data points in a metric space to strings of discrete symbols (i.e., sketches) i…
Rank/Select Queries over Mutable Bitmaps
Giulio Ermanno Pibiri, Shunsuke Kanda
The problem of answering rank/select queries over a bitmap is of utmost importance for many succinct data structures. When the bitmap does not change, many solutions exist in the t…
Succinct Trit-array Trie for Scalable Trajectory Similarity Search
Shunsuke Kanda, Koh Takeuchi, Keisuke Fujii +1
Massive datasets of spatial trajectories representing the mobility of a diversity of moving objects are ubiquitous in research and industry. Similarity search of a large collection…
Dynamic Path-Decomposed Tries
Shunsuke Kanda, Dominik Köppl, Yasuo Tabei +2
A keyword dictionary is an associative array whose keys are strings. Recent applications handling massive keyword dictionaries in main memory have a need for a space-efficient impl…