2015/10/14 by Alan Davoust, Davoust, Alan, Babak Esfandiari +1
Computer Science · #Algorithms and Data Compression #Caching and Content Delivery #Databases (cs.DB) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DB #cs.DC
paper · pdf · doi:10.48550/arxiv.1510.04347
arxiv created 2015/10/14 · openalex publication_date 2015/10/14 · arxiv updated 2015/10/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Regular Path Queries (RPQs) are a type of graph query where answers are pairs of nodes connected by a sequence of edges matching a regular expression. We study the techniques to process such queries on a distributed graph of data. While many techniques assume the location of each data element (node or edge) is known, when the components of the distributed system are autonomous, the data will be arbitrarily distributed. As the different query processing strategies are equivalently costly in the worst case, we isolate query-dependent cost factors and present a method to choose between strategies, using new query cost estimation techniques. We evaluate our techniques using meaningful queries on biomedical data.