Working Notes on Tries

T. H. Merrett

We Trie Harder

The Pointerless Representation for Tries PDF slides 78KB

Aldat and Trie techniques for OLAP datacubes PostScript slides 150KB

Tries: a Data Structure for Secondary Storage PostScript slides 4MB

Tries have been mainly used for text data, but have two tremendous advantages over other structures for all kinds of data. First, they compress data by up to a factor of 1 - 2/h, where h is the height of the trie. Second, they directly support variable resolution, so that much of the stored data that is not relevant to a query or operation can be ignored from early in the processing.

This talk will introduce tries and the properties of compression and variable resolution. We will consider how tries are represented and searched. We look at applications to text and to spatial data, in particular. We also look at read-write concurrency for dynamic tries, and at the so-called "curse of dimensionality" for high-dimensional problems in OLAP and feature vector searching.

Overview and simple coding guide PostScript notes 350KB

T. H. Merrett, H. Shang, X. Zhao, 1996 Database Structures, Based on Tries, for Text, Spatial, and General Data International Symposium on Cooperative Database Systems for Advanced Applications, Kyoto, Dec. 5--7, 1996, pp. 316--24. PostScript paper 4MB

H. Shang & T. H. Merrett, 1996 Tries for Approximate String Matching IEEE Trans. on Knowledge and Data Engineering, special issue on Digital Libraries, Nabil R. Adam, ed., 8 4(August, 1996) pp. 540--7. PostScript paper 300KB

Heping Shang Trie Methods for Text and Spatial Data on Secondary Storage LaTeX source | PostScript
Ph.D. Thesis, McGill University, January 1995.