Method of searching a data base, navigation device and method of generating an index structure

A method of performing a similarity search in a navigation device data base uses a metric index structure. The index structure includes a plurality of nodes. When a query object (51) is received, a node of the index structure which is associated with at least one object (52, 55, 59, 60) is accessed. A distance (65, 66) between the query object (51) and the at least one object (52, 55, 59, 60)is determined in accordance with a distance metric. Based on the determined distance, another node of the index structure is selectively accessed.