Efficient batch processing for multiple keyword queries on graph data
Date
2016
Authors
Chen, L.
Liu, C.
Yang, X.
Wang, B.
Li, J.
Zhou, R.
Editors
Advisors
Journal Title
Journal ISSN
Volume Title
Type:
Conference paper
Citation
Proceedings of the 25th International Conference on Information and Knowledge Management, 2016, vol.24-28-October-2016, pp.1261-1270
Statement of Responsibility
Lu Chen, Chengfei Liu, Xiaochun Yang, Bin Wang, Jianxin Li, and Rui Zhou
Conference Name
25th ACM International on Conference on Information and Knowledge Management (CIKM) (24 Oct 2016 - 28 Oct 2016 : Indianapolis, IN)
Abstract
Recently, answering keyword queries on graph data has drawn a great deal of attention from database communities. However, most graph keyword search solutions proposed so far primarily focus on a single query setting. We observe that for a popular keyword query system, the number of keyword queries received could be substantially large even in a short time interval, and the chance that these queries share common keywords is quite high. Therefore, answering keyword queries in batches would significantly enhance the performance of the system. Motivated by this, this paper studies efficient batch processing for multiple keyword queries on graph data. Realized that finding both the optimal query plan for multiple queries and the optimal query plan for a single keyword query on graph data are computationally hard, we first propose two heuristic approaches which target maximizing keyword overlap and give preferences for processing keywords with short sizes. Then we devise a cardinality based cost estimation model that takes both graph data statistics and search semantics into account. Based on the model, we design an A* based algorithm to find the global optimal execution plan for multiple queries. We evaluate the proposed model and algorithms on two real datasets and the experimental results demonstrate their efficacy.
School/Discipline
Dissertation Note
Provenance
Description
Access Status
Rights
© 2016 Copyright held by the owner/author(s)