2013/10/16 by Xavier Martinez-Palau, Martinez-Palau, Xavier, David Domínguez-Sal +7
Computer Science · #Advanced Database Systems and Queries #Data Management and Algorithms #Databases (cs.DB) #Distributed #FOS: Computer and information sciences #Graph Theory and Algorithms #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1310.4802
openalex publication_date 2013/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose the DN-tree that is a data structure to build lossy summaries of the frequent data access patterns of the queries in a distributed graph data management system. These compact representations allow us an efficient communication of the data structure in distributed systems. We exploit this data structure with a new Dynamic Data Partitioning strategy (DYDAP) that assigns the portions of the graph according to historical data access patterns, and guarantees a small network communication and a computational load balance in distributed graph queries. This method is able to adapt dynamically to new workloads and evolve when the query distribution changes. Our experiments show that DYDAP yields a throughput up to an order of magnitude higher than previous methods based on cache specialization, in a variety of scenarios, and the average response time of the system is divided by two.