{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:38:37Z","timestamp":1740123517911,"version":"3.37.3"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T00:00:00Z","timestamp":1606694400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100011512","name":"National Research Foundation","doi-asserted-by":"publisher","award":["2018R1A2B6009188"],"award-info":[{"award-number":["2018R1A2B6009188"]}],"id":[{"id":"10.13039\/100011512","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010418","name":"Institute for Information and Communications Technology Promotion","doi-asserted-by":"publisher","award":["2020-0-00073"],"award-info":[{"award-number":["2020-0-00073"]}],"id":[{"id":"10.13039\/501100010418","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2021,2]]},"abstract":"Abstract<\/jats:title>In spatial database and road network applications, the search for the nearest neighbor (NN) from a given query object q<\/jats:italic> is the most fundamental and important problem. Aggregate nearest neighbor (ANN) search is an extension of the NN search with a set of query objects $$Q = \\{ q_0, \\dots , q_{M-1} \\}$$<\/jats:tex-math>\n \n Q<\/mml:mi>\n =<\/mml:mo>\n {<\/mml:mo>\n \n q<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \u22ef<\/mml:mo>\n ,<\/mml:mo>\n \n q<\/mml:mi>\n \n M<\/mml:mi>\n -<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msub>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and finds the object $$p^*$$<\/jats:tex-math>\n \n p<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that minimizes $$g \\{ d(p^*, q_i), q_i \\in Q \\}$$<\/jats:tex-math>\n \n g<\/mml:mi>\n {<\/mml:mo>\n d<\/mml:mi>\n \n (<\/mml:mo>\n \n p<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n ,<\/mml:mo>\n \n q<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n \n q<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \u2208<\/mml:mo>\n Q<\/mml:mi>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where g<\/jats:italic> (max or sum) is an aggregate function and d<\/jats:italic>() is a distance function between two objects. Flexible aggregate nearest neighbor (FANN) search is an extension of the ANN search with the introduction of a flexibility factor $$\\phi \\, (0 < \\phi \\le 1)$$<\/jats:tex-math>\n \n \u03d5<\/mml:mi>\n \n (<\/mml:mo>\n 0<\/mml:mn>\n <<\/mml:mo>\n \u03d5<\/mml:mi>\n \u2264<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and finds the object $$p^*$$<\/jats:tex-math>\n \n p<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and the set of query objects $$Q^*_\\phi $$<\/jats:tex-math>\n \n Q<\/mml:mi>\n \u03d5<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> that minimize $$g \\{ d(p^*, q_i), q_i \\in Q^*_\\phi \\}$$<\/jats:tex-math>\n \n g<\/mml:mi>\n {<\/mml:mo>\n d<\/mml:mi>\n \n (<\/mml:mo>\n \n p<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n ,<\/mml:mo>\n \n q<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n ,<\/mml:mo>\n \n q<\/mml:mi>\n i<\/mml:mi>\n <\/mml:msub>\n \u2208<\/mml:mo>\n \n Q<\/mml:mi>\n \u03d5<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msubsup>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$Q^*_\\phi $$<\/jats:tex-math>\n \n Q<\/mml:mi>\n \u03d5<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msubsup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be any subset of Q<\/jats:italic> of size $$\\phi |Q|$$<\/jats:tex-math>\n \n \u03d5<\/mml:mi>\n |<\/mml:mo>\n Q<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This study proposes an efficient $$\\alpha $$<\/jats:tex-math>\n \u03b1<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-probabilistic FANN search algorithm in road networks. The state-of-the-art FANN search algorithm in road networks, which is known as IER-$$k\\hbox {NN}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n NN<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, used the Euclidean distance based on the two-dimensional coordinates of objects when choosing an R-tree node that most potentially contains $$p^*$$<\/jats:tex-math>\n \n p<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. However, since the Euclidean distance is significantly different from the actual shortest-path distance between objects, IER-$$k\\hbox {NN}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n NN<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> looks up many unnecessary nodes, thereby incurring many calculations of \u2018expensive\u2019 shortest-path distances and eventually performance degradation. The proposed algorithm transforms road network objects into k<\/jats:italic>-dimensional Euclidean space objects while preserving the distances between them as much as possible using landmark multidimensional scaling (LMDS)<\/jats:italic>. Since the Euclidean distance after LMDS transformation is very close to the shortest-path distance, the lookup of unnecessary R-tree nodes and the calculation of expensive shortest-path distances are reduced significantly, thereby greatly improving the search performance. As a result of performance comparison experiments conducted for various real road networks and parameters, the proposed algorithm always achieved higher performance than IER-$$k\\hbox {NN}$$<\/jats:tex-math>\n \n k<\/mml:mi>\n NN<\/mml:mtext>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>; the performance (execution time) of the proposed algorithm was improved by up to 10.87 times without loss of accuracy.<\/jats:p>","DOI":"10.1007\/s11227-020-03521-6","type":"journal-article","created":{"date-parts":[[2020,11,30]],"date-time":"2020-11-30T15:02:55Z","timestamp":1606748575000},"page":"2138-2153","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["\u03b1-Probabilistic flexible aggregate nearest neighbor search in road networks using landmark multidimensional scaling"],"prefix":"10.1007","volume":"77","author":[{"given":"Moonyoung","family":"Chung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3161-6479","authenticated-orcid":false,"given":"Woong-Kee","family":"Loh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,11,30]]},"reference":[{"issue":"6","key":"3521_CR1","doi-asserted-by":"publisher","first-page":"492","DOI":"10.14778\/2904121.2904125","volume":"9","author":"T Abeywickrama","year":"2016","unstructured":"Abeywickrama T, Cheema MA, Taniar D (2016) k-nearest neighbors on road networks: a journey in experimentation and in-memory implementation. Proc VLDB Endow (PVLDB) 9(6):492\u2013503","journal-title":"Proc VLDB Endow (PVLDB)"},{"key":"3521_CR2","unstructured":"Ioup E, Shaw K, Sample J, Abdelguerfi M (2007) Efficient AKNN spatial network queries using the M-Tree. In: Proc. of Annual ACM Int\u2019l Symp. on Advances in Geographic Information Systems (GIS), Seattle, Washington, USA, Article 46, pp 1\u20134"},{"key":"3521_CR3","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":"3521_CR4","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. IEEE Trans Knowl Data Eng 17(6):820\u2013833","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"3521_CR5","doi-asserted-by":"crossref","unstructured":"Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. In: Proc. of ACM Int\u2019l Conf. on Management of data (SIGMOD), San Jose, California, USA, pp 71\u201379","DOI":"10.1145\/223784.223794"},{"issue":"7","key":"3521_CR6","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 Mob Comput 19(7):1664\u20131676","journal-title":"IEEE Trans Mob Comput"},{"issue":"2","key":"3521_CR7","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1145\/1071610.1071616","volume":"30","author":"D Papadias","year":"2005","unstructured":"Papadias D, Tao Y, Mouratidis K, Hui CK (2005) Aggregate nearest neighbor queries in spatial databases. ACM Trans Database Syst 30(2):529\u2013576","journal-title":"ACM Trans Database Syst"},{"key":"3521_CR8","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":"3521_CR9","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"},{"key":"3521_CR10","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, pp 150\u2013167"},{"key":"3521_CR11","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":"3521_CR12","unstructured":"de Silva V, Tenenbaum JB (2004) Sparse multidimensional scaling using landmark points, Technical report, vol 120, Stanford University"},{"key":"3521_CR13","unstructured":"Ciaccia P, Patella M, Zezula P (Aug. 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"},{"key":"3521_CR14","unstructured":"Borg I, Groenen PJF (2005) Modern multidimensional scaling: theory and applications, 2nd edn. Springer"},{"key":"3521_CR15","unstructured":"Platt J (2005) FastMap, MetricMap, and landmark MDS are all Nystr\u00f6m algorithms. In: Proc. of Int\u2019l Workshop on Artificial Intelligence and Statistics (AISTATS), Bridgetown, Barbados"},{"key":"3521_CR16","doi-asserted-by":"crossref","unstructured":"Ross SM (2014) Introduction to probability and statistics for engineers and scientists, 5th edn. Academic Press","DOI":"10.1016\/B978-0-12-394811-3.50001-0"},{"key":"3521_CR17","unstructured":"Berchtold S, Keim DA, Kriegel H-P (1996) The X-tree: an index structure for high-dimensional data. In: Proc. of the Int\u2019l Conf. on Very Large Data Bases (VLDB), Bombay, India, pp 28\u201339"},{"key":"3521_CR18","doi-asserted-by":"crossref","unstructured":"Abraham I, Delling D, Goldberg AV, Werneck RF (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, May","DOI":"10.1007\/978-3-642-20662-7_20"},{"key":"3521_CR19","doi-asserted-by":"crossref","unstructured":"Akiba T, Iwata Y, Kawarabayashi K, Kawata Y (Jan. 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":"3521_CR20","doi-asserted-by":"crossref","unstructured":"Faloutsos C, Lin K-I (1995) FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets. In: Proc. of ACM Int\u2019l Conf. on Management of Data (SIGMOD), San Jose, California, USA, pp 163\u2013174","DOI":"10.1145\/223784.223812"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03521-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-020-03521-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-020-03521-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T11:02:57Z","timestamp":1611572577000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-020-03521-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,30]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["3521"],"URL":"https:\/\/doi.org\/10.1007\/s11227-020-03521-6","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2020,11,30]]},"assertion":[{"value":"16 November 2020","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2020","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}