{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T18:56:16Z","timestamp":1778784976063,"version":"3.51.4"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>\n            Given two spatial datasets\n            <jats:italic>P<\/jats:italic>\n            (e.g., facilities) and\n            <jats:italic>Q<\/jats:italic>\n            (queries), an\n            <jats:italic>aggregate nearest neighbor<\/jats:italic>\n            (ANN) query retrieves the point(s) of\n            <jats:italic>P<\/jats:italic>\n            with the smallest aggregate distance(s) to points in\n            <jats:italic>Q<\/jats:italic>\n            . Assuming, for example,\n            <jats:italic>n<\/jats:italic>\n            users at locations\n            <jats:italic>q<\/jats:italic>\n            <jats:sub>1<\/jats:sub>\n            ,\u2026\n            <jats:italic>q<\/jats:italic>\n            <jats:sub>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sub>\n            , an ANN query outputs the facility\n            <jats:italic>p<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            that minimizes the\n            <jats:italic>sum<\/jats:italic>\n            of distances |\n            <jats:italic>pq<\/jats:italic>\n            <jats:sub>i<\/jats:sub>\n            | for 1 \u2264\n            <jats:italic>i<\/jats:italic>\n            \u2264\n            <jats:italic>n<\/jats:italic>\n            that the users have to travel in order to meet there. Similarly, another ANN query may report the point\n            <jats:italic>p<\/jats:italic>\n            \u2208\n            <jats:italic>P<\/jats:italic>\n            that minimizes the\n            <jats:italic>maximum<\/jats:italic>\n            distance that any user has to travel, or the\n            <jats:italic>minimum<\/jats:italic>\n            distance from some user to his\/her closest facility. If\n            <jats:italic>Q<\/jats:italic>\n            fits in memory and\n            <jats:italic>P<\/jats:italic>\n            is indexed by an R-tree, we develop algorithms for aggregate nearest neighbors that capture several versions of the problem, including weighted queries and incremental reporting of results. Then, we analyze their performance and propose cost models for query optimization. Finally, we extend our techniques for disk-resident queries and approximate ANN retrieval. The efficiency of the algorithms and the accuracy of the cost models are evaluated through extensive experiments with real and synthetic datasets.\n          <\/jats:p>","DOI":"10.1145\/1071610.1071616","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"529-576","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":212,"title":["Aggregate nearest neighbor queries in spatial databases"],"prefix":"10.1145","volume":"30","author":[{"given":"Dimitris","family":"Papadias","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"given":"Yufei","family":"Tao","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Hong Kong, China"}]},{"given":"Kyriakos","family":"Mouratidis","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"given":"Chun Kit","family":"Hui","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304184"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375668"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of International Database Engineering and Applications Symposium (IDEAS) (Edmonton, Ont., Canada, July). 44--53","author":"Benetis R.","unstructured":"Benetis , R. , Jensen , C. , Karciauskas , G. , and Saltenis , S . 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects . In Proceedings of International Database Engineering and Applications Symposium (IDEAS) (Edmonton, Ont., Canada, July). 44--53 .]] Benetis, R., Jensen, C., Karciauskas, G., and Saltenis, S. 2002. Nearest neighbor and reverse nearest neighbor queries for moving objects. In Proceedings of International Database Engineering and Applications Symposium (IDEAS) (Edmonton, Ont., Canada, July). 44--53.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263671"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","author":"Beyer K.","unstructured":"Beyer , K. , Goldstein , J. , Ramakrishnan , R. , and Shaft , U . 1999. When is nearest neighbor meaningful? In Proceedings of International Conference on Database Theory (ICDT) ( Jerusalem, Israel, Jan.). 217--235.]] Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbor meaningful? In Proceedings of International Conference on Database Theory (ICDT) (Jerusalem, Israel, Jan.). 217--235.]]"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357776"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568519"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335433"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/290593.290596"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/565117.565143"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/331499.331504"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of ACM Workshop on Geographic Information Systems (ACM GIS) (Gaithersburg, Md., Dec.). ACM","author":"Henrich A.","year":"1994","unstructured":"Henrich , A. 1994 . A distance scan algorithm for spatial access structures . In Proceedings of ACM Workshop on Geographic Information Systems (ACM GIS) (Gaithersburg, Md., Dec.). ACM , New York, 136--143.]] Henrich, A. 1994. A distance scan algorithm for spatial access structures. In Proceedings of ACM Workshop on Geographic Information Systems (ACM GIS) (Gaithersburg, Md., Dec.). ACM, New York, 136--143.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276326"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of International Conference on Artificial Neural Networks (ICANN)","author":"Hochreiter S.","unstructured":"Hochreiter , S. , Younger , A. S. , and Conwell , P . 2001. Learning to learn using gradient descent . In Proceedings of International Conference on Artificial Neural Networks (ICANN) ( Vienna, Austria, Aug.). 87--94.]] Hochreiter, S., Younger, A. S., and Conwell, P. 2001. Learning to learn using gradient descent. In Proceedings of International Conference on Artificial Neural Networks (ICANN) (Vienna, Austria, Aug.). 87--94.]]"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0099-8"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of Very Large Data Bases Conference (VLDB)","author":"Kolahdouzan M.","unstructured":"Kolahdouzan , M. and Shahabi , C . 2004. Voronoi-based K nearest neighbor search for spatial network databases . In Proceedings of Very Large Data Bases Conference (VLDB) ( Toronto, Ont., Canada, Aug.). 840--851.]] Kolahdouzan, M. and Shahabi, C. 2004. Voronoi-based K nearest neighbor search for spatial network databases. In Proceedings of Very Large Data Bases Conference (VLDB) (Toronto, Ont., Canada, Aug.). 840--851.]]"},{"key":"e_1_2_1_23_1","volume-title":"International Workshop on Spatio-Temporal Database Management (STDBM)","author":"Kollios G.","unstructured":"Kollios , G. , Gunopulos , D. , and Tsotras , V . 1999. Nearest neighbor queries in mobile environment . In International Workshop on Spatio-Temporal Database Management (STDBM) ( Edinburgh, Scotland, Sept.). 119--134.]] Kollios, G., Gunopulos, D., and Tsotras, V. 1999. Nearest neighbor queries in mobile environment. In International Workshop on Spatio-Temporal Database Management (STDBM) (Edinburgh, Scotland, Sept.). 119--134.]]"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908983"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD)","author":"Liu X.","unstructured":"Liu , X. and Ferhatosmanoglu , H . 2003. Efficient k-NN search on streaming data series . In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) ( Santorini Island, Greece, July). 83--101.]] Liu, X. and Ferhatosmanoglu, H. 2003. Efficient k-NN search on streaming data series. In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Santorini Island, Greece, July). 83--101.]]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.615443"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of Very Large Data Bases Conference (VLDB)","author":"Ng R.","unstructured":"Ng , R. and Han , J . 1994. Efficient and effective clustering methods for spatial data mining . In Proceedings of Very Large Data Bases Conference (VLDB) ( San Francisco, Calif., Sept.). 144--155.]] Ng, R. and Han, J. 1994. Efficient and effective clustering methods for spatial data mining. In Proceedings of Very Large Data Bases Conference (VLDB) (San Francisco, Calif., Sept.). 144--155.]]"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of IEEE International Conference on Data Engineering (ICDE)","author":"Papadias D.","unstructured":"Papadias , D. , Shen , Q. , Tao , Y. , and Mouratidis , K . 2004. Group nearest neighbor queries . In Proceedings of IEEE International Conference on Data Engineering (ICDE) ( Boston, Mass., Mar.). IEEE Computer Society Press, Los Alamitos, Calif., 301--312.]] Papadias, D., Shen, Q., Tao, Y., and Mouratidis, K. 2004. Group nearest neighbor queries. In Proceedings of IEEE International Conference on Data Engineering (ICDE) (Boston, Mass., Mar.). IEEE Computer Society Press, Los Alamitos, Calif., 301--312.]]"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of Very Large Data Bases Conference (VLDB)","author":"Papadias D.","unstructured":"Papadias , D. , Zhang , J. , Mamoulis , N. , and Tao , Y . 2003. Query processing in spatial network databases . In Proceedings of Very Large Data Bases Conference (VLDB) ( Berlin, Germany, Sept.). 802--813.]] Papadias, D., Zhang, J., Mamoulis, N., and Tao, Y. 2003. Query processing in spatial network databases. In Proceedings of Very Large Data Bases Conference (VLDB) (Berlin, Germany, Sept.). 802--813.]]"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of International Conference on Database Theory (ICDT)","author":"Papadopoulos A.","unstructured":"Papadopoulos , A. and Manolopoulos , Y . 1997. Performance of nearest neighbor queries in R-trees . In Proceedings of International Conference on Database Theory (ICDT) ( Delphi, Greece, Jan.). 394--408.]] Papadopoulos, A. and Manolopoulos, Y. 1997. Performance of nearest neighbor queries in R-trees. In Proceedings of International Conference on Database Theory (ICDT) (Delphi, Greece, Jan.). 394--408.]]"},{"key":"e_1_2_1_31_1","unstructured":"Press W. Flannery B. Teukolsky S. and Vetterling W. 2002. Numerical recipes in C&plus;&plus; (second edition). Cambridge University Press ISBN 0-521-75034-2.]]  Press W. Flannery B. Teukolsky S. and Vetterling W. 2002. Numerical recipes in C&plus;&plus; (second edition). Cambridge University Press ISBN 0-521-75034-2.]]"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of Very Large Data Bases Conference (VLDB)","author":"Sakurai Y.","unstructured":"Sakurai , Y. , Yoshikawa , M. , Uemura , S. , and Kojima , H . 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation . In Proceedings of Very Large Data Bases Conference (VLDB) ( Cairo, Egypt, Sept.). 516--526.]] Sakurai, Y., Yoshikawa, M., Uemura, S., and Kojima, H. 2000. The A-tree: An index structure for high-dimensional spaces using relative approximation. In Proceedings of Very Large Data Bases Conference (VLDB) (Cairo, Egypt, Sept.). 516--526.]]"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD)","author":"Shan J.","unstructured":"Shan , J. , Zhang , D. , and Salzberg , B . 2003. On spatial-range closest-pair query . In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) ( Santorini Island, Greece, July). 252--269.]] Shan, J., Zhang, D., and Salzberg, B. 2003. On spatial-range closest-pair query. In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Santorini Island, Greece, July). 252--269.]]"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Redondo Beach, Calif., July). 79--96","author":"Song Z.","unstructured":"Song , Z. and Roussopoulos , N . 2001. K-nearest neighbor search for moving query point . In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Redondo Beach, Calif., July). 79--96 .]] Song, Z. and Roussopoulos, N. 2001. K-nearest neighbor search for moving query point. In Proceedings of International Symposium on Advances in Spatial and Temporal Databases (SSTD) (Redondo Beach, Calif., July). 79--96.]]"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01759061"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777944"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.48"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842247"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of Very Large Data Bases Conference (VLDB)","author":"Weber R.","unstructured":"Weber , R. , Schek , H. J. , and Blott , S . 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In Proceedings of Very Large Data Bases Conference (VLDB) ( New York, N.Y., Aug.). 194--205.]] Weber, R., Schek, H. J., and Blott, S. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of Very Large Data Bases Conference (VLDB) (New York, N.Y., Aug.). 194--205.]]"},{"key":"e_1_2_1_41_1","volume-title":"New Results and New Trends in Computer Science","author":"Welzl E.","unstructured":"Welzl , E. 1991. Smallest enclosing disks (balls and ellipsoids) . In New Results and New Trends in Computer Science . Springer-Verlag , Lecture Notes in Computer Science, vol. 555 . New York, 359--370.]] Welzl, E. 1991. Smallest enclosing disks (balls and ellipsoids). In New Results and New Trends in Computer Science. Springer-Verlag, Lecture Notes in Computer Science, vol. 555. New York, 359--370.]]"},{"key":"e_1_2_1_42_1","first-page":"5","article-title":"The Weber problem: History and perspectives","volume":"1","author":"Wesolowsky G.","year":"1993","unstructured":"Wesolowsky , G. 1993 . The Weber problem: History and perspectives . Loc. Sci. 1 , 1, 5 -- 23 .]] Wesolowsky, G. 1993. The Weber problem: History and perspectives. Loc. Sci. 1, 1, 5--23.]]","journal-title":"Loc. Sci."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.128"},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of Very Large Data Bases Conference (VLDB)","author":"Yu C.","unstructured":"Yu , C. , Ooi , B , Tan , K. , and Jagadish , H . 2001. Indexing the distance: An efficient method to KNN processing . In Proceedings of Very Large Data Bases Conference (VLDB) ( Rome, Italy, Sept.). 421--430.]] Yu, C., Ooi, B, Tan, K., and Jagadish, H. 2001. Indexing the distance: An efficient method to KNN processing. In Proceedings of Very Large Data Bases Conference (VLDB) (Rome, Italy, Sept.). 421--430.]]"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.92"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071610.1071616","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:25:26Z","timestamp":1672244726000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071610.1071616"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071610.1071616"],"URL":"https:\/\/doi.org\/10.1145\/1071610.1071616","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}