{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,23]],"date-time":"2026-01-23T08:58:11Z","timestamp":1769158691353,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,20]],"date-time":"2021-06-20T00:00:00Z","timestamp":1624147200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["322046"],"award-info":[{"award-number":["322046"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,20]]},"DOI":"10.1145\/3452021.3458322","type":"proceedings-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T14:21:58Z","timestamp":1624026118000},"page":"138-152","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Minimum Coresets for Maxima Representation of Multidimensional Data"],"prefix":"10.1145","author":[{"given":"Yanhao","family":"Wang","sequence":"first","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}]},{"given":"Michael","family":"Mathioudakis","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}]},{"given":"Yuchen","family":"Li","sequence":"additional","affiliation":[{"name":"Singapore Management University, Singapore, Singapore"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2021,6,20]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008736"},{"key":"e_1_3_2_2_2_1","volume-title":"et almbox","author":"Agarwal Pankaj K","year":"2005","unstructured":"Pankaj K Agarwal , Sariel Har-Peled , Kasturi R Varadarajan , et almbox . 2005 . Geometric approximation via coresets. In Combinatorial and computational geometry. Cambridge University Press , 1--30. Pankaj K Agarwal, Sariel Har-Peled, Kasturi R Varadarajan, et almbox. 2005. Geometric approximation via coresets. In Combinatorial and computational geometry. Cambridge University Press, 1--30."},{"key":"e_1_3_2_2_3_1","first-page":"1","article-title":"Efficient Algorithms for k-Regret Minimizing Sets","volume":"7","author":"Agarwal Pankaj K.","year":"2017","unstructured":"Pankaj K. Agarwal , Nirman Kumar , Stavros Sintos , and Subhash Suri . 2017 . Efficient Algorithms for k-Regret Minimizing Sets . In SEA. 7 : 1 -- 7 :23. Pankaj K. Agarwal, Nirman Kumar, Stavros Sintos, and Subhash Suri. 2017. Efficient Algorithms for k-Regret Minimizing Sets. In SEA. 7:1--7:23.","journal-title":"SEA."},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Pankaj K. Agarwal Jeff M. Phillips and Hai Yu. 2010. Stability of epsilon-Kernels. In ESA (1). 487--499.  Pankaj K. Agarwal Jeff M. Phillips and Hai Yu. 2010. Stability of epsilon-Kernels. In ESA (1). 487--499.","DOI":"10.1007\/978-3-642-15775-2_42"},{"key":"e_1_3_2_2_5_1","volume-title":"Agarwal and Hai Yu","author":"Pankaj","year":"2007","unstructured":"Pankaj K. Agarwal and Hai Yu . 2007 . A space-optimal data-stream algorithm for coresets in the plane. In SoCG. 1--10. Pankaj K. Agarwal and Hai Yu. 2007. A space-optimal data-stream algorithm for coresets in the plane. In SoCG. 1--10."},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250755"},{"key":"e_1_3_2_2_7_1","volume-title":"Chan","author":"Arya Sunil","year":"2014","unstructured":"Sunil Arya and Timothy M . Chan . 2014 . Better \u03b5-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and \u03b5-Kernels. In SoCG. 416--425. Sunil Arya and Timothy M. Chan. 2014. Better \u03b5-Dependencies for Offline Approximate Nearest Neighbor Search, Euclidean Minimum Spanning Trees, and \u03b5-Kernels. In SoCG. 416--425."},{"key":"e_1_3_2_2_8_1","first-page":"1","article-title":"Near-Optimal epsilon-Kernel Construction and Related Problems","volume":"10","author":"Arya Sunil","year":"2017","unstructured":"Sunil Arya , Guilherme Dias da Fonseca , and David M. Mount . 2017 . Near-Optimal epsilon-Kernel Construction and Related Problems . In SoCG. 10 : 1 -- 10 :15. Sunil Arya, Guilherme Dias da Fonseca, and David M. Mount. 2017. Near-Optimal epsilon-Kernel Construction and Related Problems. In SoCG. 10:1--10:15.","journal-title":"SoCG."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Abolfazl Asudeh Azade Nazi Nan Zhang and Gautam Das. 2017. Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative. In SIGMOD. 821--834.  Abolfazl Asudeh Azade Nazi Nan Zhang and Gautam Das. 2017. Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative. In SIGMOD. 821--834.","DOI":"10.1145\/3035918.3035932"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"crossref","unstructured":"Olivier Bachem Mario Lucic and Andreas Krause. 2018. Scalable k-Means Clustering via Lightweight Coresets. In KDD. 1119--1127.  Olivier Bachem Mario Lucic and Andreas Krause. 2018. Scalable k-Means Clustering via Lightweight Coresets. In KDD. 1119--1127.","DOI":"10.1145\/3219819.3219973"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/358315.358392"},{"key":"e_1_3_2_2_14_1","first-page":"1","article-title":"Approximate Convex Hull of Data Streams","volume":"21","author":"Blum Avrim","year":"2018","unstructured":"Avrim Blum , Vladimir Braverman , Ananya Kumar , Harry Lang , and Lin F. Yang . 2018 . Approximate Convex Hull of Data Streams . In ICALP. 21 : 1 -- 21 :13. Avrim Blum, Vladimir Braverman, Ananya Kumar, Harry Lang, and Lin F. Yang. 2018. Approximate Convex Hull of Data Streams. In ICALP. 21:1--21:13.","journal-title":"ICALP."},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Avrim Blum Sariel Har-Peled and Benjamin Raichel. 2016. Sparse Approximation via Generating Point Sets. In SODA. 548--557.  Avrim Blum Sariel Har-Peled and Benjamin Raichel. 2016. Sparse Approximation via Generating Point Sets. In SODA. 548--557.","DOI":"10.1137\/1.9781611974331.ch40"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2272457"},{"key":"e_1_3_2_2_17_1","first-page":"1","article-title":"k-Regret Minimizing Set","volume":"11","author":"Cao Wei","year":"2017","unstructured":"Wei Cao , Jian Li , Haitao Wang , Kangning Wang , Ruosong Wang , Raymond Chi-Wing Wong , and Wei Zhan . 2017 . k-Regret Minimizing Set : Efficient Algorithms and Hardness. In ICDT. 11 : 1 -- 11 :19. Wei Cao, Jian Li, Haitao Wang, Kangning Wang, Ruosong Wang, Raymond Chi-Wing Wong, and Wei Zhan. 2017. k-Regret Minimizing Set: Efficient Algorithms and Hardness. In ICDT. 11:1--11:19.","journal-title":"Efficient Algorithms and Hardness. In ICDT."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.10.002"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3116272.3116514"},{"key":"e_1_3_2_2_20_1","first-page":"1","article-title":"Dynamic Streaming Algorithms for Epsilon-Kernels","volume":"27","author":"Chan Timothy M.","year":"2016","unstructured":"Timothy M. Chan . 2016 . Dynamic Streaming Algorithms for Epsilon-Kernels . In SoCG. 27 : 1 -- 27 :11. Timothy M. Chan. 2016. Dynamic Streaming Algorithms for Epsilon-Kernels. In SoCG. 27:1--27:11.","journal-title":"SoCG."},{"key":"e_1_3_2_2_21_1","first-page":"1","article-title":"Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry","volume":"26","author":"Chan Timothy M.","year":"2017","unstructured":"Timothy M. Chan . 2017 . Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry . In SoCG. 26 : 1 -- 26 :15. Timothy M. Chan. 2017. Applications of Chebyshev Polynomials to Low-Dimensional Computational Geometry. In SoCG. 26:1--26:15.","journal-title":"SoCG."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0925-7721(97)00006-0"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28874"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"crossref","unstructured":"Sariel Har-Peled and Soham Mazumdar. 2004. On coresets for k-means and k-median clustering. In STOC. 291--300.  Sariel Har-Peled and Soham Mazumdar. 2004. On coresets for k-means and k-median clustering. In STOC. 291--300.","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/s0097539704446281"},{"key":"e_1_3_2_2_29_1","first-page":"1","article-title":"Version 4 of the CRU TS monthly high-resolution gridded multivariate climate dataset. Sci","volume":"7","author":"Harris Ian","year":"2020","unstructured":"Ian Harris , Timothy J Osborn , Phil Jones , and David Lister . 2020 . Version 4 of the CRU TS monthly high-resolution gridded multivariate climate dataset. Sci . Data , Vol. 7 , 1 (2020), 1 -- 18 . Ian Harris, Timothy J Osborn, Phil Jones, and David Lister. 2020. Version 4 of the CRU TS monthly high-resolution gridded multivariate climate dataset. Sci. Data , Vol. 7, 1 (2020), 1--18.","journal-title":"Data"},{"key":"e_1_3_2_2_30_1","first-page":"1","article-title":"epsilon-Kernel Coresets for Stochastic Points","volume":"50","author":"Huang Lingxiao","year":"2016","unstructured":"Lingxiao Huang , Jian Li , Jeff M. Phillips , and Haitao Wang . 2016 . epsilon-Kernel Coresets for Stochastic Points . In ESA. 50 : 1 -- 50 :18. Lingxiao Huang, Jian Li, Jeff M. Phillips, and Haitao Wang. 2016. epsilon-Kernel Coresets for Stochastic Points. In ESA. 50:1--50:18.","journal-title":"ESA."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"crossref","unstructured":"Nirman Kumar and Stavros Sintos. 2018. Faster Approximation Algorithm for the k-Regret Minimizing Set and Related Problems. In ALENEX. 62--74.  Nirman Kumar and Stavros Sintos. 2018. Faster Approximation Algorithm for the k-Regret Minimizing Set and Related Problems. In ALENEX. 62--74.","DOI":"10.1137\/1.9781611975055.6"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-008-0157-z"},{"key":"e_1_3_2_2_33_1","unstructured":"Baharan Mirzasoleiman Jeff Bilmes and Jure Leskovec. 2020. Coresets for Data-efficient Training of Machine Learning Models. In ICML. 6950--6960.  Baharan Mirzasoleiman Jeff Bilmes and Jure Leskovec. 2020. Coresets for Data-efficient Training of Machine Learning Models. In ICML. 6950--6960."},{"key":"e_1_3_2_2_34_1","unstructured":"Stanislav Morozov and Artem Babenko. 2018. Non-metric Similarity Graphs for Maximum Inner Product Search. In NeurIPS . 4726--4735.  Stanislav Morozov and Artem Babenko. 2018. Non-metric Similarity Graphs for Maximum Inner Product Search. In NeurIPS . 4726--4735."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920980"},{"key":"e_1_3_2_2_36_1","volume-title":"Orlin and Antonio Sede n o-Noda","author":"James","year":"2017","unstructured":"James B. Orlin and Antonio Sede n o-Noda . 2017 . An O(nm) time algorithm for finding the min length directed cycle in a graph. In SODA. 1866--1879. James B. Orlin and Antonio Sede n o-Noda. 2017. An O(nm) time algorithm for finding the min length directed cycle in a graph. In SODA. 1866--1879."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"crossref","unstructured":"Peng Peng and Raymond Chi-Wing Wong. 2014. Geometry approach for k-regret query. In ICDE. 772--783.  Peng Peng and Raymond Chi-Wing Wong. 2014. Geometry approach for k-regret query. In ICDE. 772--783.","DOI":"10.1109\/ICDE.2014.6816699"},{"key":"e_1_3_2_2_38_1","volume-title":"Preparata and Michael Ian Shamos","author":"Franco","year":"1985","unstructured":"Franco P. Preparata and Michael Ian Shamos . 1985 . Computational Geometry - An Introduction .Springer. Franco P. Preparata and Michael Ian Shamos. 1985. Computational Geometry - An Introduction .Springer."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368291"},{"key":"e_1_3_2_2_40_1","unstructured":"Shulong Tan Zhixin Zhou Zhaozhuo Xu and Ping Li. 2019. On Efficient Retrieval of Top Similarity Vectors. In EMNLP\/IJCNLP (1). 5235--5245.  Shulong Tan Zhixin Zhou Zhaozhuo Xu and Ping Li. 2019. On Efficient Retrieval of Top Similarity Vectors. In EMNLP\/IJCNLP (1). 5235--5245."},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"crossref","unstructured":"Yanhao Wang Yuchen Li and Kian-Lee Tan. 2019. Coresets for Minimum Enclosing Balls over Sliding Windows. In KDD. 314--323.  Yanhao Wang Yuchen Li and Kian-Lee Tan. 2019. Coresets for Minimum Enclosing Balls over Sliding Windows. In KDD. 314--323.","DOI":"10.1145\/3292500.3330826"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00570-z"},{"key":"e_1_3_2_2_43_1","volume-title":"Jian Li, Cheng Long, and Ashwin Lall.","author":"Xie Min","year":"2018","unstructured":"Min Xie , Raymond Chi-Wing Wong , Jian Li, Cheng Long, and Ashwin Lall. 2018 . Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality. In SIGMOD. 959--974. Min Xie, Raymond Chi-Wing Wong, Jian Li, Cheng Long, and Ashwin Lall. 2018. Efficient k-Regret Query Algorithm with Restriction-free Bound for any Dimensionality. In SIGMOD. 959--974."},{"key":"e_1_3_2_2_44_1","unstructured":"Albert Yu Pankaj K. Agarwal and Jun Yang. 2012. Processing a large number of continuous preference top-k queries. In SIGMOD. 397--408.  Albert Yu Pankaj K. Agarwal and Jun Yang. 2012. Processing a large number of continuous preference top-k queries. In SIGMOD. 397--408."},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9067-9"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118746.3118922"},{"key":"e_1_3_2_2_47_1","unstructured":"Zhixin Zhou Shulong Tan Zhaozhuo Xu and Ping Li. 2019. M\u00f6bius Transformation for Fast Inner Product Search on Graph. In NeurIPS . 8216--8227.  Zhixin Zhou Shulong Tan Zhaozhuo Xu and Ping Li. 2019. M\u00f6bius Transformation for Fast Inner Product Search on Graph. In NeurIPS . 8216--8227."}],"event":{"name":"SIGMOD\/PODS '21: International Conference on Management of Data","location":"Virtual Event China","acronym":"SIGMOD\/PODS '21","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458322","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3452021.3458322","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:00Z","timestamp":1750197780000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3452021.3458322"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,20]]},"references-count":47,"alternative-id":["10.1145\/3452021.3458322","10.1145\/3452021"],"URL":"https:\/\/doi.org\/10.1145\/3452021.3458322","relation":{},"subject":[],"published":{"date-parts":[[2021,6,20]]},"assertion":[{"value":"2021-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}