{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,4]],"date-time":"2026-02-04T18:43:32Z","timestamp":1770230612961,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:00:00Z","timestamp":1694217600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["61572537"],"award-info":[{"award-number":["61572537"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Nature Science Foundation of China","doi-asserted-by":"crossref","award":["U1501252"],"award-info":[{"award-number":["U1501252"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Data Sci. Eng."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>With the increasing of requirements from many aspects, various queries and analyses arise focusing on social network. Time is a common and necessary dimension in various types of social networks. Social networks with time information are called temporal social networks, in which time information can be the time when a user sends message to another user. Keywords search in temporal social networks consists of finding relationships between a group users that has a set of query labels and is valid within the query time interval. It provides assistance in social network analysis, classification of social network users, community detection, etc. However, the existing methods have limitations in solving temporal social network keyword search problems. We propose a basic algorithm, the discrete timestamp algorithm, with the intention of turning the problem into a traditional keyword search on social networks. We also propose an approximative algorithm based on the discrete timestamp algorithm, but it still suffers from the traditional algorithms\u2019 low efficiency. To further improve the performance, we propose a new algorithm based on dynamic programming to solve the keyword search in temporal social network. The main idea is to extend a vertex into a solution by edge-growth operation and tree-merger operation. We also propose two powerful pruning techniques to reduce the intermediate results during the extension. Additionally, all of the algorithms we proposed are capable of handling a variety of ranking functions, and all of them can be made to conform to top-N keyword querying. The efficiency and effectiveness of the proposed algorithms are verified through extensive empirical studies.<\/jats:p>","DOI":"10.1007\/s41019-023-00218-7","type":"journal-article","created":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T10:02:14Z","timestamp":1694253734000},"page":"368-384","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An Efficient Keywords Search in Temporal Social Networks"],"prefix":"10.1007","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5995-3242","authenticated-orcid":false,"given":"Youming","family":"Ge","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zitong","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yubao","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,9,9]]},"reference":[{"key":"218_CR1","unstructured":"David K, Jon K, Amit K (2000) Connectivity and inference problems for temporal networks. In: STOC, pp 504\u2013513"},{"key":"218_CR2","doi-asserted-by":"publisher","first-page":"6979","DOI":"10.1007\/s11227-020-03534-1","volume":"77","author":"J Guan-Yi","year":"2021","unstructured":"Guan-Yi J, Yi-Cheng C, Hung-Ming L (2021) Evolution pattern mining on dynamic social network. J Supercomput 77:6979\u20136991","journal-title":"J Supercomput"},{"key":"218_CR3","doi-asserted-by":"crossref","unstructured":"Xiaoying C, Chong Z, Bin G, Weidong X (2017) Temporal query processing in social network. In: JIIS, pp 147\u2013166","DOI":"10.1007\/s10844-016-0437-0"},{"issue":"8","key":"218_CR4","first-page":"1667","volume":"29","author":"Z Liu","year":"2017","unstructured":"Liu Z, Wang C, Chen Y (2017) Keyword search on temporal graphs. TKDE 29(8):1667\u20131680","journal-title":"TKDE"},{"key":"218_CR5","doi-asserted-by":"publisher","first-page":"7777","DOI":"10.1007\/s11227-017-1976-z","volume":"76","author":"S Jingwen","year":"2020","unstructured":"Jingwen S, Chaokun W, Changping W, Gaoyang G, Jun Q (2020) An attribute-based community search method with graph refining. J Supercomput 76:7777\u20137804","journal-title":"J Supercomput"},{"key":"218_CR6","doi-asserted-by":"publisher","first-page":"1301","DOI":"10.1007\/s11227-020-03304-z","volume":"77","author":"J Youngho","year":"2021","unstructured":"Youngho J, Hyunwoo L, Ayoung C, Mincheol W (2021) Web behavior analysis in social life logging. J Supercomput 77:1301\u20131320","journal-title":"J Supercomput"},{"key":"218_CR7","doi-asserted-by":"crossref","unstructured":"Ding B, Yu JX, Wang S, Qin L, Zhang X, Lin X (2007) Finding top-k min-cost connected trees in databases. In: ICDE, pp 836\u2013845","DOI":"10.1109\/ICDE.2007.367929"},{"key":"218_CR8","doi-asserted-by":"crossref","unstructured":"Ma S, Hu R, Wang L, Lin X, Huai J (2017) Fast computation of dense temporal subgraphs. In: ICDE, pp 361\u2013372","DOI":"10.1109\/ICDE.2017.95"},{"issue":"5","key":"218_CR9","first-page":"1179","volume":"17","author":"F Rizzolo","year":"2008","unstructured":"Rizzolo F, Vaisman AA (2008) Temporal xml: modeling, indexing, and query processing. PVLDB 17(5):1179\u20131212","journal-title":"PVLDB"},{"key":"218_CR10","doi-asserted-by":"crossref","unstructured":"He H, Wang H, Yang J, Yu PS (2007) Blinks: ranked keyword searches on graphs. In: SIGMOD, pp 305\u2013316","DOI":"10.1145\/1247480.1247516"},{"key":"218_CR11","doi-asserted-by":"crossref","unstructured":"Kimelfeld B, Sagiv Y (2006) Finding and approximating top-k answers in keyword proximity search. In: SIGMOD, pp 173\u2013182","DOI":"10.1145\/1142351.1142377"},{"key":"218_CR12","doi-asserted-by":"crossref","unstructured":"Bhalotia G, Hulgeri A, Nakhe C, Chakrabarti S, Sudarshan S (2002) Keyword searching and browsing in databases using banks. In: ICDE, pp 431\u2013440","DOI":"10.1109\/ICDE.2002.994756"},{"key":"218_CR13","unstructured":"Kacholia V, Pandit S, Chakrabarti S, Sudarshan S, Desai R, Karambelkar H (2005) Bidirectional expansion for keyword search on graph databases. In: VLDB, pp 505\u2013516"},{"key":"218_CR14","doi-asserted-by":"crossref","unstructured":"Golenberg K, Kimelfeld B, Sagiv Y (2008) Keyword proximity search in complex data graphs. In: SIGMOD, pp 927\u2013940","DOI":"10.1145\/1376616.1376708"},{"issue":"3","key":"218_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1002\/net.3230010302","volume":"1","author":"SE Dreyfus","year":"1971","unstructured":"Dreyfus SE, Wagner RA (1971) The Steiner problem in graphs. Networks 1(3):195\u2013207","journal-title":"Networks"},{"key":"218_CR16","doi-asserted-by":"crossref","unstructured":"Reich G, Widmayer P (1989) Beyond Steiner\u2019s problem: a VLSI oriented generalization. In: WG, pp 196\u2013210","DOI":"10.1007\/3-540-52292-1_14"},{"key":"218_CR17","doi-asserted-by":"crossref","unstructured":"Li R-H, Qin L, Yu JX, Mao R (2016) Efficient and progressive group steiner tree search. In: SIGMOD, pp 91\u2013106","DOI":"10.1145\/2882903.2915217"},{"issue":"1","key":"218_CR18","first-page":"58","volume":"2","author":"H Wentao","year":"2019","unstructured":"Wentao H, Kaiwei L, Shimin C, Wenguang C (2019) Auxo: a temporal graph management system. BDMA 2(1):58\u201371","journal-title":"BDMA"},{"issue":"2","key":"218_CR19","first-page":"142","volume":"6","author":"Y Jianye","year":"2021","unstructured":"Jianye Y, Wu Y, Wenjie Z (2021) Keyword search on large graphs: a survey. DSE 6(2):142\u2013162","journal-title":"DSE"},{"key":"218_CR20","doi-asserted-by":"crossref","unstructured":"Hristidis V, Papakonstantinou Y, Gravano L (2003) Efficient ir-style keyword search over relational databases. In: VLDB, pp 850\u2013861","DOI":"10.1016\/B978-012722442-8\/50080-X"},{"key":"218_CR21","doi-asserted-by":"crossref","unstructured":"Luo Y, Lin X, Wang W, Zhou X (2007) Spark: top-k keyword query in relational databases. In: SIGMOD, pp 115\u2013126","DOI":"10.1145\/1247480.1247495"},{"key":"218_CR22","doi-asserted-by":"crossref","unstructured":"Sayyadian M, LeKhac H, Doan A, Gravano L (2007) Efficient keyword search across heterogeneous relational databases. In: ICDE, pp 346\u2013355","DOI":"10.1109\/ICDE.2007.367880"},{"issue":"2","key":"218_CR23","first-page":"139","volume":"32","author":"K Thirunarayan","year":"2009","unstructured":"Thirunarayan K, Immaneni T (2009) A coherent query language for XML. JIIS 32(2):139\u2013162","journal-title":"JIIS"},{"issue":"14","key":"218_CR24","first-page":"1642","volume":"6","author":"L Zhang","year":"2013","unstructured":"Zhang L, Tran T, Rettinger A (2013) Probabilistic query rewriting for efficient and effective keyword search on graph data. PVLDB 6(14):1642\u20131653","journal-title":"PVLDB"},{"key":"218_CR25","doi-asserted-by":"crossref","unstructured":"Qin L, Yu JX, Chang L, Tao Y (2009) Querying communities in relational databases. In: ICDE, pp 724\u2013735","DOI":"10.1109\/ICDE.2009.67"},{"key":"218_CR26","first-page":"564","volume":"4","author":"A Balmin","year":"2004","unstructured":"Balmin A, Hristidis V, Papakonstantinou Y (2004) Objectrank: authority-based keyword search in databases. VLDB 4:564\u2013575","journal-title":"VLDB"},{"issue":"14","key":"218_CR27","first-page":"1137","volume":"7","author":"Y Sun","year":"2021","unstructured":"Sun Y, Xiao X, Cui B, Halgamuge K, Lappas T, Luo J (2021) Finding group Steiner trees in graphs with both vertex and edge weights. PVLDB 7(14):1137\u20131149","journal-title":"PVLDB"},{"issue":"37","key":"218_CR28","first-page":"2502","volume":"3","author":"B Luyi","year":"2022","unstructured":"Luyi B, Xinyi D, Bin Q (2022) Adaptive query relaxation and top-k result sorting of fuzzy spatiotemporal data based on XML. IJIS 3(37):2502\u20132520","journal-title":"IJIS"},{"issue":"2","key":"218_CR29","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1145\/22952.22956","volume":"12","author":"R Snodgrass","year":"1987","unstructured":"Snodgrass R (1987) The temporal query language tquel. TODS 12(2):247\u2013298","journal-title":"TODS"},{"key":"218_CR30","doi-asserted-by":"crossref","unstructured":"Jensen CS, Snodgrass RT, Soo MD (1995) The tsql2 data model. In: The TSQL2 temporal query language. Springer, pp 157\u2013240","DOI":"10.1007\/978-1-4615-2289-8_10"},{"issue":"3","key":"218_CR31","first-page":"424","volume":"32","author":"B Jaewook","year":"2020","unstructured":"Jaewook B, Sungpil W, Daeyoung K (2020) hronoGraph: enabling temporal graph traversals for efficient information diffusion analysis over time. TKDE 32(3):424\u2013437","journal-title":"TKDE"},{"issue":"5","key":"218_CR32","first-page":"825","volume":"30","author":"D Ariel","year":"2021","unstructured":"Ariel D, Eliseo P, Matas P, Valeria S, Alejandro V (2021) A model and query language for temporal graph databases. JVLDB 30(5):825\u2013858","journal-title":"JVLDB"},{"key":"218_CR33","unstructured":"Maria M, Zolt M, Philipe P Pierre M (2022) Clock-G: a temporal graph management system with space-efficient storage technique. ICDE, pp 2263\u20132276"},{"issue":"4","key":"218_CR34","first-page":"352","volume":"4","author":"W Yishu","year":"2019","unstructured":"Yishu W, Ye Y, Yuliang M, Guoren W (2019) Time-dependent graphs: definitions, applications, and algorithms. DSE 4(4):352\u2013366","journal-title":"DSE"},{"key":"218_CR35","unstructured":"Koloniari G, Souravlias D, Pitoura E (2013) On graph deltas for historical queries. arXiv preprint arXiv:1302.5549"},{"key":"218_CR36","doi-asserted-by":"crossref","unstructured":"Fard A, Abdolrashidi A, Ramaswamy L, Miller JA (2012) Towards efficient query processing on massive time-evolving graphs. In: CollaborateCom, pp 567\u2013574","DOI":"10.4108\/icst.collaboratecom.2012.250532"},{"key":"218_CR37","doi-asserted-by":"crossref","unstructured":"Huo W, Tsotras VJ (2014) Efficient temporal shortest path queries on evolving social graphs. In: SSDBM, pp 1\u20134","DOI":"10.1145\/2618243.2618282"},{"issue":"9","key":"218_CR38","first-page":"721","volume":"7","author":"H Wu","year":"2014","unstructured":"Wu H, Cheng J, Huang S, Ke Y, Lu Y, Xu Y (2014) Path problems in temporal graphs. PVLDB 7(9):721\u2013732","journal-title":"PVLDB"},{"key":"218_CR39","doi-asserted-by":"crossref","unstructured":"Rozenshtein P, Gionis A, Prakash BA, Vreeken J (2016) Reconstructing an epidemic over time. In: KDD, pp 1835\u20131844","DOI":"10.1145\/2939672.2939865"},{"key":"218_CR40","doi-asserted-by":"crossref","unstructured":"Xiao H, Rozenshtein P, Tatti N, Gionis A (2018) Reconstructing a cascade from temporal observations. In: SDM, pp 666\u2013674","DOI":"10.1137\/1.9781611975321.75"},{"key":"218_CR41","first-page":"321","volume":"27","author":"L Lei","year":"2018","unstructured":"Lei L, Kai Z, Sibo W, Wen H, Xiaofang Z (2018) Go slow to go fast: minimal on-road time route scheduling with parking facilities using historical trajectory. JVLDB 27:321\u2013345","journal-title":"JVLDB"}],"container-title":["Data Science and Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-023-00218-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41019-023-00218-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41019-023-00218-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,11]],"date-time":"2023-10-11T03:58:17Z","timestamp":1696996697000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41019-023-00218-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,9]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["218"],"URL":"https:\/\/doi.org\/10.1007\/s41019-023-00218-7","relation":{},"ISSN":["2364-1185","2364-1541"],"issn-type":[{"value":"2364-1185","type":"print"},{"value":"2364-1541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,9,9]]},"assertion":[{"value":"18 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"This article does not contain any studies with human participants or animals performed by any of the authors. Results are gotten through simulation and tested number of times to take final value.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical Approval"}}]}}