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 (52, 55, 59, 60) of said plurality objects, for each object of said at least one object (52, 55, 59, 60) associated with said root node (11-13; 71-73), respectively determining a distance (65, 66) between said query object and said object, said distance (65, 66) 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 (65, 66), 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 (52, 55, 59, 60) of said plurality objects, for each object of said at least one object (52, 55, 59, 60) associated with said root node (11-13; 71-73), respectively determining a distance (65, 66) between said query object and said object, said distance (65, 66) 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 (52, 55, 59, 60) of said plurality objects, for each object of said at least one object (52, 55, 59, 60) associated with said root node (11-13; 71-73), respectively determining a distance (65, 66) between said query object and said object, said distance (65, 66) 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 (65, 66), 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.