Archive for the 'algorithms' Category

algorithms review : tries | take #1

July 29, 2010

http://en.wikipedia.org/wiki/Trie

  • Tries represent prefix trees
  • String search in O(log(n)) is naturally obtained by adding strings to trie
  • Common case for key-value stores is “get all keys by prefix” – Trie is a natural way to achieve this. Can this be mapped to key-value store ? Indeed – we map each tree node to a entry in hashmap and store keys representing child nodes in that key’s content.
  • HashTrie – popular extension of key-value stores -> update is O(len(key)), retrieval is O(len(key)). The main problem is due to the fact that we need to update key *content* in order to maintain the tree – which makes ConcurrentHashTree relatively complex to design
  • How to iterate HashTrie ? – would require having a master-key that would act as top-level node and contain keys of all first-level child keys
  • SortedHashTrie ?