Alibaba Group Holding Limited
AUGMENTATION TO THE SUCCINCT TRIE FOR MULTI-SEGMENT KEYS

Abstract:

Mechanisms for constructing and querying a database are described. Constructing the database includes accessing the database comprising multi-component data and constructing an augmented succinct trie (AST) as an index of the database. The database includes sorted data blocks. Construction of the AST is based on the multi-component data. The AST includes indications of boundaries of the data components of the multi-component data. Querying the database includes accessing a key comprising multiple data components and augmenting the key data with data component boundary information. The AST is searched using the augmented key and a search result provided as a value corresponding to the key in the database.