{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:12:07Z","timestamp":1778807527194,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":44,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,14]],"date-time":"2020-06-14T00:00:00Z","timestamp":1592092800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["IIS-18-14493"],"award-info":[{"award-number":["IIS-18-14493"]}]},{"name":"National Science Foundation","award":["CCF-15-13816"],"award-info":[{"award-number":["CCF-15-13816"]}]},{"name":"National Science Foundation","award":["CCF-15-46392"],"award-info":[{"award-number":["CCF-15-46392"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,14]]},"DOI":"10.1145\/3375395.3387667","type":"proceedings-article","created":{"date-parts":[[2020,5,29]],"date-time":"2020-05-29T15:10:29Z","timestamp":1590765029000},"page":"213-227","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Efficient Indexes for Diverse Top-k Range Queries"],"prefix":"10.1145","author":[{"given":"Pankaj K.","family":"Agarwal","sequence":"first","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stavros","family":"Sintos","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Steiger","sequence":"additional","affiliation":[{"name":"Duke University, Durham, NC, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1","volume-title":"33rd International Symposium on Computational Geometry, SoCG 2017","volume":"77","author":"Abrahamsen M.","year":"2017","unstructured":"M. Abrahamsen , M. de Berg , K. Buchin , M. Mehr , and A. D. Mehrabi . Range-clustering queries. In B. Aronov and M. J. Katz, editors , 33rd International Symposium on Computational Geometry, SoCG 2017 , July 4 --7 , 2017 , Brisbane, Australia, volume 77 of LIPIcs, pages 5: 1 -- 5 :16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. M. Abrahamsen, M. de Berg, K. Buchin, M. Mehr, and A. D. Mehrabi. Range-clustering queries. In B. Aronov and M. J. Katz, editors, 33rd International Symposium on Computational Geometry, SoCG 2017, July 4--7, 2017, Brisbane, Australia, volume 77 of LIPIcs, pages 5:1--5:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133067"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/223\/03131"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90001-9"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0110-y"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015","author":"Aghamolaei S.","year":"2015","unstructured":"S. Aghamolaei , M. Farhadi , and H. Zarrabi-Zadeh . Diversity maximization via composable coresets . In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015 , Kingston, Ontario, Canada, August 10--12 , 2015 . Queen's University, Ontario, Canada, 2015. S. Aghamolaei, M. Farhadi, and H. Zarrabi-Zadeh. Diversity maximization via composable coresets. In Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, Kingston, Ontario, Canada, August 10--12, 2015. Queen's University, Ontario, Canada, 2015."},{"key":"e_1_3_2_1_7_1","volume-title":"Approximate range searching. Computational Geometry, 17(3--4):135--152","author":"Arya S.","year":"2000","unstructured":"S. Arya and D. M. Mount . Approximate range searching. Computational Geometry, 17(3--4):135--152 , 2000 . S. Arya and D. M. Mount. Approximate range searching. Computational Geometry, 17(3--4):135--152, 2000."},{"key":"e_1_3_2_1_8_1","volume-title":"An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM (JACM), 45(6):891--923","author":"Arya S.","year":"1998","unstructured":"S. Arya , D. M. Mount , N. S. Netanyahu , R. Silverman , and A. Y. Wu . An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM (JACM), 45(6):891--923 , 1998 . S. Arya, D. M. Mount, N. S. Netanyahu, R. Silverman, and A. Y. Wu. An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. Journal of the ACM (JACM), 45(6):891--923, 1998."},{"key":"e_1_3_2_1_9_1","volume-title":"O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications","author":"M.","year":"2008","unstructured":"M. d. Berg , O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications . Springer-Verlag TELOS , Santa Clara, CA, USA , 3 rd ed. edition, 2008 . M. d. Berg, O. Cheong, M. v. Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed. edition, 2008.","edition":"3"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009340"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9142-2"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3086464"},{"key":"e_1_3_2_1_13_1","volume-title":"A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM (JACM), 42(1):67--90","author":"Callahan P. B.","year":"1995","unstructured":"P. B. Callahan and S. R. Kosaraju . A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM (JACM), 42(1):67--90 , 1995 . P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. Journal of the ACM (JACM), 42(1):67--90, 1995."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055540.3055541"},{"key":"e_1_3_2_1_15_1","volume-title":"EPFL","author":"Cevallos A.","year":"2016","unstructured":"A. Cevallos . Approximation algorithms for geometric dispersion. Technical report , EPFL , 2016 . A. Cevallos. Approximation algorithms for geometric dispersion. Technical report, EPFL, 2016."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039695"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2018.0982"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336216"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702418498"},{"key":"e_1_3_2_1_20_1","volume-title":"Jan.","author":"Clark B. N.","year":"1991","unstructured":"B. N. Clark , C. J. Colbourn , and D. S. Johnson . Unit disk graphs. Discrete Math., 86(1--3):165--177 , Jan. 1991 . B. N. Clark, C. J. Colbourn, and D. S. Johnson. Unit disk graphs. Discrete Math., 86(1--3):165--177, Jan. 1991."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2--4, 1988","author":"Feder T.","year":"1988","unstructured":"T. Feder and D. H. Greene . Optimal algorithms for approximate clustering. In J. Simon, editor , Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2--4, 1988 , Chicago, Illinois, USA, pages 434--444. ACM , 1988 . T. Feder and D. H. Greene. Optimal algorithms for approximate clustering. In J. Simon, editor, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2--4, 1988, Chicago, Illinois, USA, pages 434--444. ACM, 1988."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514926"},{"key":"e_1_3_2_1_25_1","volume-title":"American Mathematical Soc.","author":"Har-Peled S.","year":"2011","unstructured":"S. Har-Peled . Geometric approximation algorithms. Number 173 . American Mathematical Soc. , 2011 . S. Har-Peled. Geometric approximation algorithms. Number 173. American Mathematical Soc., 2011."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00034-5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0903"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594560"},{"key":"e_1_3_2_1_29_1","volume-title":"Optimization in geometric graphs: Complexity and approximation. Texas A&M University","author":"Kahruman-Anderoglu S.","year":"2009","unstructured":"S. Kahruman-Anderoglu . Optimization in geometric graphs: Complexity and approximation. Texas A&M University , 2009 . S. Kahruman-Anderoglu. Optimization in geometric graphs: Complexity and approximation. Texas A&M University, 2009."},{"key":"e_1_3_2_1_30_1","volume-title":"The hB-tree: A multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems (TODS), 15(4):625--658","author":"Lomet D. B.","year":"1990","unstructured":"D. B. Lomet and B. Salzberg . The hB-tree: A multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems (TODS), 15(4):625--658 , 1990 . D. B. Lomet and B. Salzberg. The hB-tree: A multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems (TODS), 15(4):625--658, 1990."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230250205"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/197405.197408"},{"key":"e_1_3_2_1_33_1","first-page":"194","volume-title":"Japanese Conference on Discrete and Computational Geometry","author":"Matsui T.","year":"1998","unstructured":"T. Matsui . Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs . In Japanese Conference on Discrete and Computational Geometry , pages 194 -- 200 . Springer , 1998 . T. Matsui. Approximation algorithms for maximum independent set problems and fractional coloring problems on unit disk graphs. In Japanese Conference on Discrete and Computational Geometry, pages 194--200. Springer, 1998."},{"key":"e_1_3_2_1_34_1","first-page":"165","volume-title":"Proceedings of the 11th International Workshop, APPROX","author":"Matthew Mccutchen R.","year":"2008","unstructured":"R. Matthew Mccutchen and S. Khuller . Streaming algorithms for k-center clustering with outliers and with anonymity . In Proceedings of the 11th International Workshop, APPROX 2008 , and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, APPROX '08 \/ RANDOM '08, pages 165 -- 178 , Berlin, Heidelberg, 2008. Springer-Verlag . R. Matthew Mccutchen and S. Khuller. Streaming algorithms for k-center clustering with outliers and with anonymity. In Proceedings of the 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008 on Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques, APPROX '08 \/ RANDOM '08, pages 165--178, Berlin, Heidelberg, 2008. Springer-Verlag."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2543924"},{"key":"e_1_3_2_1_36_1","volume-title":"Dissimilarity Representation For Pattern Recognition","author":"Elzbieta D. R.","year":"2005","unstructured":"D. R. PW and P. Elzbieta . Dissimilarity Representation For Pattern Recognition , The : Foundations And Applications, volume 64 . World scientific, 2005 . D. R. PW and P. Elzbieta. Dissimilarity Representation For Pattern Recognition, The: Foundations And Applications, volume 64. World scientific, 2005."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19094-0_13"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745777"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213576"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"M. Sydow. Approximation guarantees for max sum and max min facility dispersion with parameterised triangle inequality and applications in result diversification. 2014.  M. Sydow. Approximation guarantees for max sum and max min facility dispersion with parameterised triangle inequality and applications in result diversification. 2014.","DOI":"10.14708\/ma.v42i2.547"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404048"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3192965.3192969"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508702"}],"event":{"name":"SIGMOD\/PODS '20: International Conference on Management of Data","location":"Portland OR USA","acronym":"SIGMOD\/PODS '20","sponsor":["SIGMOD ACM Special Interest Group on Management of Data"]},"container-title":["Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387667","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375395.3387667","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:32:49Z","timestamp":1750199569000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375395.3387667"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,14]]},"references-count":44,"alternative-id":["10.1145\/3375395.3387667","10.1145\/3375395"],"URL":"https:\/\/doi.org\/10.1145\/3375395.3387667","relation":{},"subject":[],"published":{"date-parts":[[2020,6,14]]},"assertion":[{"value":"2020-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}