A method of performing a similarity search in a navigation device data base using a metric index structure (10; 70) with a tree form, said data base including a plurality of text strings as objects, said metric index structure (10; 70) including a plurality of nodes (11-17; 71-75) with some of the nodes being directory nodes including pointers to other nodes and with at least some of the other nodes being leaf nodes not including a pointer to other nodes; wherein each node is associated with one or more objects; and wherein the objects are allocated to the nodes according to a distance metric that only depends on the relative distance between the objects within the nodes, said method comprising: receiving a text string as query object , said metric index structure (10; 70) is stored in a storage device of said navigation device ; and said method further comprises: accessing the root node (11-13; 71-73) of said index structure (10; 70) which is associated with at least one object of said plurality objects, for each object of said at least one object associated with said root node (11-13; 71-73), respectively determining a distance between said query object and said object, said distance being respectively determined in accordance with the distance metric, and selectively accessing another node (12-17; 72-75) of said index structure (10; 70) based on the distance between the query object and the object included in the accessed node, wherein objects are selectively pruned from said similarity search based on said determined distances , wherein when a leaf node is accessed, the distance between the object O j in the leaf node and the query object Q is determined only if d Q ; P O j − d O j ; P O j ≤ R | where P(Oj) is the parent of the leaf node in which object Oj is located d( , ) being the distance, R being a fixed search radius, output as a result of the search, the objects found in the search of the index structure which have a distance from the query object which is less than a predetermined threshold. receiving a text string as query object , said metric index structure (10; 70) is stored in a storage device of said navigation device ; and said method further comprises: accessing the root node (11-13; 71-73) of said index structure (10; 70) which is associated with at least one object of said plurality objects, for each object of said at least one object associated with said root node (11-13; 71-73), respectively determining a distance between said query object and said object, said distance being respectively determined in accordance with the distance metric, and selectively accessing another node (12-17; 72-75) of said index structure (10; 70) based on the distance between the query object and the object included in the accessed node, accessing the root node (11-13; 71-73) of said index structure (10; 70) which is associated with at least one object of said plurality objects, for each object of said at least one object associated with said root node (11-13; 71-73), respectively determining a distance between said query object and said object, said distance being respectively determined in accordance with the distance metric, and selectively accessing another node (12-17; 72-75) of said index structure (10; 70) based on the distance between the query object and the object included in the accessed node, wherein objects are selectively pruned from said similarity search based on said determined distances , wherein when a leaf node is accessed, the distance between the object O j in the leaf node and the query object Q is determined only if d Q ; P O j − d O j ; P O j ≤ R | where P(Oj) is the parent of the leaf node in which object Oj is located d( , ) being the distance, R being a fixed search radius, output as a result of the search, the objects found in the search of the index structure which have a distance from the query object which is less than a predetermined threshold. <EOS>