Succinct storage methods improve search trees for complex networks
Succinct Representation of Search Trees on Trees
Data Structures and Algorithms
Summary
Finding a specific point in a complicated network can be tricky and slow without the right tools. This paper looks at ways to store special search structures, called search trees on trees, in a very compact form so they take up less space. The researchers made sure these compact versions still let you search quickly, and that building them doesn’t take too long. Their methods work for both general cases and a more specialized version called Steiner-closed search trees.
What this means in practice
- •For network engineers: Store and traverse large network topologies efficiently using compact search trees to speed up routing and queries.
- •For database system developers: Implement space-saving search tree indices that maintain fast query times for hierarchical or graph-structured data.
Authors
Seungbum Jo, Nodari Sitchinava
Abstract
A search tree on trees (STT) is a data structure for performing a search for a target vertex in a reference tree. A standard binary search tree is a special case of an STT, where the reference tree is a path of totally ordered elements. In this paper, we study the problem of succinct representation of STTs. We consider two cases: (1) general search trees on trees, and (2) Steiner-closed search trees on trees [Bose et al. TALG 2023]. For both cases, we present representations that can be constructed in polynomial time and achieve optimal space up to the lower-order additive terms. We also present data structures for supporting fast traversals of both general and Steiner-closed STTs. For general STTs our data structure still takes optimal space up to lower-order additive terms.