Materialized Graph Index Structure for Fast K-NN Query Based on Distributed Sparse Matrix Multiplication

Graph data is used in a variety of applications. For example, in location-based services, k-NN queries for finding nearby POIs are very frequently used. Therefore, we design a materialized graph index structure for efficient query processing of graph data. The graph index is constructed by using a sparse matrix multiplication of a parallel array database. To verify the efficiency, we compared the proposed method with those of CombBLAS and Gemini in terms of kNN query processing time. As a result, despite using disks, our method improves performance 24 and 3.9 times compared to those of CombBLAS and Gemini for k-NN query processing, respectively.