Generating Illustrative Snippets for Open Data on the Web

ABSTRACT

To embrace the open data movement, increasingly many datasets have been published on the Web to be reused. Users, when assessing the usefulness of an unfamiliar dataset, need means to quickly inspect its contents. To satisfy the needs, we propose to automatically extract an optimal small portion from a dataset, called a snippet, to concisely illustrate the contents of the dataset. We consider the quality of a snippet from three aspects: coverage, familiarity, and cohesion, which are jointly formulated in a new combinatorial optimization problem called the maximum-weight-and-coverage connected graph problem (MwcCG). We give a constant-factor approximation algorithm for this NP-hard problem, and experiment with our solution on real-world datasets. Our quantitative analysis and user study show that our approach outperforms a baseline approach.

References

1. . Bai, R. Delbru, and G. Tummarello. RDF snippets for Semantic Web search engines. In phProc. O™, part II, pages 1304--1318, November 2008.
2. . Basse, F. Gandon, I. Mirbel, and M. Lo. DFS-based frequent graph pattern extraction to characterize the content of RDF triple stores. In phProc. WebSci, April 2010.
3. . Benedetti, L. Po, and S. Bergamaschi. A visual summary for Linked Open Data sources. In phProc. ISWC Posters & Demos, pages 173--176, October 2014.
4. . Campinas, R. Delbru, and G. Tummarello. Efficiency and precision trade-offs in graph summary algorithms. In phProc. IDEAS, pages 38--47, October 2013.
5. . Cheng, C. Jin, and Y. Qu. HIEDS: A Generic and Efficient Approach to Hierarchical Dataset Summarization. In phProc. IJCAI, pages 3705--3711, July 2016.
6. . Cheng, T. Tran, and Y. Qu. RELIN: Relatedness and informativeness-based centrality for entity summarization. In phProc. ISWC, pages 114--129, October 2011.
7. . Cheng, D. Xu, and Y. Qu. C3D
8. P: A summarization method for interactive entity resolution. phJ. Web Semant., 35:202--213, December 2015.
9. . Cheng, D. Xu, and Y. Qu. Summarizing entity descriptions for effective and efficient human-centered entity linking. In phProc. WWW, pages 184--194, May 2015.
10. . Dolby, A. Fokoue, A. Kalyanpur, A. Kershenbaum, E. Schonberg, K. Srinivas, and L. Ma. Scalable semantic retrieval through summarization and refinement. In phProc. AAAI, pages 299--304, July 2007.
11. . Gunaratna, K. Thirunarayan, and A. Sheth. FACES: Diversity-aware entity summarization using incremental hierarchical conceptual clustering. In phProc. AAAI, pages 116--122, January 2015.
12. .S. Hochbaum and A. Pathria. Node-optimal connected k-subgraphs. Manuscript, August 1994.
13. . Hübler, H.-P. Kriegel, K. Borgwardt, and Z. Ghahramani. Metropolis algorithms for representative subgraph sampling. In phProc. ICDM, pages 283--292, December 2008.
14. . Khatchadourian and M.P. Consens. ExpLOD: Summary-based exploration of interlinking and RDF usage in the Linked Open Data cloud. In phProc. ESWC, pages 272--287, May--June 2010.
15. .F. Lee and D.R. Dooly. Decomposition algorithms for the maximum-weight connected graph problem. phNav. Res. Logist., 45(8):817--837, December 1998.
16. . Leskovec and C. Faloutsos. Sampling from large graphs. In phProc. KDD, pages 631--636, August 2006.
17. . Liu and Y. Chen. Differentiating search results on structured data. phACM Trans. Database Syst., 37(1):4, February 2012.
18. . Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. phTechnical Report, Stanford InfoLab, 1999.
19. . Presutti, L. Aroyo, A. Adamou, B. Schopman, A. Gangemi, and G. Schreiber. Extracting core knowledge from Linked Data. In phProc. COLD, October 2011.
20. . Rietveld, R. Hoekstra, S. Schlobach, and C. Guéret. Structural properties as proxy for semantic relevance in RDF graph sampling. In phProc. ISWC, pages 81--96, October 2014.
21. . Thalhammer, I. Toma, A.J. Roa-Valverde, and D. Fensel. Leveraging usage data for Linked Data movie entity summarization. In phProc. USEWOD, April 2012.
22. . Tian, R.A. Hankins, and J.M. Patel. Efficient aggregation for graph summarization. In phProc. SIGMOD, pages 567--580, June 2008.
23. . Troullinou, H. Kondylakis, E. Daskalaki, and D. Plexousakis. RDF digest: Efficient summarization of RDF/S KBs. In phProc. ESWC, pages 119--134, May--June 2015.
24. . Zhang, G. Cheng, and Y. Qu. Ontology summarization based on RDF sentence graph. In phProc. WWW, pages 707--716, May 2007.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval tasks and goals

      • Summarization

  • World Wide Web

    • Web data description languages

      • Semantic web description languages

        • Resource Description Framework (RDF)

• Mathematics of computing

  • Discrete mathematics

    • Combinatorics

      • Combinatorial optimization

    • Graph theory

      • Approximation algorithms