K-NEAREST NEIGHBORS SEARCH IMPLEMENTATION ON TIME AGGREGATED GRAPH IN GRAPH DATABASE

• Main Author: Legawa Halqavi, Prama
• Format: Final Project
• Language: Indonesia
• Online Access: https://digilib.itb.ac.id/gdl/view/42404
• Institution: Institut Teknologi Bandung

In real world problems, the data contained in a graph data structure is not always constant, the data can change over time. One of graph modeling which can model time dependent graph is time aggregated graph. Time aggregated graph can answer queries such as searching for knearest neighbors. K-nearest neighbors search on graph is a search operation that search k nearest nodes from given source node. However, k-nearest neighbors search on time aggregated graph cannot be solved using the classic k-nearest neighbors algorithm. Special modeling is also needed to store the time aggregated graph data structure into a graph database. In this work, a plugin is built that can be used to manage time aggregated graphs on the Neo4j graph database and it can search k-nearest neighbors on the time aggregated graph. Time aggregated graph that modeled into the database has edge value that changes over time and a constant node (doesn’t change over time). The edge value of the graph being modeled is a time variable so the k-nearest neighbors search is solved by finding the nearest k node in terms of time. Operations that support data manipulation in the time aggregated graph are also implemented. These operations consist of accessors, modifiers, and predicates operation. The implemented plugin is tested with three types of testing, they are functionality testing, performance testing, and the use of kNN function on the plugin. Functionality testing gets output results as expected. In performance testing, the testing is aims to see the impact of some kNN function input parameters to the execution time. The testing results from the performance test is that the k parameter is affect the execution time of the kNN function. Then the use of the kNN function on the plugin is done by creating a web-based application that utilizes the kNN search function contained on the plugin.