mapbox / mapbox/nepomuk

Improve Data Structures for finding Departures

Open
#92 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Backend Feature Request
Dominant language
C++
Stars
24
Forks
7
PR merge metrics
No merged PRs in 30d

Description

The data structures that allow finding departures can probably be improved. The goal is a data structure that stores all stops and their respective departures on a line. The look-ups should support the following operations:

### Line + Stop -> localID

For every line, and every stop, we should get the position of the stop along the line. This look-up should be possible to do in **O(1)** (via hashing), but we might be able to offer something better. It could be that lines in general are short enough so that _linear scan remains an option_.

### localID + Time -> Time

For every local ID and a arrival time, we want to be able to find the next departure of the line from the stop. The look-up itself probably requires **logarithmic** time + x, if we do a binary search over all departures.

### localID + Time -> {stops, duration}

When we know the actual departure for a localID, we should be able to collect all stops + durations along the line (so that search algorithms) can reach the next stops on a line. This look-up should also be possible in **O(1)**, if we store appropriate information with the previous two look-ups which are required to access the line table anyhow.

### Usage

The usage of this data structure should hide all access of the first two look-ups and simply allow an access via `stop-id` and `arrival time` to `{stops,durations,departure_time}`, which is a trip that leaves at `departure_time` and can reach `stops` in offsets stored in `durations`.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating the existing data structures and departure lookup entry points in the C++ router, then compare them with the three requested lookup operations. Done means providing a line-and-stop lookup, next-departure lookup, and trip stop/duration access behind the proposed stop-id and arrival-time interface, with the stated complexity targets validated.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
backend
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.