nach oben

World Wide Web

Erschienen in:

01.05.2016

Finding smallest k-Compact tree set for keyword queries on graphs using mapreduce

verfasst von: Chengfei Liu, Liang Yao, Jianxin Li, Rui Zhou, Zhenying He

Erschienen in: World Wide Web | Ausgabe 3/2016

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Keyword search is integrated in many applications on account of the convenience to convey users’ query intention. Most existing works in keyword search on graphs modeled the query results as individual minimal connected trees or connected graphs that contain the keywords. We observe that significant overlap may exist among those query results, which would affect the result diversification. Besides, most solutions required accessing graph data and pre-built indexes in memory, which is not suitable to process big dataset. In this paper, we define the smallest k-compact tree set as the keyword query result, where no shared graph node exists between any two compact trees. We then develop a progressive A* based scalable solution using MapReduce to compute the smallest k-compact tree set, where the computation process could be stopped once the generated compact tree set is sufficient to compute the keyword query result. We conduct experiments to show the efficiency of our proposed algorithm.

Vorheriger Artikel Query intent mining with multiple dimensions of web search data

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Bhalotia, G., Hulgeri, A., Nakhe, C., Chakrabarti, S., Sudarshan, S.: Keyword searching and browsing in databases using banks. In: ICDE, pp 431–440 (2002)

Dalvi, B.B., Kshirsagar, M., Sudarshan, S.: Keyword search on external memory data graphs. PVLDB 1(1), 1189–1204 (2008)

Ding, B., Jeffrey X.Y., Wang, S., Qin, L., Zhang, X., Lin, X.: Finding top-k min-cost connected trees in databases. In: ICDE, pp 836–845 (2007)

Elbassuoni, S., Blanco, R.: Keyword search over RDF graphs. In: Proceedings of the 20th ACM Conference on Information and Knowledge Management, CIKM 2011, Glasgow, United Kingdom, October 24-28, 2011, pp 237–242 (2011)

Golenberg, K., Kimelfeld, B., Sagiv, Y.: Keyword proximity search in complex data graphs. In: Wang, J. T.-L. (ed.) SIGMOD Conference ACM, pp 927–940 (2008)

He, H., Wang, H., Yang, J., Philip, S.Y.: Blinks: ranked keyword searches on graphs. In: SIGMOD Conference, pp 305–316 (2007)

Jeffrey X.Y., Qin, L., Chang, L.: Keyword search in relational databases A survey. IEEE Data Eng. Bull. 33(1), 67–78 (2010)

Kacholia, V., Pandit, S., Chakrabarti, S., Sudarshan, S., Desai, R., Karambelkar, H.: Bidirectional expansion for keyword search on graph databases. In: VLDB, pp 505–516 (2005)

Kargar, M., An. A.: Keyword search in graphs finding r-cliques. PVLDB 4(10), 681–692 (2011)

10.

Ley, M.: The dblp computer science bibliography: Evolution, research issues, perspectives. In: SPIRE, pp 1–10 (2002)

11.

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: SIGMOD Conference, pp 903–914 (2008)

12.

Li, J., Liu, C., Islam, Md.S.: Keyword-based correlated network computation over large social media. In: IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014, pp 268–279 (2014)

13.

Li, J., Liu, C., Zhou, R., Wang, W.: Top-k keyword search over probabilistic xml data. In: ICDE, pp 673–684 (2011)

14.

Li, J., Liu, C., Zhou, R., Jeffrey X.Y.: Quasi-slca based keyword queryprocessing over probabilistic XML data. IEEE Trans. Knowl. Data Eng. 26(4), 957–969 (2014)CrossRef

15.

Li, J., Liu, C., Jeffrey X.Y.: Context-based diversification for keyword queries over XML data. IEEE Trans. Knowl. Data Eng. 27(3), 660–672 (2015)CrossRef

16.

Moussa, R.: Tpc-h benchmark analytics scenarios and performances on hadoop data clouds. In: NDT (1), pp 220–234 (2012)

17.

Qin, L., Jeffrey X.Y., Chang, L., Tao, Y.: Querying communities in relational databases. In: ICDE, pp 724–735 (2009)

18.

Ye, Y., Wang, G., Chen, L., Wang, H., Efficient keyword search on uncertain graph data. IEEE Trans. Knowl. Data Eng. 25(12), 2767–2779 (2013)CrossRef

19.

Zhou, R., Liu, C., Li, J., Jeffrey X.Y.: ELCA evaluation for keyword search on probabilistic XML data. World Wide Web 16(2), 171–193 (2013)CrossRef

Titel: Finding smallest k-Compact tree set for keyword queries on graphs using mapreduce
verfasst von: Chengfei Liu
Liang Yao
Jianxin Li
Rui Zhou
Zhenying He
Publikationsdatum: 01.05.2016
Verlag: Springer US
Erschienen in: World Wide Web / Ausgabe 3/2016
Print ISSN: 1386-145X
Elektronische ISSN: 1573-1413
DOI: https://doi.org/10.1007/s11280-015-0337-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3/2016

PARADISE: Big data analytics using the DBMS tightly integrated with the distributed file system

Does Web accessibility differ among banks?

Answering subgraph queries over massive disk resident graphs

Finding seeds to bootstrap focused crawlers

Semantic change computation: A successive approach

Query intent mining with multiple dimensions of web search data