Effective graph clustering for path queries in digital map databases
Effective graph clustering for path queries in digital map databases
复制标题
DOI：
10.1145/238355.238497
复制
发表时间：
1996-11
期刊：
影响因子：
--
通讯作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
中科院分区：
文献类型：
--
作者：
Yun-Wu Huang;N. Jing;Elke A. Rundensteiner
Clustering for Path Queries in Digital Map Databases * Ning Jingt Elke A. Rundensteiner Changsha Institute of Technology University of Michigan jning@eecs.umiclt.edu rtmdenst@eecs.umich.edu In this paper, we present an experimental evaluation of graph clustering strategies in terms of their effectiveness in optimizing I/O for path query processing in digital map databases. Clustering optimization is attractive because it does not incurs any run-time cost, and is complimentary to many of the existing techniques in path query optimization. We first propose a novel graph clustering technique, called Spatial Partition Clustering (SPC), that creates balanced partitions of links based on the spatial proximity of their origin nodes. We then select three alternative clustering techniques from the literature, namely two-way partitioning, approximately topological clustering, and random clustering, to compare their performance in path query processing with SPC. Experimental evahration indicates that our SPC performs the best for the high-locality graphs (such as GIS maps), whereas the two-way partitioning approach performs the best for no-locality random graphs.
