Recherche efficace des k plus proches voisins dans les réseaux de transport public

Le transport public joue un rôle essentiel dans l'atténuation de la congestion routière et la réduction des émissions de carbone. La recherche des k plus proches voisins (k NN) dans les réseaux de transport public est un problème fondamental dans les services basés sur la localisation, qui vise à trouver les k objets les plus proches d'un point de requête donné. La méthode traditionnelle, l'algorithme de Dijkstra, a été employée pour résoudre le problème k NN, cependant, elle est notoirement inefficace dans le traitement des requêtes. Alors que d'autres travaux précomputent un index pour accélérer le traitement des requêtes, ils restent cependant lents. De plus, ils ne peuvent pas évoluer vers de grands graphes en raison de leur dépendance à des index de chemin gourmands en ressources. Pour remédier à ces limitations, nous proposons une nouvelle approche basée sur un index qui utilise une structure d'index simple mais efficace pour traiter les requêtes k NN avec une complexité temporelle presque optimale. L'index ne repose pas sur un index de chemin, ce qui le rend efficace à construire et évolutif pour les grands graphes. D'amples expériences ont été menées sur des jeux de données du monde réel pour démontrer l'efficacité et l'évolutivité de notre approche. Les résultats montrent que notre approche surpasse les solutions existantes jusqu'à quatre ordres de grandeur dans le traitement des requêtes et deux ordres de grandeur dans la construction de l'index.