{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:12Z","timestamp":1750306332422,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T00:00:00Z","timestamp":1468972800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Australian Research Council Projects","award":["FT-130101457, DP-140102164 and LE-140100061"],"award-info":[{"award-number":["FT-130101457, DP-140102164 and LE-140100061"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,2,28]]},"abstract":"<jats:p>Determinantal Point Processes (DPPs) are stochastic models which assign each subset of a base dataset with a probability proportional to the subset\u2019s degree of diversity. It has been shown that DPPs are particularly appropriate in data subset selection and summarization (e.g., news display, video summarizations). DPPs prefer diverse subsets while other conventional models cannot offer. However, DPPs inference algorithms have a polynomial time complexity which makes it difficult to handle large and time-varying datasets, especially when real-time processing is required. To address this limitation, we developed a fast sampling algorithm for DPPs which takes advantage of the nature of some time-varying data (e.g., news corpora updating, communication network evolving), where the data changes between time stamps are relatively small. The proposed algorithm is built upon the simplification of marginal density functions over successive time stamps and the sequential Monte Carlo (SMC) sampling technique. Evaluations on both a real-world news dataset and the Enron Corpus confirm the efficiency of the proposed algorithm.<\/jats:p>","DOI":"10.1145\/2943785","type":"journal-article","created":{"date-parts":[[2016,7,21]],"date-time":"2016-07-21T15:13:24Z","timestamp":1469114004000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Fast Sampling for Time-Varying Determinantal Point Processes"],"prefix":"10.1145","volume":"11","author":[{"given":"Maoying","family":"Qiao","sequence":"first","affiliation":[{"name":"Centre for Quantum Computation &amp; Intelligent Systems and University of Technology Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard Yi Da","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Bian","sequence":"additional","affiliation":[{"name":"Centre for Quantum Computation &amp; Intelligent Systems and University of Technology Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dacheng","family":"Tao","sequence":"additional","affiliation":[{"name":"Centre for Quantum Computation &amp; Intelligent Systems and University of Technology Sydney, NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,7,20]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2962--2966","author":"Abel Fabian","year":"2013","unstructured":"Fabian Abel , Qi Gao , Geert-Jan Houben , and Ke Tao . 2013 . Twitter-based user modeling for news recommendations . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2962--2966 . Fabian Abel, Qi Gao, Geert-Jan Houben, and Ke Tao. 2013. Twitter-based user modeling for news recommendations. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2962--2966."},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 31st International Conference on Machine Learning (ICML).","author":"Affandi Raja Hafiz","year":"2014","unstructured":"Raja Hafiz Affandi , Emily B. Fox , Ryan P. Adams , and Ben Taskar . 2014 . Learning the parameters of determinantal point process kernels . In Proceedings of the 31st International Conference on Machine Learning (ICML). Raja Hafiz Affandi, Emily B. Fox, Ryan P. Adams, and Ben Taskar. 2014. Learning the parameters of determinantal point process kernels. In Proceedings of the 31st International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS).","author":"Affandi Raja Hafiz","year":"2013","unstructured":"Raja Hafiz Affandi , Emily B. Fox , and Ben Taskar . 2013 a. Approximation inference in continuous determinantal point processes . In Proceedings of Advances in Neural Information Processing Systems (NIPS). Raja Hafiz Affandi, Emily B. Fox, and Ben Taskar. 2013a. Approximation inference in continuous determinantal point processes. In Proceedings of Advances in Neural Information Processing Systems (NIPS)."},{"volume-title":"Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS).","author":"Affandi Raja Hafiz","key":"e_1_2_1_4_1","unstructured":"Raja Hafiz Affandi , Alex Kulesza , and Emily B. Fox . 2013b. Markov determinantal point processes . In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS). Raja Hafiz Affandi, Alex Kulesza, and Emily B. Fox. 2013b. Markov determinantal point processes. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics (AISTATS)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2306678"},{"key":"e_1_2_1_6_1","volume-title":"NetDraw software for network visualization","author":"Borgatti Steve P.","year":"2002","unstructured":"Steve P. Borgatti . 2002. NetDraw software for network visualization . Lexington, KY : Analytic Technologies ( 2002 ), 95. Steve P. Borgatti. 2002. NetDraw software for network visualization. Lexington, KY: Analytic Technologies (2002), 95."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10955-005-7583-z"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291025"},{"key":"e_1_2_1_9_1","first-page":"2845","article-title":"On a sequential subset selection procedure for the least probable multinomial cell","volume":"20","author":"Chen Pinyucen","year":"1991","unstructured":"Pinyucen Chen and Lifang Hsu . 1991 . On a sequential subset selection procedure for the least probable multinomial cell . Stoch. Anal. Appl. 20 , 9 (1991), 2845 -- 2862 . Pinyucen Chen and Lifang Hsu. 1991. On a sequential subset selection procedure for the least probable multinomial cell. Stoch. Anal. Appl. 20, 9 (1991), 2845--2862.","journal-title":"Stoch. Anal. Appl."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9868.2006.00553.x"},{"key":"e_1_2_1_11_1","volume-title":"Carley","author":"Diesner Jana","year":"2005","unstructured":"Jana Diesner and Kathleen M . Carley . 2005 . Exploration of communication networks from the Enron email corpus. In SIAM International Conference on Data Mining : Workshop on Link Analysis, Counterterrorism and Security, Newport Beach, CA. Citeseer. Jana Diesner and Kathleen M. Carley. 2005. Exploration of communication networks from the Enron email corpus. In SIAM International Conference on Data Mining: Workshop on Link Analysis, Counterterrorism and Security, Newport Beach, CA. Citeseer."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10588-005-5377-0"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1111\/1467-9868.00280"},{"volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS), 3149--3157","author":"Gillenwater J.","key":"e_1_2_1_14_1","unstructured":"J. Gillenwater , A. Kulesza , E. Fox , and B. Taskar . 2014. Expectation-maximization for learning determinantal point processes . In Proceedings of Advances in Neural Information Processing Systems (NIPS), 3149--3157 . J. Gillenwater, A. Kulesza, E. Fox, and B. Taskar. 2014. Expectation-maximization for learning determinantal point processes. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 3149--3157."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/2390948.2391026"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS).","author":"Gillenwater Jennifer","year":"2012","unstructured":"Jennifer Gillenwater , Alex Kulesza , and Ben Taskar . 2012 b. Near-optimal MAP inference for determinantal point processes . In Proceedings of Advances in Neural Information Processing Systems (NIPS). Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. 2012b. Near-optimal MAP inference for determinantal point processes. In Proceedings of Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1704292"},{"key":"e_1_2_1_18_1","volume-title":"Van Loan","author":"Golub Gene H.","year":"2012","unstructured":"Gene H. Golub and Charles F . Van Loan . 2012 . Matrix Computations. Vol. 3 . JHU Press . Gene H. Golub and Charles F. Van Loan. 2012. Matrix Computations. Vol. 3. JHU Press."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS)","author":"Gong Boqing","year":"2014","unstructured":"Boqing Gong , Wei-Lun Chao , Kristen Grauman , and Fei Sha . 2014 . Diverse sequential subset selection for supervised video summarization . In Proceedings of Advances in Neural Information Processing Systems (NIPS) , 2069--2077. Boqing Gong, Wei-Lun Chao, Kristen Grauman, and Fei Sha. 2014. Diverse sequential subset selection for supervised video summarization. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2069--2077."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1214\/154957806000000078"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086737.2086739"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS), 2319--2327","author":"Kang Byungkon","year":"2013","unstructured":"Byungkon Kang . 2013 . Fast determinantal point process sampling with application to clustering . In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2319--2327 . Byungkon Kang. 2013. Fast determinantal point process sampling with application to clustering. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 2319--2327."},{"volume-title":"Proceedings of the 15th IFAC Symposium on System Identification (SYSID).","author":"Kantas N.","key":"e_1_2_1_23_1","unstructured":"N. Kantas , A. Doucet , S. S. Singh , and J. M. Maciejowski . 2009. An overview of sequential Monte Carlo methods for parameter estimation in general state-space models . In Proceedings of the 15th IFAC Symposium on System Identification (SYSID). N. Kantas, A. Doucet, S. S. Singh, and J. M. Maciejowski. 2009. An overview of sequential Monte Carlo methods for parameter estimation in general state-space models. In Proceedings of the 15th IFAC Symposium on System Identification (SYSID)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30115-8_22"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of Advances in Neural Information Processing Systems (NIPS), 1171--1179","author":"Kulesza Alex","year":"2010","unstructured":"Alex Kulesza and Ben Taskar . 2010 . Structured determinantal point processes . In Proceedings of Advances in Neural Information Processing Systems (NIPS), 1171--1179 . Alex Kulesza and Ben Taskar. 2010. Structured determinantal point processes. In Proceedings of Advances in Neural Information Processing Systems (NIPS), 1171--1179."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 28th International Conference on Machine Learning (ICML).","author":"Kulesza Alex","year":"2011","unstructured":"Alex Kulesza and Ben Taskar . 2011 a. K-dpps: Fixed-size determinantal point processes . In Proceedings of the 28th International Conference on Machine Learning (ICML). Alex Kulesza and Ben Taskar. 2011a. K-dpps: Fixed-size determinantal point processes. In Proceedings of the 28th International Conference on Machine Learning (ICML)."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI).","author":"Kulesza Alex","year":"2011","unstructured":"Alex Kulesza and Ben Taskar . 2011 b. Learning determinantal point processes . In Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI). Alex Kulesza and Ben Taskar. 2011b. Learning determinantal point processes. In Proceedings of Conference on Uncertainty in Artificial Intelligence (UAI)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Alex Kulesza and Ben Taskar. 2012. Determinantal Point Processes for Machine Learning.   Alex Kulesza and Ben Taskar. 2012. Determinantal Point Processes for Machine Learning.","DOI":"10.1561\/9781601986290"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2456899"},{"key":"e_1_2_1_30_1","volume-title":"Algorithm-dependent generalization bounds for multi-task learning","author":"Liu Tongliang","year":"2016","unstructured":"Tongliang Liu , Dacheng Tao , Mingli Song , and Stephen Maybank . 2016. Algorithm-dependent generalization bounds for multi-task learning . IEEE Trans. Pattern Anal. Mach. Intell . ( 2016 ). DOI:http:\/\/dx.doi.org\/10.1109\/TPAMI.2016.2544314 10.1109\/TPAMI.2016.2544314 Tongliang Liu, Dacheng Tao, Mingli Song, and Stephen Maybank. 2016. Algorithm-dependent generalization bounds for multi-task learning. IEEE Trans. Pattern Anal. Mach. Intell. (2016). DOI:http:\/\/dx.doi.org\/10.1109\/TPAMI.2016.2544314"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2307\/1425855"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556612"},{"key":"e_1_2_1_33_1","unstructured":"Christophe Ange Napol\u00e9on Biscio and Fr\u00e9d\u00e9ric Lavancier. 2014. About repulsiveness of determinantal point processes.  Christophe Ange Napol\u00e9on Biscio and Fr\u00e9d\u00e9ric Lavancier. 2014. About repulsiveness of determinantal point processes."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 28th AAAI Conference on Artificial Intelligence.","author":"Ohsaka Naoto","year":"2014","unstructured":"Naoto Ohsaka , Takuya Akiba , Yuichi Yoshida , and Ken-ichi Kawarabayashi. 2014 . Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations . In Proceedings of the 28th AAAI Conference on Artificial Intelligence. Naoto Ohsaka, Takuya Akiba, Yuichi Yoshida, and Ken-ichi Kawarabayashi. 2014. Fast and accurate influence maximization on large networks with pruned Monte-Carlo simulations. In Proceedings of the 28th AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, 3047--3051","author":"Rakthanmanon Thanawin","year":"2013","unstructured":"Thanawin Rakthanmanon , Bilson Campana , Abdullah Mueen , Gustavo Batista , Brandon Westover , Qiang Zhu , Jesin Zakaria , and Eamonn Keogh . 2013 . Data mining a trillion time series subsequences under dynamic time warping . In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, 3047--3051 . Thanawin Rakthanmanon, Bilson Campana, Abdullah Mueen, Gustavo Batista, Brandon Westover, Qiang Zhu, Jesin Zakaria, and Eamonn Keogh. 2013. Data mining a trillion time series subsequences under dynamic time warping. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, 3047--3051."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of WSDM Workshop on Diversity in Document Retrieval.","author":"Raman Karthik","year":"2012","unstructured":"Karthik Raman , Pannaga Shivaswamy , and Thorsten Joachims . 2012 . Learning to diversify from implicit feedback . In Proceedings of WSDM Workshop on Diversity in Document Retrieval. Karthik Raman, Pannaga Shivaswamy, and Thorsten Joachims. 2012. Learning to diversify from implicit feedback. In Proceedings of WSDM Workshop on Diversity in Document Retrieval."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2002.808076"},{"volume-title":"Estimating Convergence of Markov Chain Monte Carlo Simulations. Master\u2019s thesis","author":"Sahlin Kristoffer","key":"e_1_2_1_38_1","unstructured":"Kristoffer Sahlin . 2011. Estimating Convergence of Markov Chain Monte Carlo Simulations. Master\u2019s thesis . Stockholm University , Stockholm, Sweden . Kristoffer Sahlin. 2011. Estimating Convergence of Markov Chain Monte Carlo Simulations. Master\u2019s thesis. Stockholm University, Stockholm, Sweden."},{"key":"e_1_2_1_41_1","volume-title":"Adams","author":"Snoek Jasper","year":"2013","unstructured":"Jasper Snoek and Ryan P . Adams . 2013 . A determinantal point process latent variable model for inhibition in neural spiking data. In Proceedings of Advances in Neural Information Processing Systems (NIPS) . Jasper Snoek and Ryan P. Adams. 2013. A determinantal point process latent variable model for inhibition in neural spiking data. In Proceedings of Advances in Neural Information Processing Systems (NIPS)."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1080\/07474946.2014.961848"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 28th AAAI Conference on Artificial Intelligence.","author":"Wang Shusen","year":"2014","unstructured":"Shusen Wang , Chao Zhang , Hui Qian , and Zhihua Zhang . 2014 . Using the matrix ridge approximation to speedup determinantal point processes sampling algorithms . In Proceedings of the 28th AAAI Conference on Artificial Intelligence. Shusen Wang, Chao Zhang, Hui Qian, and Zhihua Zhang. 2014. Using the matrix ridge approximation to speedup determinantal point processes sampling algorithms. In Proceedings of the 28th AAAI Conference on Artificial Intelligence."},{"key":"e_1_2_1_44_1","volume-title":"Jennings","author":"Wu Feng","year":"2013","unstructured":"Feng Wu , Shlomo Zilberstein , and Nicholas R . Jennings . 2013 . Monte-Carlo expectation maximization for decentralized POMDPs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press , 397--403. Feng Wu, Shlomo Zilberstein, and Nicholas R. Jennings. 2013. Monte-Carlo expectation maximization for decentralized POMDPs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI). AAAI Press, 397--403."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1361684.1361686"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2013.2296528"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2015.2417578"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCYB.2014.2386282"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.19"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556613"},{"key":"e_1_2_1_51_1","volume-title":"Adams","author":"Zou James Y.","year":"2012","unstructured":"James Y. Zou and Ryan P . Adams . 2012 . Priors for diversity in generative latent variable models. In Proceedings of Advances in Neural Information Processing Systems (NIPS) . James Y. Zou and Ryan P. Adams. 2012. Priors for diversity in generative latent variable models. In Proceedings of Advances in Neural Information Processing Systems (NIPS)."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2943785","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2943785","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:45Z","timestamp":1750222485000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2943785"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,7,20]]},"references-count":49,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,2,28]]}},"alternative-id":["10.1145\/2943785"],"URL":"https:\/\/doi.org\/10.1145\/2943785","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2016,7,20]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-07-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}