Finding Temporal Graphs Using Keywords

Authors(2) :-Ramaswamy Satyanarayana Sankar, K Somasekhar

Archiving graph data over history is demanded in many applications, such as social network studies, collaborative projects, scientific graph databases, and bibliographies. Typically people are interested in querying temporal graphs. Existing keyword search approaches for graph-structured data are insufficient for querying temporal graphs. This paper initiates the study of supporting keyword-based queries on temporal graphs. We propose a search syntax that is a moderate extension of keyword search, which allows casual users to easily search temporal graphs with optional predicates and ranking functions related to timestamps. To generate results efficiently, we first propose a best path iterator, which finds the paths between two data nodes in each snapshot that is the “best” with respect to three ranking factors. It prunes invalid or inferior paths and maximizes shared processing among different snapshots. Then we develop algorithms that efficiently generate top-k query results. Extensive experiments verified the efficiency and effectiveness of our approach.

Authors and Affiliations

Ramaswamy Satyanarayana Sankar
Department of MCA, RCR Institutions of Management & Technology, Tirupathi, Andhra Pradesh, India
K Somasekhar

  1. Tsql2 and sql3 interactions. rts/sql3.html.
  2. VisTrails.
  3. WebArchive Project. cho/research/ archive.html.
  4. A.Balmin, V.Hristidis, and Y.Papakonstantinou.ObjectRank: Authority-Based Keyword Search in Databases.In VLDB, pages 564–575, 2004.
  5. G.Bhalotia, A.Hulgeri, C.Nakhe, S.Chakrabarti, and S.Sudarshan.Keyword Searching and Browsing in Databases using BANKS.In ICDE, pages 431–440, 2002.
  6. R.Bin-Thalab and N.El-Tazi.TOIX: Temporal Object Indexing for XML Documents.In DEXA, pages 235–249, 2015.
  7. R.Bin-Thalab, N.El-Tazi, and M.E.El-Sharkawi.TMIX: Temporal Model for Indexing XML Documents.In AICCSA, pages 1–8, 2013.
  8. J.Coffman and A.C.Weaver.A Framework for Evaluating Database Keyword Search Strategies.In CIKM, 2010.
  9. B.Ding, J.X.Yu, and L.Qin.Finding Time-Dependent Shortest Paths over Large Graphs.In EDBT, pages 205–216, 2008.
  10. B.Ding, J.X.Yu, S.Wang, L.Qin, X.Zhang, and X.Lin.Finding Top-k Min-Cost Connected Trees in Databases.In ICDE, pages 836–845, 2007.
  11. A.Fard, A.Abdolrashidi, L.Ramaswamy, and J.A.Miller.Towards Efficient Query Processing on Massive Time-evolving Graphs.In CollaborateCom, pages 567–574, 2012.
  12. K.Golenberg, B.Kimelfeld, and Y.Sagiv.Keyword Proximity Search in Complex Data Graphs.In SIGMOD Conference, pages 927–940, 2008.
  13. H.He, H.Wang, J.Yang, and P.S.Yu.BLINKS: Ranked Keyword Searches on Graphs.In SIGMOD Conference, pages 305–316, 2007.
  14. V.Hristidis, L.Gravano, and Y.Papakonstantinou.Efficient IRStyle Keyword Search over Relational Databases.In VLDB, pages 850–861, 2003.
  15. W.Huo and V.J.Tsotras.Efficient Temporal Shortest Path Queries on Evolving Social Graphs.In SSDBM, pages 38:1–38:4, 2014.
  16. C.S.Jensen, R.T.Snodgrass, and M.D.Soo.The TSQL2 Data Model.In The TSQL2 Temporal Query Language.1995.
  17. V.Kacholia, S.Pandit, S.Chakrabarti, S.Sudarshan, R.Desai, and H.Karambelkar.Bidirectional Expansion For Keyword Search on Graph Databases.In VLDB, pages 505–516, 2005.
  18. D.Kempe, J.Kleinberg, and A.Kumar.Connectivity and inference problems for temporal networks.In Proceedings of the Thirty-second Annual ACM Symposium on Theory of Computing, STOC ’00, pages 504–513, New York, NY, USA, 2000.ACM.
  19. B.Kimelfeld and Y.Sagiv.Finding and Approximating Top-k Answers in Keyword Proximity Search.In PODS, 2006.
  20. G.Koloniari, D.Souravlias, and E.Pitoura.On Graph Deltas for Historical Queries.CoRR, abs/1302.5549, 2013.
  21. Y.Luo, X.Lin, W.Wang, and X.Zhou.SPARK: Top-k Keyword Query in Relational Databases.In SIGMOD Conference, pages 115– 126, 2007.
  22. L.Qin, J.X.Yu, L.Chang, and Y.Tao.Querying Communities in Relational Databases.In ICDE, pages 724–735, 2009.
  23. C.Ren, E.Lo, B.Kao, X.Zhu, and R.Cheng.On Querying Historical Evolving Graph Sequences.PVLDB, 4(11), 2011.
  24. F.Rizzolo and A.A.Vaisman.Temporal XML: Modeling, Indexing, and Query Processing.VLDB J., 17(5):1179–1212, 2008.
  25. M.Sayyadian, H.LeKhac, A.Doan, and L.Gravano.Efficient Keyword Search Across Heterogeneous Relational Databases.In ICDE, pages 346–355, 2007.
  26. R.T.Snodgrass.The Temporal Query Language TQuel.ACM Trans.Database Syst., 12(2):247–298, 1987.
  27. M.Steinbauer and G.Anderst-Kotsis.DynamoGraph: A Distributed System for Large-scale, Temporal Graph Processing, its Implementation and First Observations.In WWW, 2016.
  28. L.Zhang, T.Tran, and A.Rettinger.Probabilistic Query Rewriting for Efficient and Effective Keyword Search on Graph Data.In PVLDB, 2014.
  29. B.Zong, X.Xiao, Z.Li, Z.Wu, Z.Qian, X.Yan, A.K.Singh, and G.Jiang.Behavior Query Discovery in System-Generated Temporal Graphs.PVLDB, 9(4):240–251, 2015.

Publication Details

Published in : Volume 3 | Issue 4 | March-April 2018
Date of Publication : 2018-04-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 1207-1209
Manuscript Number : CSEIT1833585
Publisher : Technoscience Academy

ISSN : 2456-3307

Cite This Article :

Ramaswamy Satyanarayana Sankar, K Somasekhar, "Finding Temporal Graphs Using Keywords", International Journal of Scientific Research in Computer Science, Engineering and Information Technology (IJSRCSEIT), ISSN : 2456-3307, Volume 3, Issue 4, pp.1207-1209, March-April-2018.
Journal URL :

Article Preview