{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T22:44:31Z","timestamp":1753051471925},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:p>\n            In a graph, the reverse nearest neighbors (RNN) of vertex\n            <jats:italic>f<\/jats:italic>\n            refer to the set of vertices that consider\n            <jats:italic>f<\/jats:italic>\n            as their nearest neighbor. When\n            <jats:italic>f<\/jats:italic>\n            represents a facility like a subway station, its RNN comprises potential users who prefer the nearest facility. In practice, there may be\n            <jats:italic>underutilized<\/jats:italic>\n            facilities with small RNN sizes, and relocating these facilities to expand their service can be costly or infeasible. A more cost-effective approach involves selectively upgrading some edges (e.g., reducing their weights) to expand the RNN sizes of underutilized facilities. This motivates our research on the\n            <jats:bold>Expanding Reverse Nearest Neighbors<\/jats:bold>\n            (ERNN) problem, which aims to maximize the RNN size of a target facility by upgrading a limited number of edges. Solving the ERNN problem allows underutilized facilities to serve more users and alleviate the burden on other facilities. Despite numerous potential applications, ERNN is hard to solve: It can be proven to be NP-hard and APX-hard, and it exhibits non-monotonic and non-submodular properties. To overcome these challenges, we propose novel greedy algorithms that improve efficiency by minimizing the number of edges that need to be processed and the cost of processing each edge. Experimental results demonstrate that the proposed algorithms achieve orders of magnitude speedup compared to the standard greedy algorithm while greatly expanding the RNN.\n          <\/jats:p>","DOI":"10.14778\/3636218.3636220","type":"journal-article","created":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:04:07Z","timestamp":1709658247000},"page":"630-642","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Expanding Reverse Nearest Neighbors"],"prefix":"10.14778","volume":"17","author":[{"given":"Wentao","family":"Li","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou)"}]},{"given":"Maolin","family":"Cai","sequence":"additional","affiliation":[{"name":"Chongqing University"}]},{"given":"Min","family":"Gao","sequence":"additional","affiliation":[{"name":"Chongqing University"}]},{"given":"Dong","family":"Wen","sequence":"additional","affiliation":[{"name":"The University of New South Wales"}]},{"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"AAII, FEIT, University of Technology, Sydney"}]},{"given":"Wei","family":"Wang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou), The Hong Kong University of Science and Technology"}]}],"member":"320","published-online":{"date-parts":[[2024,3,5]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Computing reverse nearest neighbourhood on road maps. World Wide Web","author":"Allheeib Nasser","year":"2022","unstructured":"Nasser Allheeib, Kiki Adhinugraha, David Taniar, and Md Saiful Islam. 2022. Computing reverse nearest neighbourhood on road maps. World Wide Web (2022), 1--32."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3166071"},{"key":"e_1_2_1_3_1","first-page":"72","article-title":"Upgrading arcs to minimize the maximum travel time in a network. Networks","volume":"47","author":"Campbell Ann Melissa","year":"2006","unstructured":"Ann Melissa Campbell, Timothy J Lowe, and Li Zhang. 2006. Upgrading arcs to minimize the maximum travel time in a network. Networks: An International Journal 47, 2 (2006), 72--80.","journal-title":"An International Journal"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187908"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-011-0235-9"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2904121.2904122"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2990192"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554899"},{"key":"e_1_2_1_10_1","volume-title":"Complexity of computer computations","author":"Karp Richard M","unstructured":"Richard M Karp. 1972. Reducibility among combinatorial problems. In Complexity of computer computations. Springer, 85--103."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/335191.335415"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.05.002"},{"key":"e_1_2_1_13_1","unstructured":"Wentao Li Maolin Cai Min Gao Dong Wen Lu Qin and Wei Wang. 2023. Technical Report. https:\/\/www.dropbox.com\/scl\/fo\/7jkd2bgwzvg5rv8bj2fmr\/h?rlkey=673fyrek4rlvq10q4oyuva4ql&dl=0"},{"key":"e_1_2_1_14_1","volume-title":"Manipulating Structural Graph Clustering. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2749--2761","author":"Li Wentao","year":"2022","unstructured":"Wentao Li, Min Gao, Dong Wen, Hongwei Zhou, Cai Ke, and Lu Qin. 2022. Manipulating Structural Graph Clustering. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 2749--2761."},{"key":"e_1_2_1_15_1","volume-title":"2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 73--84","author":"Li Wentao","year":"2021","unstructured":"Wentao Li, Min Gao, Fan Wu, Wenge Rong, Junhao Wen, and Lu Qin. 2021. Manipulating black-box networks for centrality promotion. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 73--84."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00186-011-0363-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-014-0219-1"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403281"},{"key":"e_1_2_1_19_1","volume-title":"Ke Wang, Zhijie Li, Cheng Chen, and Zhitong Chen.","author":"Liu Yubao","year":"2013","unstructured":"Yubao Liu, Raymond Chi-Wing Wong, Ke Wang, Zhijie Li, Cheng Chen, and Zhitong Chen. 2013. A new approach for maximizing bichromatic reverse nearest neighbor search. Knowledge and information systems 36, 1 (2013), 23--58."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551863"},{"key":"e_1_2_1_21_1","volume-title":"2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 1083--1088","author":"Medya Sourav","year":"2016","unstructured":"Sourav Medya, Petko Bogdanov, and Ambuj Singh. 2016. Towards scalable network delay minimization. In 2016 IEEE 16th International Conference on Data Mining (ICDM). IEEE, 1083--1088."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2792470"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213889"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1781--1795","author":"Ouyang Dian","year":"2020","unstructured":"Dian Ouyang, Dong Wen, Lu Qin, Lijun Chang, Ying Zhang, and Xuemin Lin. 2020. Progressive top-k nearest neighbors search in large road networks. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 1781--1795."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230260105"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063952"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547315"},{"key":"e_1_2_1_28_1","volume-title":"Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimedia systems 15","author":"Safar Maytham","year":"2009","unstructured":"Maytham Safar, Dariush Ibrahimi, and David Taniar. 2009. Voronoi-based reverse nearest neighbor query processing on spatial networks. Multimedia systems 15 (2009), 295--308."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 424--427","author":"Stanojevic Rade","year":"2018","unstructured":"Rade Stanojevic, Sofiane Abbar, and Mohamed Mokbel. 2018. W-edge: Weighing the edges of the road network. In Proceedings of the 26th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. 424--427."},{"key":"e_1_2_1_30_1","volume-title":"2008 The Ninth International Conference on Web-Age Information Management. IEEE, 238--245","author":"Sun Huan-Liang","year":"2008","unstructured":"Huan-Liang Sun, Chao Jiang, Jun-Ling Liu, and Limei Sun. 2008. Continuous reverse nearest neighbor queries on moving objects in road networks. In 2008 The Ninth International Conference on Web-Age Information Management. IEEE, 238--245."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523214"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1754--1763","author":"Sun Xin","year":"2021","unstructured":"Xin Sun, Xin Huang, Zitan Sun, and Di Jin. 2021. Budget-constrained Truss Maximization over Large Graphs: A Component-based Approach. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 1754--1763."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457247"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687754"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.89"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1128596.1128765"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:COAP.0000013061.17529.79"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3636218.3636220","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,5]],"date-time":"2024-03-05T17:09:22Z","timestamp":1709658562000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3636218.3636220"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["10.14778\/3636218.3636220"],"URL":"https:\/\/doi.org\/10.14778\/3636218.3636220","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,12]]},"assertion":[{"value":"2024-03-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}