Database Reference
In-Depth Information
algorithm was later improved by Chan et al. [15]. A cache conscious
extension of the same algorithm for external memory applications was
proposed by Hon et al. [37].
The detailed expansion based trie algorithm for incrementally com-
puting the edit distance of every prefix of a query string was indepen-
dently proposed by Ji et al. [38] and Chaudhuri and Kaushik [20]. These
algorithms were tailored specifically for computing edit distance as a
user is typing a query one letter at a time. The main difference from
the dictionary reporting problem is that the whole query string is not
known in advance, hence certain optimizations based on knowing the
query are not applicable. In addition, these algorithms reuse previous
computation to eciently retrieve the new answers, after a new letter
is typed. Conceptually the two algorithms are the same. In practice
they differ in the order that nodes are added in the active nodes list.
Chaudhuri and Kaushik [20] need to process every node before all its
children in order to maintain correctness (which necessitates maintain-
ing a queue, resulting in some additional space). Ji et al. [38] only need
to maintain a hash table, since the order in which nodes are processed
is not important. The B-tree based algorithms were proposed by Zhang
et al. [78].
Search WWH ::




Custom Search