A prototype for suggesting users other users who follow similar paths in the city.
This prototype is based on an Android application (app) that periodically sends the user's location and other information to a server. This server runs two services: one that is listening to HTTP requests for database insertions (database-service) and another one that processes users' paths, clusters them in different groups, and notifies users about the existence of other users sharing similar paths in the city. The rationale behind this approach, is that people doing the same path (for example, from home to work) have a high chance of having a connection in real-life. Thus, they could probably benefit of meeting each other, for example for car sharing. This could also be a new way of providing new contact suggestions for social networks. Instead of running the protype on different users it is possible to generate synthetic but still valid data for hundreds users. The prototype includes a Java program (paths-generator) for this task.
The repository includes the following:
-
paths-generator. A Java program to generate synthetic users' paths in a city. Given a graph G=(V, E) where V is the set of vertices (intersections in streets) and E the edges (distance between nodes) of the graph G, this Java program generates N synthetic paths as follows. First, it manually sets two vertices in V as starting and ending points, respectively. Then, it provides values for α and β. These two parameters are the maximum desirable euclidean distances, in meters, to the starting and ending points, respectively. Next, the Java program automatically selects N random pairs of vertices from G which are no further than α and β meters to the starting and ending points, respectively. For each pair of new starting and ending points it computes the shortest path by running the Dijkstra algorithm. As result, it gets the optimal path from each starting point to its corresponding ending point. Thus, our Java program finally returns a set of N synthetic paths that is written to a text file. Original source code available at https://github.com/cintrano/Robust-shortest-path. More details in [3].
-
database-service. An Angular web service listening to HTTP requests from clients and storing the received information into a database.
-
clustering-service. A Python script that processes users' paths converting them from geographical to Cartesian coordinates. Next, it computes the Hausdorff distance [1] for each pair of paths and stores these values in a distance matrix. Informally, the Hausdorff distance is the greatest of all the distances from a point in one set to the closest point in the other set. The distance matrix is then used to cluster all paths by running the density-based spatial clustering of applications with noise (DBSCAN) algorithm [2]. As result this algorithm returns the cluster each path belongs to. Finally, the script processes this information and sends a notification to users who share a path with other users through the MQTT protocol.
-
app. An Android app that sends user's location to a server (database-service) and notifies the user about other users sharing similar paths in the city. It internally uses different constants which define the URL where the database service is listening to, the update interval between user's locations readings in seconds, and the meters between two continuous data sending. The latter prevents the app to send information when the user is not moving or the delta between two consecutive readings is lower than the given threshold. Other constants define MQTT configuration such as server address and subscription topic. All information is sent in JSON format. The communication with respect to the database and clustering services is through HTTP requests and the MQTT protocol, respectively.
[1] A. A. Taha and A. Hanbury, “An efficient algorithm for calculating the exact Hausdorff distance.” IEEE Transactions On Pattern Analysis And Machine Intelligence, vol. 37 pp. 2153-63, 2015.
[2] Ester, Martin; Kriegel, Hans-Peter; Sander, Jörg; Xu, Xiaowei (1996). Simoudis, Evangelos; Han, Jiawei; Fayyad, Usama M. (eds.). A density-based algorithm for discovering clusters in large spatial databases with noise. Proceedings of the Second International Conference on Knowledge Discovery and Data Mining (KDD-96). AAAI Press. pp. 226–231. CiteSeerX 10.1.1.121.9220. ISBN 1-57735-004-9.
[3] Cintrano, C., Chicano, F., & Alba, E. (2019). Facing robustness as a multi-objective problem: A bi-objective shortest path problem in smart regions. Information Sciences, 503, 255-273.