{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T22:39:24Z","timestamp":1781908764502,"version":"3.54.5"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2013,6]]},"abstract":"<jats:p>\n            Top-k diversity queries over objects embedded in a low-dimensional vector space aim to retrieve the best\n            <jats:italic>k<\/jats:italic>\n            objects that are both relevant to given user's criteria and well distributed over a designated region. An interesting case is provided by spatial Web objects, which are produced in great quantity by location-based services that let users attach content to places and are found also in domains like trip planning, news analysis, and real estate. In this article we present a technique for addressing such queries that, unlike existing methods for diversified top-\n            <jats:italic>k<\/jats:italic>\n            queries, does not require accessing and scanning\n            <jats:italic>all<\/jats:italic>\n            relevant objects in order to find the best\n            <jats:italic>k<\/jats:italic>\n            results. Our\n            <jats:italic>Space Partitioning and Probing<\/jats:italic>\n            (SPP) algorithm works by progressively exploring the vector space, while keeping track of the already seen objects and of their relevance and position. The goal is to provide a good quality result set in terms of both relevance and diversity. We assess quality by using as a baseline the result set computed by MMR, one of the most popular diversification algorithms, while minimizing the number of accessed objects. In order to do so, SPP exploits score-based and distance-based access methods, which are available, for instance, in most geo-referenced Web data sources. Experiments with both synthetic and real data show that SPP produces results that are relevant and spatially well distributed, while significantly reducing the number of accessed objects and incurring a very low computational overhead.\n          <\/jats:p>","DOI":"10.1145\/2487259.2487262","type":"journal-article","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T14:32:49Z","timestamp":1372775569000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Top-k diversity queries over bounded regions"],"prefix":"10.1145","volume":"38","author":[{"given":"Ilio","family":"Catallo","sequence":"first","affiliation":[{"name":"Politecnico di Milano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eleonora","family":"Ciceri","sequence":"additional","affiliation":[{"name":"Politecnico di Milano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piero","family":"Fraternali","sequence":"additional","affiliation":[{"name":"Politecnico di Milano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Davide","family":"Martinenghi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Marco","family":"Tagliasacchi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,7,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498766"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989405"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880999.1881028"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'98)","author":"Berchtold S.","unstructured":"Berchtold , S. , Ertl , B. , Keim , D. A. , Kriegel , H.-P. , and Seidl , T . 1998. Fast nearest neighbor search in high-dimensional space . In Proceedings of the International Conference on Data Engineering (ICDE'98) . 209--218. Berchtold, S., Ertl, B., Keim, D. A., Kriegel, H.-P., and Seidl, T. 1998. Fast nearest neighbor search in high-dimensional space. In Proceedings of the International Conference on Data Engineering (ICDE'98). 209--218."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213580"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34002-4_2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920891"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989363"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/1988776.1988781"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291025"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142505"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687666"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835449.1835506"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935897"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860709"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247623"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/565117.565143"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497474"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213884"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1988688.1988704"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_24_1","first-page":"15","article-title":"The KNDN problem: A quest for unity in diversity","volume":"32","author":"Haritsa J. R.","year":"2009","unstructured":"Haritsa , J. R. 2009 . The KNDN problem: A quest for unity in diversity . IEEE Data Eng. Bull. 32 , 4, 15 -- 22 . Haritsa, J. R. 2009. The KNDN problem: A quest for unity in diversity. IEEE Data Eng. Bull. 32, 4, 15--22.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Ilyas I. F. Aref W. G. and Elmagarmid A. K. 2003. Supporting top-k join queries in relational databases. VLDB J. 754--765.   Ilyas I. F. Aref W. G. and Elmagarmid A. K. 2003. Supporting top-k join queries in relational databases. VLDB J. 754--765.","DOI":"10.1016\/B978-012722442-8\/50072-0"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Jain A. Sarda P. and \n      Haritsa J. R\n  . \n  2004\n  . Providing diversity in k-nearest neighbor query results. In Proceedings of the 8th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining H. Dai R. Srikant and C. Zhang Eds. Lecture Notes in Computer Science Series vol. \n  3056 Springer 404--413.  Jain A. Sarda P. and Haritsa J. R. 2004. Providing diversity in k-nearest neighbor query results. In Proceedings of the 8th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining H. Dai R. Srikant and C. Zhang Eds. Lecture Notes in Computer Science Series vol. 3056 Springer 404--413.","DOI":"10.1007\/978-3-540-24775-3_49"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063979"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687663"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1005566.1005569"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920889"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920980"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the International Conference on Data Engineering. R. Chirkova, A. Dogac, M. T. \u00d6zsu, and T. K. Sellis, Eds., IEEE, 1066--1075","author":"Ni J.","unstructured":"Ni , J. and Ravishankar , C. V . 2007. Pointwise-dense region queries in spatio-temporal databases . In Proceedings of the International Conference on Data Engineering. R. Chirkova, A. Dogac, M. T. \u00d6zsu, and T. K. Sellis, Eds., IEEE, 1066--1075 . Ni, J. and Ravishankar, C. V. 2007. Pointwise-dense region queries in spatio-temporal databases. In Proceedings of the International Conference on Data Engineering. R. Chirkova, A. Dogac, M. T. \u00d6zsu, and T. K. Sellis, Eds., IEEE, 1066--1075."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350233"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772770"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376924"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12275-0_18"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-004-5622-6"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497431"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767846"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2487259.2487262","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2487259.2487262","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:54Z","timestamp":1750235754000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2487259.2487262"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":40,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,6]]}},"alternative-id":["10.1145\/2487259.2487262"],"URL":"https:\/\/doi.org\/10.1145\/2487259.2487262","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2012-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}