It's for a public transit app, where the user can type the departure and arrival stations and tap on the search button. The departure and arrival are AutoCompleteTextViews. When you start typing, it shows suggestions, so you don't have to type the whole station name.
The suggestions are intelligent - they are sorted based on:
- The station's distance from where you are located. This is only for stops within 1 km radius.
- Usage history - how many time have you used this station as arrival / departure.
- The station's importance - is this a big metro station or a small bus stop nobody uses?
For every station, I calculate an evaluation based on these parameters. The stations are then sorted by their evaluation. The sorted list is then filtered by the string typed by the user. One feature is that when the user types "stat", the suggestions include not only "station example" but also "example station" (i.e. you can start typing a middle word of the station name).
Right now, you have to select a city and you can search only within that city. The stations are loaded into memory from a .java file and sorted. Every time your location changes, the stations are sorted again. The biggest city has less than 10,000 stations.
For quite a long time, I've been planning to implement search within the whole country - you won't have to search within just one city. The problem is, that there are almost 100,000 stations. I don't want to make an update that would make anything noticably slower, which means that
- The app should start within 1 - 2 s.
- When you type something, the suggestions should update within 30 ms.
- When the location updates, the suggestions should update within 300 ms (the location updates very soon after start and the top arrival & departure stations are prefilled, so the user can often just click on the search button after start, without typing anything).
An additional parameter needs to be used for sorting - the city where the user is located. If I'm in one city, I'm mostly interested in that city's stations.
Right now, I'm half way through an implementation that uses a binary file with list of stations, that is loaded into memory after launch. This implementation contains some ugly microoptimizations (whenever you type, the app needs to loop through 100,000 stations within ~30ms). It sort of works, but I was thinking that a database based solution would make things simpler. So right now I'm exploring whether that's feasible.
This is getting long, so just a quick summary of how the database based solution could be implemented. The current city's stations would be loaded into memory (that's why I need to load 10,000 rows into memory). The previously used stations too. These in-memory stations would be sorted. When the user types something, the in-memory list is filtered and a db query is performed to filter through the remaining stations: "SELECT * FROM stations WHERE name LIKE 'abc%'". The results are merged and shown as suggestions.
The SELECT query is quite fast, because the database does binary search internaly. Any query that needs to go through all of the rows is out of the question.