Effective Graph Clustering for Path Queries in Digital Map Databases.
Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Effective Graph Clustering for Path Queries in Digital Map Databases.
CIKM 1996: 215-222@inproceedings{DBLP:conf/cikm/HuangJR96,
author = {Yun-Wu Huang and
Ning Jing and
Elke A. Rundensteiner},
title = {Effective Graph Clustering for Path Queries in Digital Map Databases},
booktitle = {CIKM '96, Proceedings of the Fifth International Conference on
Information and Knowledge Management, November 12 - 16, 1996,
Rockville, Maryland, USA},
publisher = {ACM},
year = {1996},
pages = {215-222},
ee = {db/conf/cikm/HuangJR96.html, http://doi.acm.org/10.1145/238355.238497},
crossref = {DBLP:conf/cikm/96},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
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
evaluation 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.
Copyright © 1996 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "Volume 2 Issue 4, CIKM, DOLAP, GIS, SIGFIDET, ..." and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
BibTeX
Printed Edition
CIKM '96, Proceedings of the Fifth International Conference on Information and Knowledge Management, November 12 - 16, 1996, Rockville, Maryland, USA.
ACM 1996
Contents BibTeX
Online Edition
Citation Page
BibTeX
Referenced by
- Ning Jing, Yun-Wu Huang, Elke A. Rundensteiner:
Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation.
IEEE Trans. Knowl. Data Eng. 10(3): 409-432(1998)
- Yun-Wu Huang, Ning Jing, Elke A. Rundensteiner:
Integrated Query Processing Strategies for Spatial Path Queries.
ICDE 1997: 477-486
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
CIKM 1996 Proceedings, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:01:53 2009