{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:30:49Z","timestamp":1772166649592,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T00:00:00Z","timestamp":1612828800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T00:00:00Z","timestamp":1612828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Big Data"],"published-print":{"date-parts":[[2021,12]]},"abstract":"Abstract<\/jats:title>\n \n As the scale of datasets used for big data applications expands rapidly, there have been increased efforts to develop faster algorithms. This paper addresses big data summarisation problems using the submodular maximisation approach and proposes an efficient algorithm for maximising general non-negative submodular objective functions subject to\n k<\/jats:italic>\n -extendible system constraints. Leveraging a random sampling process and a decreasing threshold strategy, this work proposes an algorithm, named Sample Decreasing Threshold Greedy (SDTG). The proposed algorithm obtains an expected approximation guarantee of\n \n \n $$\\frac{1}{1+k}-\\epsilon $$<\/jats:tex-math>\n \n \n \n 1<\/mml:mn>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for maximising monotone submodular functions and of\n \n \n $$\\frac{k}{(1+k)^2}-\\epsilon $$<\/jats:tex-math>\n \n \n \n k<\/mml:mi>\n \n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n <\/mml:mfrac>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in non-monotone cases with expected computational complexity of\n \n \n $$O\\left(\\frac{n}{(1+k)\\epsilon }\\ln \\frac{r}{\\epsilon }\\right)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n \n \n n<\/mml:mi>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n +<\/mml:mo>\n k<\/mml:mi>\n )<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n ln<\/mml:mo>\n \n r<\/mml:mi>\n \u03f5<\/mml:mi>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Here,\n r<\/jats:italic>\n is the largest size of feasible solutions, and\n \n \n $$\\epsilon \\in \\left(0, \\frac{1}{1+k}\\right)$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n \u2208<\/mml:mo>\n \n 0<\/mml:mn>\n ,<\/mml:mo>\n \n 1<\/mml:mn>\n \n 1<\/mml:mn>\n +<\/mml:mo>\n k<\/mml:mi>\n <\/mml:mrow>\n <\/mml:mfrac>\n <\/mml:mfenced>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is an adjustable designing parameter for the trade-off between the approximation ratio and the computational complexity. The performance of the proposed algorithm is validated and compared with that of benchmark algorithms through experiments with a movie recommendation system based on a real database.\n <\/jats:p>","DOI":"10.1186\/s40537-021-00416-y","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T07:03:39Z","timestamp":1612854219000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A sample decreasing threshold greedy-based algorithm for big data summarisation"],"prefix":"10.1186","volume":"8","author":[{"given":"Teng","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9938-0370","authenticated-orcid":false,"given":"Hyo-Sang","family":"Shin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antonios","family":"Tsourdos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,9]]},"reference":[{"issue":"2","key":"416_CR1","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.bdr.2015.01.006","volume":"2","author":"X Jin","year":"2015","unstructured":"Jin X, Wah BW, Cheng X, Wang Y. Significance and challenges of big data research. Big Data Res. 2015;2(2):59\u201364.","journal-title":"Big Data Res"},{"key":"416_CR2","unstructured":"Mirzasoleiman B. Big data summarization using submodular functions. Doctoral dissertation, ETH Zurich; 2017."},{"key":"416_CR3","unstructured":"Tschiatschek S, Djolonga J, Krause A. Learning probabilistic submodular diversity models via noise contrastive estimation. In: Proceedings of the 19th international conference on artificial intelligence and statistics (AISTATS); 2016. p. 770\u20139."},{"key":"416_CR4","doi-asserted-by":"crossref","unstructured":"Yu Q, Xu EL, Cui S. Submodular maximization with multi-knapsack constraints and its applications in scientific literature recommendations. In: 2016 IEEE global conference on signal and information processing (GlobalSIP); 2016. p. 1295\u20139.","DOI":"10.1109\/GlobalSIP.2016.7906050"},{"key":"416_CR5","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A. Fast constrained submodular maximization: personalized data summarization. In: Proceedings of the 33rd international conference on machine learning (ICML). vol. 48; 2016. p. 1358\u201367."},{"key":"416_CR6","unstructured":"Mirzasoleiman B, Karbasi A, Krause A. Deletion-robust submodular maximization: data summarization with the right to be forgotten. In: Proceedings of the 34th international conference on machine learning (ICML). vol. 70; 2017. p. 2449\u201358."},{"key":"416_CR7","unstructured":"Mirzasoleiman B, Karbasi A, Sarkar R, Krause A. Distributed submodular maximization: identifying representative elements in massive data. In: Advances in neural information processing systems (NIPS); 2013. p. 2049\u201357."},{"issue":"1","key":"416_CR8","first-page":"8330","volume":"17","author":"B Mirzasoleiman","year":"2016","unstructured":"Mirzasoleiman B, Karbasi A, Sarkar R, Krause A. Distributed submodular maximization. J Mach Learn Res. 2016;17(1):8330\u2013733.","journal-title":"J Mach Learn Res"},{"key":"416_CR9","unstructured":"Norouzi-Fard A, Tarnawski J, Mitrovi\u0107 S, Zandieh A, Mousavifar A, Svensson O. Beyond $$1\/2$$-approximation for submodular maximization on massive data streams. In: Proceedings of the 35th international conference on machine learning (ICML); 2018. p. 3829\u201338."},{"key":"416_CR10","unstructured":"Balkanski E, Mirzasoleiman B, Krause A, Singer Y. Learning sparse combinatorial representations via two-stage submodular maximization. In: Proceedings of the 33rd international conference on machine learning (ICML); 2016. p. 2207\u201316."},{"key":"416_CR11","doi-asserted-by":"crossref","unstructured":"Lavania C, Bilmes J. Auto-summarization: a step towards unsupervised learning of a submodular mixture. In: Proceedings of the 2019 SIAM international conference on data mining (sDM). SIAM; 2019. p. 396\u2013404.","DOI":"10.1137\/1.9781611975673.45"},{"key":"416_CR12","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A. Streaming submodular maximization: massive data summarization on the fly. In: 20th ACM SIGKDD international conference on knowledge discovery and data mining (KDD). New York: ACM; 2014. p. 671\u201380.","DOI":"10.1145\/2623330.2623637"},{"key":"416_CR13","unstructured":"Balkanski E, Breuer A, Singer Y. Non-monotone submodular maximization in exponentially fewer iterations. In: 32nd conference on neural information processing systems (NeurIPS 2018); 2018. p. 2353\u201364."},{"key":"416_CR14","unstructured":"Mitrovic M, Kazemi E, Zadimoghaddam M, Karbasi A. Data summarization at scale: a two-stage submodular approach. In: Proceedings of the 35th international conference on machine learning (ICML). vol. 80. PMLR; 2018. p. 3596\u2013605."},{"key":"416_CR15","unstructured":"Mirzasoleiman B, Karbasi A, Badanidiyuru A, Krause A. Distributed submodular cover: succinctly summarizing massive data. In: Advances in neural information processing systems (NIPS); 2015. p. 2881\u20139."},{"key":"416_CR16","doi-asserted-by":"crossref","unstructured":"Xu J, Mukherjee L, Li Y, Warner J, Rehg JM, Singh V. Gaze-enabled egocentric video summarization via constrained submodular maximization. In: 2015 IEEE conference on computer vision and pattern recognition (CVPR); 2015. p. 2235\u201344.","DOI":"10.1109\/CVPR.2015.7298836"},{"key":"416_CR17","doi-asserted-by":"crossref","unstructured":"Gygli M, Grabner H, Van\u00a0Gool L. Video summarization by learning submodular mixtures of objectives. In: 2015 IEEE conference on computer vision and pattern recognition (CVPR); 2015. p. 3090\u20138.","DOI":"10.1109\/CVPR.2015.7298928"},{"key":"416_CR18","unstructured":"Krause A, Guestrin C. Near-optimal observation selection using submodular functions. In: Proceedings of the 22nd national conference on artificial intelligence. vol. 2. Palo Alto: AAAI Press; 2007. p. 1650\u20134."},{"issue":"1","key":"416_CR19","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML. An analysis of approximations for maximizing submodular set functions\u2014I. Math Program. 1978;14(1):265\u201394.","journal-title":"Math Program"},{"key":"416_CR20","doi-asserted-by":"crossref","unstructured":"Mestre J. Greedy in approximation algorithms. In: European symposium on algorithms (ESA). New York: Springer; 2006. p. 528\u201339.","DOI":"10.1007\/11841036_48"},{"key":"416_CR21","unstructured":"Feldman M, Harshaw C, Karbasi A. Greed is good: near-optimal submodular maximization via greedy optimization. In: Proceedings of the 2017 conference on learning theory (COLT). vol. 65. PMLR; 2017. p. 1\u201327."},{"key":"416_CR22","doi-asserted-by":"crossref","unstructured":"Badanidiyuru A, Vondr\u00e1k J. Fast algorithms for maximizing submodular functions. In: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM; 2014. p. 1497\u2013514.","DOI":"10.1137\/1.9781611973402.110"},{"issue":"4","key":"416_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2827872","volume":"5","author":"FM Harper","year":"2016","unstructured":"Harper FM, Konstan JA. The movielens datasets: history and context. ACM Trans Interac Intell Syst (TIIS). 2016;5(4):1\u201319.","journal-title":"ACM Trans Interac Intell Syst (TIIS)"},{"key":"416_CR24","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondr\u00e1k J, Krause A. Lazier than lazy greedy. In: 29th AAAI conference on artificial intelligence. Palo Alto: AAAI Press; 2015. p. 1812\u20138.","DOI":"10.1609\/aaai.v29i1.9486"},{"issue":"2","key":"416_CR25","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/moor.2016.0809","volume":"42","author":"N Buchbinder","year":"2016","unstructured":"Buchbinder N, Feldman M, Schwartz R. Comparing apples and oranges: query trade-off in submodular maximization. Math Oper Res. 2016;42(2):308\u201329.","journal-title":"Math Oper Res"},{"key":"416_CR26","unstructured":"Breuer A, Balkanski E, Singer Y. The FAST algorithm for submodular maximization. In: International conference on machine learning. PMLR; 2020. p. 1134\u201343."},{"issue":"3","key":"416_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1287\/moor.3.3.177","volume":"3","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA. Best algorithms for approximating the maximum of a submodular set function. Math Oper Res. 1978;3(3):177\u201388.","journal-title":"Math Oper Res"},{"issue":"6","key":"416_CR28","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu G, Chekuri C, P\u00e1l M, Vondr\u00e1k J. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput. 2011;40(6):1740\u201366.","journal-title":"SIAM J Comput"},{"key":"416_CR29","doi-asserted-by":"crossref","unstructured":"Feldman M, Naor J, Schwartz RA, unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd annual symposium on foundations of computer science (FOCS). New York: IEEE. 2011. p. 570\u20139.","DOI":"10.1109\/FOCS.2011.46"},{"key":"416_CR30","unstructured":"Amanatidis G, Fusco F, Lazos P, Leonardi S, Reiffenh\u00e4user R. Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In: Advances in Neural Information Processing Systems. 2020;33."},{"key":"416_CR31","unstructured":"Segui-Gasco P, Shin HS. Fast non-monotone submodular maximisation subject to a matroid constraint. arXiv preprint arXiv:170306053. 2017."},{"key":"416_CR32","doi-asserted-by":"crossref","unstructured":"Gupta A, Roth A, Schoenebeck G, Talwar K. Constrained non-monotone submodular maximization: offline and secretary algorithms. In: International workshop on internet and network economics (WINE). New York: Springer; 2010. p. 246\u201357.","DOI":"10.1007\/978-3-642-17572-5_20"},{"key":"416_CR33","unstructured":"Li T, Shin HS, Tsourdos A. Fast submodular maximization subject to k-extendible system constraints. arXiv preprint arXiv:181107673v1. 2018."},{"key":"416_CR34","unstructured":"Shin HS, Li T, Segui-Gasco P. Sample greedy based task allocation for multiple robot systems. arXiv preprint arXiv:190103258. 2019."},{"key":"416_CR35","unstructured":"Li T, Shin HS, Tsourdos A. Threshold greedy based task allocation for multiple robot operations. arXiv preprint arXiv:190901239. 2019."},{"key":"416_CR36","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","volume":"3","author":"A Krause","year":"2014","unstructured":"Krause A, Golovin D. Submodular function maximization. Tractability. 2014;3:71\u2013104.","journal-title":"Tractability."},{"key":"416_CR37","doi-asserted-by":"crossref","unstructured":"Buchbinder N, Feldman M, Naor JS, Schwartz R. Submodular maximization with cardinality constraints. In: Proceedings of the 25th annual ACM-SIAM symposium on discrete algorithms (SODA). SIAM; 2014. p. 1433\u201352.","DOI":"10.1137\/1.9781611973730.80"},{"key":"416_CR38","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/BFb0006528","volume-title":"Optimization techniques","author":"M Minoux","year":"1978","unstructured":"Minoux M. Accelerated greedy algorithms for maximizing submodular set functions. Optimization techniques. Berlin: Springer; 1978. p. 234\u2013243."}],"container-title":["Journal of Big Data"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-021-00416-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s40537-021-00416-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s40537-021-00416-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,15]],"date-time":"2022-12-15T19:44:20Z","timestamp":1671133460000},"score":1,"resource":{"primary":{"URL":"https:\/\/journalofbigdata.springeropen.com\/articles\/10.1186\/s40537-021-00416-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,9]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["416"],"URL":"https:\/\/doi.org\/10.1186\/s40537-021-00416-y","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-107397\/v1","asserted-by":"object"}]},"ISSN":["2196-1115"],"issn-type":[{"value":"2196-1115","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,9]]},"assertion":[{"value":"4 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 January 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"30"}}