Abstract
Keyword search over relational databases makes it easier to retrieve information from structural data. One solution is to first represent the relational data as a graph, and then find the minimum Steiner tree containing all the keywords by traversing the graph. However, the existing work involves substantial costs even for those based on heuristic algorithms, as the minimum Steiner tree problem is proved to be an NP-hard problem. In order to reduce the response time for a single search to a low level, a progressive ant-colony-optimization-based algorithm, called PACOKS, is proposed here, which achieves the best answer in a step-by-step manner, through the cooperation of large amounts of searches over time, instead of in an one-step manner by a single search. Through this way, the high costs for finding the best answer, are shared among large amounts of searches, so that low cost and fast response time for a single search is achieved. Extensive experimental results based on our prototype show that our method can achieve better performance than those state-of-the-art methods.
Supported by the Natural Science Foundation of China (61303004), the National Key Technology Support Program (2015BAH16F00/F01) and the Key Technology Program of Xiamen City (3502Z20151016).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Agrawal, S., Chaudhuri, S., Das, G.: DBXplorer: A system for keyword-based search over relational databases. In: Proceedings of ICDE, pp. 5–16 (2002)
Bhalotia, G., Hulgeri, A., Nakhe, C., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using banks. In: Proceedings of ICDE, pp. 431–440 (2002)
Djebali, S., Raimbault, T.: SimplePARQL: a new approach using keywords over SPARQL to query the web of data. In: Proceedings of the 11th International Conference on Semantic Systems, SEMANTICS 2015, Vienna, Austria, 15–17 September 2015, pp. 188–191 (2015)
Gutjahr, W.J.: A graph-based ant system and its convergence. Future Gener. Comput. Syst. 16(1), 873–888 (2000)
He, H., Wang, H., Yang, J., Yu, P.S.: BLINKS: ranked keyword searches on graphs. In: Proceedings of SIGMOD, pp. 305–316 (2007)
Hristidis, V., Papakonstantinou, Y.: DISCOVER: Keyword search in relationaldatabases. In: Proceedings of VLDB, pp. 670–681 (2002)
Kacholia, V., Pandit, S., Chakrabarti, S., Sudarshan, S., Desai, R., Karambelkar, H.: Bidirectional expansion for keyword search on graph databases. In: Proceedings of VLDB, pp. 505–516 (2005)
Kim, I.-J., Whang, K.-Y., Kwon, H.-Y.: SRT-rank: Ranking keyword query results in relational databases using the strongly related tree. IEICE Trans. Inf. Syst. 97(D(9)), 2398–2414 (2014)
Li, G., Ooi, B.C., Feng, J., Wang, J., Zhou, L.: EASE: an effective 3-in-1 keyword search method for unstructured, semi-structured and structured data. In: Proceedings of SIGMOD, pp. 903–914 (2008)
Liu, F., Yu, C., Meng, W., Chowdhury, A.: Effective keyword search in relational databases. In: Proceedings of SIGMOD, pp. 563–574 (2006)
Luo, Y., Wang, W., Lin, X., Zhou, X., Wang, J., Li, K.: Spark2: Top-k keyword query in relational databases. TKDE 23(12), 1763–1780 (2011)
Markowetz, A., Yang, Y., Papadias, D.: Keyword search on relational data streams. In: Proceedings of SIGMOD, pp. 605–616 (2007)
Park, C.-S., Lim, S.: Effective keyword query processing with an extended answer structure in large graph databases. IJWIS 10(1), 65–84 (2014)
Tao, Y., Yu, J.X.: Finding frequent co-occurring terms in relational keyword search. In: Proceedings of EDBT, pp. 839–850 (2009)
Yang, W., Guo, T.: An ant colony optimization algorithm for the minimum steiner tree problem and its convergence proof. Acta Math. Appl. Sinica 29(2), 352–361 (2006)
Zhou, J., Liu, Y., Yu, Z.: Improving the effectiveness of keyword search in databases using query logs. In: Li, J., Sun, Y., Yu, X., Sun, Y., Dong, X.L., Dong, X.L. (eds.) WAIM 2015. LNCS, vol. 9098, pp. 193–206. Springer, Heidelberg (2015). doi:10.1007/978-3-319-21042-1_16
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Lin, Z., Xue, Q., Lai, Y. (2016). PACOKS: Progressive Ant-Colony-Optimization-Based Keyword Search over Relational Databases. In: Cui, B., Zhang, N., Xu, J., Lian, X., Liu, D. (eds) Web-Age Information Management. WAIM 2016. Lecture Notes in Computer Science(), vol 9659. Springer, Cham. https://doi.org/10.1007/978-3-319-39958-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-39958-4_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-39957-7
Online ISBN: 978-3-319-39958-4
eBook Packages: Computer ScienceComputer Science (R0)