{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,29]],"date-time":"2023-08-29T15:23:34Z","timestamp":1693322614186},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"14","license":[{"start":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T00:00:00Z","timestamp":1651622400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T00:00:00Z","timestamp":1651622400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Institute of Information & Communications Technology Planning & Evaluation","award":["2020-0-00073"]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["2021R1A2C101443"],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,9]]},"abstract":"Abstract<\/jats:title>This study proposes an efficient exact k<\/jats:italic>-flexible aggregate nearest neighbor (k<\/jats:italic>-FANN) search algorithm in road networks using the M-tree. The state-of-the-art IER-k<\/jats:italic>NN algorithm used the R-tree and pruned off unnecessary nodes based on the Euclidean coordinates of objects in road networks. However, IER-k<\/jats:italic>NN made many unnecessary accesses to index nodes since the Euclidean distances between objects are significantly different from the actual shortest-path distances between them. In contrast, our algorithm proposed in this study can greatly reduce unnecessary accesses to index nodes compared with IER-k<\/jats:italic>NN since the M-tree is constructed based on the actual shortest-path distances between objects. To the best of our knowledge, our algorithm is the first exact FANN algorithm that uses the M-tree. We prove that our algorithm does not cause any false drop. In conducting a series of experiments using various real road network datasets, our algorithm consistently outperformed IER-k<\/jats:italic>NN by up to 6.92 times.<\/jats:p>","DOI":"10.1007\/s11227-022-04496-2","type":"journal-article","created":{"date-parts":[[2022,5,4]],"date-time":"2022-05-04T14:02:49Z","timestamp":1651672969000},"page":"16286-16302","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficient exact k-flexible aggregate nearest neighbor search in road networks using the M-tree"],"prefix":"10.1007","volume":"78","author":[{"given":"Moonyoung","family":"Chung","sequence":"first","affiliation":[]},{"given":"Soon J.","family":"Hyun","sequence":"additional","affiliation":[]},{"ORCID":"http:\/\/orcid.org\/0000-0002-3161-6479","authenticated-orcid":false,"given":"Woong-Kee","family":"Loh","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,4]]},"reference":[{"key":"4496_CR1","unstructured":"Abdelgawad L, Kluegl P, Genc E, Falkner S, Hutter F (2019) Optimizing Neural Networks for Patent Classification. In: Proc. of European Conf. on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), W\u00fcrzburg, Germany, pp. 688\u2013703, Sept"},{"key":"4496_CR2","doi-asserted-by":"crossref","unstructured":"Abeywickrama T, Cheema M. A., Taniar D (2016) k-nearest neighbors on road networks: a journey in experimentation and in-memory implementation. In: Proc. of the VLDB Endowment (PVLDB). 9(6): 492\u2013503","DOI":"10.14778\/2904121.2904125"},{"key":"4496_CR3","doi-asserted-by":"crossref","unstructured":"Abeywickrama T, Cheema M. A., Storandt S (2020) Hierarchical Graph Traversal for Aggregate k Nearest Neighbors Search in Road Networks. In: Proc. of Int\u2019l Conf. on Automated Planning and Scheduling (ICAPS). Nancy, France, pp. 2\u201310","DOI":"10.24963\/ijcai.2021\/640"},{"key":"4496_CR4","doi-asserted-by":"crossref","unstructured":"Abraham I, Delling D, Goldberg A. V., Werneck R. F. (2011) A hub-based labeling algorithm for shortest paths in road networks. In: Proc. of Int\u2019l Conf. on Experimental algorithms (SEA), Crete, Greece, pp. 230\u2013241","DOI":"10.1007\/978-3-642-20662-7_20"},{"key":"4496_CR5","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, Kawarabayashi K, Kawata Y (2014) Fast shortest-path distance queries on road networks by pruned highway labeling. In: Proc. of Meeting on Algorithm Engineering & Experiments (ALENEX), Portland, Oregon, USA, pp. 147\u2013154","DOI":"10.1137\/1.9781611973198.14"},{"key":"4496_CR6","doi-asserted-by":"crossref","unstructured":"Akiba T, Hayashi T, Nori N, Iwata Y, Yoshida Y (2015) Efficient Top-$$k$$ Shortest-path distance queries on large networks by pruned landmark labeling. In: Proc. of AAAI Conf. on Artificial Intelligence, Austin, Texas, USA, pp. 2\u20138","DOI":"10.1609\/aaai.v29i1.9154"},{"key":"4496_CR7","unstructured":"Bachmann JP (2019) The SuperM-Tree: indexing metric spaces with sized objects. arXiv:1901.11453"},{"key":"4496_CR8","doi-asserted-by":"publisher","first-page":"3045","DOI":"10.1007\/s11227-021-03975-2","volume":"78","author":"RJ Barrientos","year":"2021","unstructured":"Barrientos RJ, Riquelme JA, Hern\u00e1ndez-Garc\u00eda R, Navarro CA, Soto-Silva W (2021) Fast kNN query processing over a multi-node GPU environment. J Supercomput 78:3045","journal-title":"J Supercomput"},{"key":"4496_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.is.2019.06.006","volume":"87","author":"P \u010cech","year":"2020","unstructured":"\u010cech P, Loko\u010d J, Silva YN (2020) Pivot-based approximate k-NN similarity joins for big high-dimensional data. Inf Syst 87:1\u201318","journal-title":"Inf Syst"},{"issue":"1","key":"4496_CR10","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s11192-020-03634-y","volume":"125","author":"L Chen","year":"2020","unstructured":"Chen L, Xu S, Zhu L, Zhang J, Lei X, Yang G (2020) A deep learning based method for extracting semantic information from patent documents. Scientometrics 125(1):289\u2013312","journal-title":"Scientometrics"},{"key":"4496_CR11","doi-asserted-by":"crossref","unstructured":"Chen Z, Yao B, Wang Z. J., Gao X, Shang S, Ma S, Guo M (2020) Flexible Aggregate Nearest Neighbor Queries and its Keyword-Aware Variant on Road Networks. In: IEEE Trans. on Knowledge and Data Engineering (TKDE), Early Access","DOI":"10.1109\/TKDE.2020.2975998"},{"issue":"2","key":"4496_CR12","doi-asserted-by":"publisher","first-page":"2138","DOI":"10.1007\/s11227-020-03521-6","volume":"77","author":"M Chung","year":"2021","unstructured":"Chung M, Loh W-K (2021) $$\\alpha$$-Probabilistic flexible aggregate nearest neighbor search in road networks using landmark multidimensional scaling. J Supercomput 77(2):2138\u20132153","journal-title":"J Supercomput"},{"key":"4496_CR13","unstructured":"Ciaccia P, Patella M, Zezula P (1997) M-tree: an efficient access method for similarity search in metric spaces. In: Proc. of the Int\u2019l Conf. on Very Large Data Bases (VLDB), Athens, Greece, pp. 426\u2013435"},{"issue":"5","key":"4496_CR14","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1109\/TKDE.2014.2365820","volume":"27","author":"Y Gao","year":"2015","unstructured":"Gao Y, Qin X, Zheng B, Chen G (2015) Efficient reverse top-$$k$$ Boolean spatial keyword queries on road networks. IEEE Trans Knowledge Data Eng 27(5):1205\u20131218","journal-title":"IEEE Trans Knowledge Data Eng"},{"key":"4496_CR15","doi-asserted-by":"crossref","unstructured":"Ioup E, Shaw K, Sample J, Abdelguerfi M (2007) Efficient AKNN spatial network queries using the M-Tree. In: Proc. of ACM Int\u2019l Symp. on Advances in Geographic Information Systems (GIS). Seattle, Washington, USA, Article 46, pp. 1\u20134","DOI":"10.1145\/1341012.1341070"},{"key":"4496_CR16","doi-asserted-by":"crossref","unstructured":"Kriegel H.-P., Kr\u00f6ger P, Kunath P, Renz M, Schmidt T (2007) Proximity queries in large traffic networks. In: Proc. of ACM Int\u2019l Symp. on Advances in Geographic Information Systems (GIS), Seattle, Washington, USA, Article 21, pp. 1\u20138","DOI":"10.1145\/1341012.1341040"},{"key":"4496_CR17","doi-asserted-by":"crossref","unstructured":"Kriegel H.-P., Kr\u00f6ger P, Renz M, Schmidt T (2008) Hierarchical graph embedding for efficient query processing in very large traffic networks. In: Proc. of Int\u2019l Conf. on Scientific and Statistical Database Management (SSDBM), Hong Kong, China, 150\u2013167","DOI":"10.1007\/978-3-540-69497-7_12"},{"issue":"3","key":"4496_CR18","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1109\/TKDE.2010.243","volume":"24","author":"KCK Lee","year":"2012","unstructured":"Lee KCK, Lee W, Zheng B, Tian Y (2012) ROAD: a new spatial object search framework for road networks. IEEE Trans Knowledge Data Eng 24(3):547\u2013560","journal-title":"IEEE Trans Knowledge Data Eng"},{"key":"4496_CR19","doi-asserted-by":"publisher","first-page":"12561","DOI":"10.1007\/s11227-021-03776-7","volume":"77","author":"J Lee","year":"2021","unstructured":"Lee J, Park S (2021) Efficient methods for finding an optimal network location for travel planning. J Supercomput 77:12561","journal-title":"J Supercomput"},{"issue":"9","key":"4496_CR20","doi-asserted-by":"publisher","first-page":"9827","DOI":"10.1007\/s11227-021-03665-z","volume":"77","author":"W Lee","year":"2021","unstructured":"Lee W, Song JJ, Lee CC, Jo T-C, Lee JJH (2021) Graph threshold algorithm. J Supercomput 77(9):9827\u20139847","journal-title":"J Supercomput"},{"key":"4496_CR21","doi-asserted-by":"crossref","unstructured":"Li Y, Li F, Yi K, Yao B, Wang M (2011) Flexible aggregate similarity search. In: Proc. of ACM Int\u2019l Conf. on Management of Data (SIGMOD), Athens, Greece, pp. 1009\u20131020","DOI":"10.1145\/1989323.1989429"},{"issue":"3","key":"4496_CR22","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s00778-015-0418-x","volume":"25","author":"F Li","year":"2016","unstructured":"Li F, Yi K, Tao Y, Yao B, Li Y, Xie D, Wang M (2016) Exact and approximate flexible aggregate similarity search. VLDB J 25(3):317\u2013338","journal-title":"VLDB J"},{"issue":"6","key":"4496_CR23","doi-asserted-by":"publisher","first-page":"3592","DOI":"10.1109\/TITS.2020.3003902","volume":"22","author":"S Li","year":"2021","unstructured":"Li S, Li B, Yu J, Zhang L, Zhang A, Cai K (2021) Probabilistic threshold $$k$$-ANN query method based on uncertain voronoi diagram in internet of vehicles. IEEE Trans Intell Transp Syst 22(6):3592\u20133602","journal-title":"IEEE Trans Intell Transp Syst"},{"key":"4496_CR24","doi-asserted-by":"crossref","unstructured":"Manolopoulos Y, Nanopoulos A, Papadopoulos AN, Theodoridis Y (2005) R-Trees: theory and applications. Springer","DOI":"10.1007\/978-1-84628-293-5"},{"issue":"7","key":"4496_CR25","doi-asserted-by":"publisher","first-page":"1664","DOI":"10.1109\/TMC.2019.2911950","volume":"19","author":"X Miao","year":"2020","unstructured":"Miao X, Gao Y, Mai G, Chen G, Li Q (2020) On efficiently monitoring continuous aggregate $$k$$ nearest neighbors in road networks. IEEE Trans Mobile Comput 19(7):1664\u20131676","journal-title":"IEEE Trans Mobile Comput"},{"key":"4496_CR26","doi-asserted-by":"crossref","unstructured":"Ouyang D, Wen D, Qin L, Chang L, Zhang Y, Lin X (2020) Progressive Top-K Nearest Neighbors Search in large road networks. In: Proc. of ACM SIGMOD Int\u2019l Conf. on Management of Data (SIGMOD). Portland, Oregon, USA, 1781\u20131795","DOI":"10.1145\/3318464.3389746"},{"key":"4496_CR27","doi-asserted-by":"crossref","unstructured":"Papadias D, Zhang J, Mamoulis N, TaoQuery Y (2003) Processing in spatial network databases. In: Proc. of Int\u2019l Conf. on Very Large Data Bases (VLDB), Berlin, Germany, pp. 802\u2013813","DOI":"10.1016\/B978-012722442-8\/50076-8"},{"issue":"1","key":"4496_CR28","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s11192-021-04179-4","volume":"127","author":"AH Roudsari","year":"2022","unstructured":"Roudsari AH, Afshar J, Lee W, Lee S (2022) PatentNet: multi-label classification of patent documents using deep learning based language understanding. Scientometrics 127(1):207\u2013231","journal-title":"Scientometrics"},{"key":"4496_CR29","doi-asserted-by":"crossref","unstructured":"Shalaby M, Stutzki J, Schubert M, Gunnemann S (2018) An LSTM approach to patent classification based on fixed hierarchy vectors. In: Proc. of SIAM Int\u2019l Conf. on Data Mining (SDM), San Diego, CA, USA, pp. 495\u2013503","DOI":"10.1137\/1.9781611975321.56"},{"key":"4496_CR30","doi-asserted-by":"crossref","unstructured":"Shaw K, Ioup E, Sample J, Abdelguerfi M, Tabone O (2007) Efficient approximation of spatial network queries using the m-tree with road network embedding. In: Proc. of Int\u2019l Conf. on Scientific and Statistical Database Management (SSDBM), Banff, Canada, pp. 11\u201311","DOI":"10.1109\/SSDBM.2007.11"},{"key":"4496_CR31","first-page":"721","volume":"15","author":"V de Silva","year":"2003","unstructured":"de Silva V, Tenenbaum JB (2003) Global versus local methods in nonlinear dimensionality reduction. Adv Neural Inf Process Syst 15:721\u2013728","journal-title":"Adv Neural Inf Process Syst"},{"key":"4496_CR32","unstructured":"de Silva V, Tenenbaum JB (2004) Sparse multidimensional scaling using landmark points, Technical report, Vol. 120, Stanford University"},{"key":"4496_CR33","doi-asserted-by":"crossref","unstructured":"Yao B, Chen Z, Gao X, Shang S, Ma S, Guo M (2018) Flexible aggregate nearest neighbor queries in road networks. In: Proc. of IEEE Int\u2019l Conf. on Data Engineering (ICDE), Paris, France, pp. 761\u2013772","DOI":"10.1109\/ICDE.2018.00074"},{"issue":"6","key":"4496_CR34","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1109\/TKDE.2005.87","volume":"17","author":"ML Yiu","year":"2005","unstructured":"Yiu ML, Mamoulis N, Papadias D (2005) Aggregate nearest neighbor queries in road networks. Trans Knowledge Data Eng 17(6):820\u2013833","journal-title":"Trans Knowledge Data Eng"},{"key":"4496_CR35","doi-asserted-by":"publisher","first-page":"813","DOI":"10.1016\/j.ins.2019.10.021","volume":"512","author":"J Zhao","year":"2020","unstructured":"Zhao J, Gao Y, Ma C, Jin P, Wen S (2020) On efficiently diversified top-$$k$$ geo-social keyword query processing in road networks. Inf Sci 512:813\u2013829","journal-title":"Inf Sci"},{"issue":"8","key":"4496_CR36","doi-asserted-by":"publisher","first-page":"2175","DOI":"10.1109\/TKDE.2015.2399306","volume":"27","author":"R Zhong","year":"2015","unstructured":"Zhong R, Li G, Tan K, Zhou L, Gong Z (2015) G-Tree: an efficient and scalable index for spatial search on road networks. IEEE Trans Knowledge Data Eng 27(8):2175\u20132189","journal-title":"IEEE Trans Knowledge Data Eng"},{"key":"4496_CR37","doi-asserted-by":"crossref","unstructured":"Zhou Y, Zeng J (2015) Massively parallel a* search on a GPU. In: Proc. of AAAI Conf. on Artificial Intelligence, Austin, Texas, USA, pp. 1248\u20131254","DOI":"10.1609\/aaai.v29i1.9367"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04496-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04496-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04496-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,8]],"date-time":"2022-09-08T16:48:17Z","timestamp":1662655697000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04496-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,4]]},"references-count":37,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["4496"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04496-2","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,4]]},"assertion":[{"value":"1 April 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 May 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}
