Sorry, you need to enable JavaScript to visit this website.

facebooktwittermailshare

c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches

Abstract: 

Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ, a keyword dictionary is a data structure built on K that provides locate, prefix search, and update operations on K. Under the assumption that α = w / lg σ characters fit into a single machine word w, we propose a keyword dictionary that represents K in n lg σ + O(k lg n) bits of space, supporting all operations in O(m / α + lg α) expected time on an input string of length m in the word RAM model. This data structure is underlined with an exhaustive practical evaluation, highlighting the practical usefulness of the proposed data structure, especially for prefix searches - one of the most elementary keyword dictionary operations.

up
0 users have voted:

Paper Details

Authors:
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Submitted On:
31 March 2020 - 1:42am
Short Link:
Type:
Presentation Slides
Event:
Presenter's Name:
Kazuya Tsuruta and Dominik Köppl
Session:
Session 8
Document Year:
2020
Cite

Document Files

Video Presentation

Slides

(108)

Keywords

Additional Categories

Subscribe

[1] Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, "c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5049. Accessed: Aug. 10, 2020.
@article{5049-20,
url = {http://sigport.org/5049},
author = {Kazuya Tsuruta; Dominik Köppl; Shunsuke Kanda; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda },
publisher = {IEEE SigPort},
title = {c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches},
year = {2020} }
TY - EJOUR
T1 - c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
AU - Kazuya Tsuruta; Dominik Köppl; Shunsuke Kanda; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5049
ER -
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. (2020). c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches. IEEE SigPort. http://sigport.org/5049
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, 2020. c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches. Available at: http://sigport.org/5049.
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. (2020). "c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches." Web.
1. Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5049