Λεπτομέρειες

ΕίδοςΔημοσίευση
ΚωδικόςTR-2008-12
ΤίτλοςΑποτίμηση ερωτημάτων πρόσβασης
ΣυγγραφέαςΠαναγιώτης Μπούρος, Θοδωρής Δαλαμάγκας, Σπύρος Σκιαδόπουλος, Τιμος Σελλής
Έτος2008
Λέξεις κλειδιάreachability queries
ΠερίληψηGraphs are used for modelling complex problems in many areas, such as spatial and road networks, social networks, Semantic Web. An important type of queries in graphs are reachability queries. In this paper, we consider the problem of answering "find a path" reachability queries. Given two nodes s and t in a graph, we want to find a path from s to t. To this end, we propose a novel representation of a graph as a set of paths that preserve the reachability information and introduce P-Index to index and provide efficient access in this representation. Then, we extend the depth-first search algorithm to work with the paths of the representation, instead of the graph edges, for evaluating "find a path" reachability queries. Finally, we conduct a preliminary set of experiments that indicate the advantage of exploiting a set of paths for efficiently answering "find a path" reachability queries instead of using the edges of the graph.
ΚατηγορίαAdvanced Query Processing-Optimization Techniques
ΔημοσίευσηProceedings of the Workshop on Spatial and Temporal Reasoning (STRWS) in conjunction with the 18th European Conference on Artificial Intelligence (ECAI'08), Patras, Greece, July 22, 2008
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα