Ideas about clustering on the graph database

[LucaFalasca]

Idee di design per la rappresentazione dei dati e il clustering nel database a grafo:

Rappresentiamo ogni nodo con la prenotazione richiesta (sostanzialmente la coppia (fermata inziale, fermata finale)). Ogni volta che andiamo ad inserire un nuovo nodo andiamo a verificare quali nodi hanno almeno uno tra fermata iniziale o fermata finale vicino ad una fermata inziale o finale di un altro nodo. La vicinanza verrà definità in base alla distanza tra le coordinate senza andare a usare le api, in pratica si traccia un cerchio intorno alle coordinate e si prendono tutte le fermate che ci cadono dentro.

In questo esempio i due marker rosa rappresentano un nodo prenotazione e quelli verdi un altro. Essi saranno considerati "compatibili spazialmente" perchè l'arrivo del nodo rosa è vicino alla partenza del nodo verde

Una volta che si hanno a disposizioni questi nodi si va a controllare se sono anche "compatibili temporalmente". Quindi si va a verificare se la distanza in termini di tempo tramite le api di Snap4City e si verifica se è compatibile rispetto alla tempo indicato sulla prenotazione. Questa verifica va fatta molto a grana larga in modo da non escludere troppo facilemente dei tempi che potrebbero essere compatibili o no in base al percorso che potrebbe fare l'autobus, però allo stesso tempo escludere quelli sicuramente impossibili (tipo quelli che hanno un tempo minore del tempo di percorrena oppure una distanza di tempo di prenotazione di diverse ore).

Se i due nodi sono compatibili anche temporalmente allora essi verranno collegati sul grafo e clusterizzati. In questo modo dovrebbe essere più semplice scegliere i nodi più papabili per l'algoritmo.

[StefanAdrianHuma]

Guarda, perfetto! Le modifiche che ho apportato al database le ho fatte proprio in vista di questa cosa avendovi gia sentito parlare dell'aprossimazione spaziale tra fermate. Tanto per dare un numero su cui iniziare quanto considerate accettabile come raggio della circonferenza (1Km , 500m) considerate che quello è una distanza che l'utente fa a piedi.

[LucaFalasca]

Pensavo di definire in maniera più specifica come avviene il potenziale collegamento tra nodi (potenziale perché l'effettivo collegamento dipenderà anche dalla compatibilità temporale). Casistiche:

• Se il nodo 1 ha la fermata di arrivo compatibile spazialmente con quella di partenza del nodo 2 allora verrà tracciato un collegamento dal nodo 1 al nodo 2
• Se il nodo 1 ha la fermata di partenza compatibile con quella di arrivo del nodo 2 allora verrà tracciato un collegamento dal nodo 2 al nodo 1 (in pratica stessa casistica di prima ma al contrario)
• se il nodo 1 e il nodo 2 hanno le partenze compatibili allora verrà tracciata una doppia freccia in entrambe le direzioni
• se il nodo 1 e il nodo 2 hanno gli arrivi compatibili il nodo non sarà considerato compatibile e non verrà tracciato nessun collegamento tra i due nodi

Ogni nodo rappresenta sempre una prenotazione e quindi sarà collegato a due fermate. Queste due fermate potrebbero essere considerate come altri nodi di altro tipo a cui ogni nodo prenotazione è collegato. In questo modo ci sono due tipologie di nodi:

• un tipo che riguarda le fermate (in modo di non avere dati duplicati nel caso in cui due fermate siano considerate da prenotazioni diverse
• un altro tipo che riguarda la singola prenotazione dell'utente che sarà collegato a due nodi fermate

@StefanAdrianHuma fammi sapere se questa rappresentazione che ho pensato è compatibile con il db a grafo e in generale fatemi sapere che ne pensate @matteo-conti-97 @StefanAdrianHuma

[LucaFalasca]

Tanto per dare un numero su cui iniziare quanto considerate accettabile come raggio della circonferenza (1Km , 500m) considerate che quello è una distanza che l'utente fa a piedi.

Secondo me si può anche aumentare il raggio di più perché altrimenti si rischia di isolare troppo zone sperdute e va a finire che non fanno mai parte di nessun cluster. Un altro problema è che andremo a stimare questo raggio attraverso le coordinate delle fermate e non tramite la loro distanza effettiva su strada perché altrimenti per ogni distanza tra coppie di fermate dovremmo fare una richiesta diversa alle api di snap4city. A meno che non vogliamo "clonare" il database delle fermate di snap4city sul nostro a grafo con le relative distanze perché se no dovremmo fare N richieste (o 2N nel caso in cui vogliamo calcolare sia l'andata che il ritorno) alle api di snap4city per ogni nodo nuovo che entra nel db, considerato N come il numero di nodi già nel database

[LucaFalasca]

Guarda, perfetto! Le modifiche che ho apportato al database le ho fatte proprio in vista di questa cosa avendovi gia sentito parlare dell'aprossimazione spaziale tra fermate. Tanto per dare un numero su cui iniziare quanto considerate accettabile come raggio della circonferenza (1Km , 500m) considerate che quello è una distanza che l'utente fa a piedi.

Però forse tu hai capito male il discorso fatto ora che ci penso. Perché mi sa che tu intendi con approssimazione spaziale che due fermate sono intercambiabili per proporre all'utente di cambiare nel caso in cui ci sia un'altra fermata con già un percorso o cose del genere. Invece io con compatibile spazialmente intendo che due nodi vengono messi nello stesso cluster, cioè è un modo per fare il filtraggio dei nodi per poi proporli all'algoritmo.

Per fare quello che dici tu potremmo implementare un altro tipo di collegamento che indica la "intercambiabilità" tra due nodi e questo magari possiamo deciderlo entro un altro raggio che potrebbe essere però di massimo 100-200 metri secondo me. In questo caso ci vuole un doppio collegamento (o un collegamento non orientato, ma non so se è disponibile sul db a grafo) tra 2 nodi fermate

[LucaFalasca]

Tra l'altro stavo pensando che con questo approccio andiamo a fare clustering direttamente, quindi non serve più avere un microservizio se si occupa di questo

[LucaFalasca]

Compatibilità temporale Dati:

• X_i = ora di partenza del nodo i
• Y_i = ora di arrivo del nodo i
• D_ij = tempo di percorrenza dal nodo i al nodo j
• offset = indica un margine di tempo accettabile extra per D_ij (io metterei 15 minuti)

Compatibilità

• Se nodo1 ha l'arrivo all'ora Y_1 e il nodo2 ha la partenza all'ora X_2, saranno compatibili se D_12 < X_2 - Y_1 < D_12 + offest
• Se nodo1 ha la partenza all'ora X_1 e il nodo2 ha la partenza all'ora X_2, saranno compatibili se D_12 < |X_2 - X_1| < D_12 + offest