Date of Publication :7th March 2016
Abstract: Keyword search is an intuitive paradigm for searching linked data sources on the web. We propose to route keywords only to relevant sources to reduce the high cost of processing keyword search queries over all sources. We propose a novel method for computing top-k routing plans based on their potentials to contain results for a given keyword query. We employ a keyword-element relationship summary that compactly represents relationships between keywords and the data elements mentioning them. A multilevel scoring mechanism is proposed for computing the relevance of routing plans based on scores at the level of keywords, data elements, element sets, and subgraphs that connect these elements. Experiments carried out using 150 publicly available sources on the web showed that valid plans (precision@1 of 0.92) that are highly relevant (mean reciprocal rank of 0.89) can be computed in 1 second on average on a single PC. Further, we show routing greatly helps to improve the performance of keyword search, without compromising its result quality.
Reference :
-
- V. Hristidis, L. Gravano, and Y. Papakonstantinou, “Efficient IR-Style Keyword Search over Relational Databases,” Proc. 29th Int’l Conf. Very Large Data Bases (VLDB), pp. 850- 861, 2003
- F. Liu, C.T. Yu, W. Meng, and A. Chowdhury, “Effective Keyword Search in Relational Databases,” Proc. ACM SIGMOD Conf., pp. 563- 574, 2006
- Y. Luo, X. Lin, W. Wang, and X. Zhou, “Spark: Top-K Keyword Query in Relational Databases,” Proc. ACM SIGMOD Conf., pp. 115- 126, 2007
- M. Sayyadian, H. LeKhac, A. Doan, and L. Gravano, “Efficient Keyword Search Across Heterogeneous Relational Databases,” Proc. IEEE 23rd Int’l Conf. Data Eng. (ICDE), pp. 346-355, 2007.
- B. Ding, J.X. Yu, S. Wang, L. Qin, X. Zhang, and X. Lin, “Finding Top-K Min-Cost Connected Trees in Databases,” Proc. IEEE 23rd Int’l Conf. Data Eng. (ICDE), pp. 836-845, 2007.
- B. Yu, G. Li, K.R. Sollins, and A.K.H. Tung, “Effective Keyword- Based Selection of Relational Databases,” Proc. ACM SIGMOD Conf., pp. 139- 150, 2007
- Q.H. Vu, B.C. Ooi, D. Papadias, and A.K.H. Tung, “A Graph Method for Keyword-Based Selection of the Top-K Databases,” Proc. ACM SIGMOD Conf., pp. 915-926, 2008
- V. Hristidis and Y. Papakonstantinou, “Discover: Keyword Search in Relational Databases,” Proc. 28th Int’l Conf. Very Large Data Bases (VLDB), pp. 670-681, 2002.
- L. Qin, J.X. Yu, and L. Chang, “Keyword Search in Databases: The Power of RDBMS,” Proc. ACM SIGMOD Conf., pp. 681-694, 2009
- G. Li, S. Ji, C. Li, and J. Feng, “Efficient Type-Ahead Search on Relational Data: A Tastier Approach,” Proc. ACM SIGMOD Conf., pp. 695- 706, 2009.