Patent ID: 7689621

Claim:
A computer-implemented method of operating a navigation system, said method comprising: using a geographic database stored on a computer readable storage medium containing data that represents geographic features, wherein said database includes a single indexing structure with three dimensions, wherein said indexing structure is a k-d tree comprising a root node, intermediate nodes and leaf nodes, wherein each node is part of a parent-child relationship wherein each parent node includes control information from which one of at least two child nodes associated with the parent node are distinguishable based on a search key, wherein a first dimension of said three dimensions includes latitude boundary information, wherein a second dimension of said three dimensions includes longitude boundary information, wherein said latitude boundary information and said longitude boundary information define a bounded area represented by a maximum latitude, a maximum longitude, a minimum latitude and a minimum longitude, wherein a third dimension of said three dimensions includes rank information, wherein each of said geographic features have an associated rank information, wherein said rank information has at least two levels, a first level of rank is associated with the geographic features of greater importance and a second level of rank is associated with geographic features of lesser importance, searching said geographic database stored on the computer readable storage medium for data representing a geographic feature using a latitude value, a longitude value and a rank value, wherein said search uses said first and second dimensions of said single indexing structure to identify the bounded area in which the latitude value and longitude value falls within, wherein said search uses said third dimension of said single indexing structure to identify said level of rank corresponding to said rank value.