Higher Order TriesSocial Security TrieSocial Security AVL & Red-BlackCompressed Social Security TrieInsertSlide 6Slide 7Slide 8Slide 9Slide 10DeleteSlide 12Slide 13Slide 14Variable Length KeysSlide 16Slide 17Tries With Edge InformationExampleEtc.Slide 21Multibit TriesMultibit Trie ExampleSlide 24Web ResourceSlide 26Higher Order Tries•Key = Social Security Number.441-12-11359 decimal digits.•10-way trie (order 10 trie).0 1 2 3 4 5 6 7 8 9Height <= 10.Social Security Trie•10-way trieHeight <= 10.Search => <= 9 branches on digits plus 1 compare.•100-way trie441-12-1135Height <= 6.Search => <= 5 branches on digits plus 1 compare.Social Security AVL & Red-Black•Red-black treeHeight <= 2log2109 ~ 60.Search => <= 60 compares of 9 digit numbers.•AVL treeHeight <= 1.44log2109 ~ 40.Search => <= 40 compares of 9 digit numbers.•Best binary tree.Height = log2109 ~ 30.Compressed Social Security Trie#ptr0 1 2 3 4 5 6 7 8 9char#•char# = character/digit used for branching.Equivalent to bit# field of compressed binary trie.•#ptr = # of nonnull pointers in the node.InsertInsert 012345678.012345678Insert 015234567.Null pointer fields not shown.2 5012345678 0152345673InsertInsert 015231671.2 5012345678 0152345673InsertInsert 079864231.2 501234567801523456731 46015231671InsertInsert 012345618.2 501234567801523456731 460152316711 72079864231InsertInsert 011917352.1 782 501234567801523456731 4601523167120798642311 7012345618Insert1 782 50123456780152345671 4601523167120798642311 701234561813011917352Delete1 782 50123456780152345671 4601523167120798642311 701234561813011917352Delete 011917352.Delete1 782 50123456780152345671 4601523167120798642311 70123456183Delete 012345678.Delete1 72 50152345671 460152316712079864231012345618Delete 015231671.3Delete1 72 501523456720798642310123456183Variable Length KeysInsert 0123.2 501234567801523456731 46015231671Problem arises only when one key is a (proper) prefix of another.Variable Length KeysInsert 0123.2 501234567801523456731 46015231671Add a special end of key character (#) to each key to eliminate this problem.Variable Length KeysEnd of key character (#) not shown.Insert 0123.2 5012345678 01523456731 4601523167101234 #5Tries With Edge Information•Add a new field (element) to each branch node.•New field points to any one of the element nodes in the subtree. •Use this pointer on way down to figure out skipped-over characters.Exampleelement field shown in blue.2 5012345678 01523456731 4601523167101234 #5Etc.•Expected height of an order m trie is ~logmn.•Limit height to h (say 6). Level h branch nodes point to buckets that employ some other search structure for all keys in subtrie.Etc.•Switch from trie scheme to simple array when number of pairs in subtrie becomes <= s (say s = 6).Expected # of branch nodes for an order m trie when n is large and m and s are small is n/(s ln m).•Sample digits from right to left (instead of from left to right) or using a pseudorandom number generator so as to reduce trie height.Multibit Tries•Variant of binary trie in which the number of bits (stride) used for branching may vary from node to node.•Proposed for Internet router applications.Variable length prefixes.Longest prefix match.•Limit height by choosing node strides.Root stride = 32 => height = 1.Strides of 16, 8, and 8 for levels 1, 2, and 3 => only 3 levels.Multibit Trie Example010 nullnull 011 10 11000S =1S =2S =11000 00101 10 11Multibit Tries•Node whose stride is s uses s bits for branching.Node has 2s children and 2s element/prefix fields.Prefixes that end at a node are stored in that node.Short prefixes are expanded to length represented by node.When root stride is 3, prefixes whose length is < 3 are expanded to length 3.P = 00* expands to P0 = 000* and P1 = 001*.If Q = 000* already exists P0 is eliminated because Q represents a longer match for any destination.Web Resource•See Web writeup for additional applications of tries. Prefix search. Automatic command (or phone number or URL) completion. LZW compression.Web Resource•See Web writeup for alternative node structures for tries. ArrayChain Binary search tree Hash