A computer-implemented method for determining skyline points of interest, comprising: determining a route path at a navigation system, wherein the route path comprises one or more links (820a-g); receiving a request for a skyline query at the navigation system, wherein the skyline query is related to one or more point of interest attributes; in response to the request, the navigation system: determining a plurality of points of interest associated with the one or more links of the route path using a stored relation that associates at least an identifier associated with a link, an identifier associated with a point of interest, a respective distance or a time between the link and the point of interest, and a value for each attribute of the one or more received point of interest attributes; selecting one or more skyline points of interest from the determined plurality of points of interest, wherein a skyline point of interest is a point of interest that is not dominated by other points of interest in the plurality of points of interest with respect to the one or more received point of interest attributes and a respective distance or time attribute based on the said associated distance or time between the link and the point of interest respectively; and producing an indication of the one or more skyline points of interest. determining a route path at a navigation system, wherein the route path comprises one or more links (820a-g); receiving a request for a skyline query at the navigation system, wherein the skyline query is related to one or more point of interest attributes; in response to the request, the navigation system: determining a plurality of points of interest associated with the one or more links of the route path using a stored relation that associates at least an identifier associated with a link, an identifier associated with a point of interest, a respective distance or a time between the link and the point of interest, and a value for each attribute of the one or more received point of interest attributes; selecting one or more skyline points of interest from the determined plurality of points of interest, wherein a skyline point of interest is a point of interest that is not dominated by other points of interest in the plurality of points of interest with respect to the one or more received point of interest attributes and a respective distance or time attribute based on the said associated distance or time between the link and the point of interest respectively; and producing an indication of the one or more skyline points of interest. determining a plurality of points of interest associated with the one or more links of the route path using a stored relation that associates at least an identifier associated with a link, an identifier associated with a point of interest, a respective distance or a time between the link and the point of interest, and a value for each attribute of the one or more received point of interest attributes; selecting one or more skyline points of interest from the determined plurality of points of interest, wherein a skyline point of interest is a point of interest that is not dominated by other points of interest in the plurality of points of interest with respect to the one or more received point of interest attributes and a respective distance or time attribute based on the said associated distance or time between the link and the point of interest respectively; and producing an indication of the one or more skyline points of interest.