1. A computer-based method, comprising: receiving an itinerary query comprising a starting location, an ending location and a duration; identifying a set of trip candidates, from a location-interest graph, comprising: performing a first comparison of the starting location of the itinerary query with at least one of a first starting location of a first trip candidate, a second starting location of a second trip candidate, a third starting location of a third trip candidate or a fourth starting location of a fourth trip candidate; performing a second comparison of the ending location of the itinerary query with at least one of a first ending location of the first trip candidate, a second ending location of the second trip candidate, a third ending location of the third trip candidate or a fourth ending location of the fourth trip candidate; performing a third comparison of the duration of the itinerary query with at least one of: a combination of at least a first travel time associated with the first trip candidate and a first stay time associated with one or more locations associated with the first trip candidate; a combination of at least a second travel time associated with the second trip candidate and a second stay time associated with one or more locations associated with the second trip candidate; a combination of at least a third travel time associated with the third trip candidate and a third stay time associated with one or more locations associated with the third trip candidate; or a combination of at least a fourth travel time associated with the fourth trip candidate and a fourth stay time associated with one or more locations associated with the fourth trip candidate; and including the first trip candidate, the second trip candidate and the third trip candidate, but not the fourth trip candidate, within the set of trip candidates based on the first comparison, the second comparison and the third comparison; identifying: a first threshold difference for the first trip candidate, the first threshold difference comprising a first difference between a desired threshold value and a first value for the first trip candidate; a second threshold difference for the second trip candidate, the second threshold difference comprising a second difference between the desired threshold value and a second value for the second trip candidate; and a third threshold difference for the third trip candidate, the third threshold difference comprising a third difference between the desired threshold value and a third value for the third trip candidate, at least one of the desired threshold value, the first value, the second value or the third threshold value based on one or more trip factors; selecting the first trip candidate and the second trip candidate, but not the third trip candidate, from the set of trip candidates based on the first threshold difference and the second threshold difference corresponding to a desired range of identified threshold differences, and the third threshold difference not corresponding to the desired range of identified threshold differences; ranking the first trip candidate and the second trip candidate based on one or more ranking factors; re-ranking the first trip candidate and the second trip candidate based on one or more historical travel sequences; and providing the re-ranked trip candidates in response to receiving the itinerary query.