TY - GEN
T1 - A generic database indexing framework for large-scale geographic knowledge graphs
AU - Sun, Yuhan
AU - Sarwat, Mohamed
N1 - Publisher Copyright:
© 2018 held by the owner/author(s).
PY - 2018/11/6
Y1 - 2018/11/6
N2 - The paper proposes Riso-Tree, a generic indexing framework for geographic knowledge graphs. Riso-Tree enables fast execution of graph queries that involve spatial predicates (aka. GraSp). The proposed framework augments the classic R-Tree structure with pre-materialized sub-graph entries. Riso-Tree first partitions the graph into sub-graphs based on their connectivity to the spatial sub-regions. The proposed index allows for fast execution of GraSp queries by efficiently pruning the traversed vertexes/edges based upon the materialized sub-graph information. The experiments show that the proposed Riso-Tree achieves up to two orders magnitude faster execution time than its counterparts when executing GraSp queries on real knowledge graphs (e.g., WikiData).
AB - The paper proposes Riso-Tree, a generic indexing framework for geographic knowledge graphs. Riso-Tree enables fast execution of graph queries that involve spatial predicates (aka. GraSp). The proposed framework augments the classic R-Tree structure with pre-materialized sub-graph entries. Riso-Tree first partitions the graph into sub-graphs based on their connectivity to the spatial sub-regions. The proposed index allows for fast execution of GraSp queries by efficiently pruning the traversed vertexes/edges based upon the materialized sub-graph information. The experiments show that the proposed Riso-Tree achieves up to two orders magnitude faster execution time than its counterparts when executing GraSp queries on real knowledge graphs (e.g., WikiData).
KW - GeoSpatial Knowledge Graph
KW - Range query
KW - Spatial index
UR - http://www.scopus.com/inward/record.url?scp=85058644020&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85058644020&partnerID=8YFLogxK
U2 - 10.1145/3274895.3274966
DO - 10.1145/3274895.3274966
M3 - Conference contribution
AN - SCOPUS:85058644020
T3 - GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
SP - 289
EP - 298
BT - 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2018
A2 - Xiong, Li
A2 - Tamassia, Roberto
A2 - Banaei, Kashani Farnoush
A2 - Guting, Ralf Hartmut
A2 - Hoel, Erik
PB - Association for Computing Machinery
T2 - 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2018
Y2 - 6 November 2018 through 9 November 2018
ER -