Abstract
In this paper, we focus on IR style queries, keyword search, over large disk-resident graphs. Since most existing approaches cache the whole graph and indexing structure in memory, these approaches cannot be applied into large graphs, such as RDF graphs and social networks. In this paper, we design a novel indexing structure,(kernel) keyword graph to summarize the structure of original graph. Based on (kernel) keyword graph, we propose an efficient keyword search algorithm. Extensive experiments confirm that our method can scale up to large graphs with millions of nodes and edges. The performance of our approach outperforms state-of-the-art algorithms by at least one order of magnitude.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bergamaschi, S., Domnori, E., Guerra, F., Lado, R.T., Velegrakis, Y.: Keyword search over relational databases: a metadata approach. In: SIGMOD Conference 2011, pp. 565–576 (2011)
Bhalotia, G., Hulgeri, A., Nakhe, C., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using banks. In: ICDE, pp. 431–440 (2002)
Chamberlin, D.D.: Xquery: A query language for xml. In: SIGMOD Conference, pp. 1–1 (2003)
Cohen, E., Halperin, E., Kaplan, H., Zwick, U.: Reachability and distance queries via 2-hop labels. SIAM J. Comput. 32(5), 937–946 (2003)
Dalvi, B.B., Kshirsagar, M., Sudarshan, S.: Keyword search on external memory data graphs. PVLDB 1(1), 1189–1204 (2008)
Ding, B., Yu, J.X., Wang, S., Qin, L., Zhang, X., Lin, X.: Finding top-k min-cost connected trees in databases. In: ICDE, pp. 836–845 (2007)
Ha, L.Q., Sicilia-Garcia, E.I., Ming, J., Smith, F.J.: Extension of zipf’s law to words and phrases. In: COLING, p. 1 (2002)
He, H., Wang, H., Yang, J., Yu, P.S.: Blinks: ranked keyword searches on graphs. In: SIGMOD Conference (2007)
Hristidis, V., Papakonstantinou, Y.: Discover: Keyword search in relational databases. In: VLDB (2002)
Kargar, M., An, A.: Keyword search in graphs: Finding r-cliques. PVLDB, pp. 681–692 (2011)
Kasneci, G., Ramanath, M., Sozio, M., Suchanek, F.M., Weikum, G.: Star: Steiner-tree approximation in relationship graphs. In: ICDE, pp. 868–879 (2009)
Ning, X., Jin, H., Jia, W., Yuan, P.: Practical and effective ir-style keyword search over semantic web. Inf. Process. Manage. 45(2) (2009)
Tran, T., Wang, H., Rudolph, S., Cimiano, P.: Top-k exploration of query candidates for efficient keyword search on graph-shaped (rdf) data. In: ICDE (2009)
Xin, D., He, Y., Ganti, V.: Keyword++: A framework to improve keyword search over entity databases. PVLDB, 711–722 (2010)
Zou, L., Chen, L., Özsu, M.T., Zhao, D.: Answering pattern match queries in large graph databases via graph embedding. VLDB J. 21(1), 97–120 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, D., Zou, L., Pan, W., Zhao, D. (2012). Keyword Graph: Answering Keyword Search over Large Graphs. In: Zhou, S., Zhang, S., Karypis, G. (eds) Advanced Data Mining and Applications. ADMA 2012. Lecture Notes in Computer Science(), vol 7713. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35527-1_53
Download citation
DOI: https://doi.org/10.1007/978-3-642-35527-1_53
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35526-4
Online ISBN: 978-3-642-35527-1
eBook Packages: Computer ScienceComputer Science (R0)