Trie is an ordered tree data structure which stores words in it so that users can search a word or a prefix quickly. Time complexity for adding a word to a Trie is $O(l)$, and for searching a word or a prefix is $O(l)$ too ($l$ is the length of the word or the prefix being added or searched). So it’s why we prefer Trie rather than Set and Hash Table in some situations, such as Dynamic Set, Associative Array and a predictive text or autocomplete Dictionary.

Read More
  • page 1 of 1
Author's picture

Haiyang Shi

I am a Ph.D. student in Computer Science and Engineering at The Ohio State University (OSU), advised by Dr. Xiaoyi Lu. My professional interests involve high-performance interconnects and protocols, erasure coding, in-network computing, and distributed systems. In my ongoing and recent projects, which are mainly developed in C++ and Java, I focus on implementing RDMA (Remote Direct Memory Access)-based communication protocols, optimizing I/O performance by exploiting RDMA for data transmission, enabling distributed systems to leverage heterogeneous hardware-optimized erasure coders in parallel, and designing coherent in-network EC to gain better overlapping and parallelism on HPC clusters. In the meantime, I have participated in characterizing deep learning over big data stacks recently, and have understandings of deep learning training on distributed systems and modern data centers. Prior to graduate school, I worked as a Software Engineer at MiningLamp and Weibo, China. I finished my Bachelor’s degree at Tianjin University, China.

Graduate Research Associate

Columbus, OH