{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T22:45:06Z","timestamp":1745621106451,"version":"3.37.3"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T00:00:00Z","timestamp":1657929600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["18K18057"],"award-info":[{"award-number":["18K18057"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100009023","name":"Precursory Research for Embryonic Science and Technology","doi-asserted-by":"crossref","award":["JPMJPR2033"],"award-info":[{"award-number":["JPMJPR2033"]}],"id":[{"id":"10.13039\/501100009023","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The <jats:italic>k<\/jats:italic> nearest neighbor (<jats:italic>k<\/jats:italic>NN) query is an essential graph data-management tool used for finding relevant data entities suited to a user-specified query node. Graph indexing methods have the potential to achieve a quick <jats:italic>k<\/jats:italic>NN search response and thus are promising approaches. However, they struggle to handle large-scale attributed complex networks. This is because constructing indices and querying <jats:italic>k<\/jats:italic>NN nodes in large-scale networks are computationally expensive, and they are not designed to handle node attributes included in the networks. In this paper, we propose a novel graph indexing algorithm, namely <jats:italic>CT<\/jats:italic> index, for fast <jats:italic>k<\/jats:italic>NN queries on large complex networks. To overcome the aforementioned limitations, our algorithm generates two types of indices based on the topological properties of complex networks. In addition, we further propose <jats:italic>BAG<\/jats:italic> index along with CT index so that our algorithm enables to explore <jats:italic>k<\/jats:italic>NN nodes based on the attribute similarity. Our extensive experiments on real-world graphs show that our algorithm achieves up to 18,074 times faster indexing and 146 times faster <jats:italic>k<\/jats:italic>NN query than other state-of-the-art methods.<\/jats:p>","DOI":"10.1007\/s13278-022-00904-w","type":"journal-article","created":{"date-parts":[[2022,7,16]],"date-time":"2022-07-16T11:02:54Z","timestamp":1657969374000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Indexing complex networks for fast attributed kNN queries"],"prefix":"10.1007","volume":"12","author":[{"given":"Suomi","family":"Kobayashi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shohei","family":"Matsugu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8530-2651","authenticated-orcid":false,"given":"Hiroaki","family":"Shiokawa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,16]]},"reference":[{"key":"904_CR1","doi-asserted-by":"crossref","unstructured":"Abeywickrama, T., Cheema, M.A.: Efficient Landmark-Based Candidate Generation for kNN Queries on Road Networks. In: Proceedings of the 22nd International Conference on database systems for advanced applications (DASFAA 2017), pp. 425\u2013440 (2017)","DOI":"10.1007\/978-3-319-55699-4_26"},{"key":"904_CR2","doi-asserted-by":"publisher","unstructured":"Alom Z, Carminati B, Ferrari E (2018) Detecting Spam Accounts on Twitter. In: 2018 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2018), pp. 1191\u20131198. https:\/\/doi.org\/10.1109\/ASONAM.2018.8508495","DOI":"10.1109\/ASONAM.2018.8508495"},{"key":"904_CR3","doi-asserted-by":"crossref","unstructured":"Asghari M, Deng D, Shahabi C, Demiryurek U, Li Y (2016) Price-Aware Real-Time Ride-Sharing at Scale: An Auction-Based Approach. In: Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL 2016)","DOI":"10.1145\/2996913.2996974"},{"key":"904_CR4","doi-asserted-by":"publisher","unstructured":"Bast H, Funke S, Matijevic D (2006) Ultrafast Shortest-Path Queries via Transit Nodes. In: Proceedings of a DIMACS Workshop of The Shortest Path Problem, vol. 74, pp. 175\u2013192. https:\/\/doi.org\/10.1090\/dimacs\/074\/07","DOI":"10.1090\/dimacs\/074\/07"},{"key":"904_CR5","doi-asserted-by":"crossref","unstructured":"Benson A, Kleinberg J (2019) Link Prediction in Networks with Core-Fringe Data. In: Proceedings of The Web Conference 2019 (WWW 2019), pp. 94\u2013104","DOI":"10.1145\/3308558.3313626"},{"issue":"11","key":"904_CR6","doi-asserted-by":"publisher","first-page":"777","DOI":"10.1080\/08839514.2020.1782002","volume":"34","author":"EK Boahen","year":"2020","unstructured":"Boahen EK, Changda W, Elvire BB (2020) Detection of compromised online social network account with an enhanced knn. Appl Artif Intell 34(11):777\u2013791. https:\/\/doi.org\/10.1080\/08839514.2020.1782002","journal-title":"Appl Artif Intell"},{"issue":"2","key":"904_CR7","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/3292390.3292394","volume":"10","author":"MA Cheema","year":"2018","unstructured":"Cheema MA (2018) Indoor location-based services: challenges and opportunities. SIGSPATIAL Special 10(2):10\u201317","journal-title":"SIGSPATIAL Special"},{"key":"904_CR8","doi-asserted-by":"crossref","unstructured":"Chen J-S, Huang H-Y, Hsu C-Y (2020) A knn based position prediction method for sns places. In: Proceedings of the 12th Asian Conference on intelligent information and database systems (ACIIDS 2020), pp. 266\u2013273","DOI":"10.1007\/978-3-030-42058-1_22"},{"key":"904_CR9","doi-asserted-by":"crossref","unstructured":"Chen Z, Shen HT, Zhou X (2011) Discovering Popular Routes from Trajectories. In: Proceedings of the 2011 IEEE 27th International Conference on data engineering (ICDE 2011), pp. 900\u2013911","DOI":"10.1109\/ICDE.2011.5767890"},{"key":"904_CR10","doi-asserted-by":"publisher","unstructured":"Chen Z, Li P, Xiao J, Nie L, Liu Y (2020) An Order Dispatch System Based on Reinforcement Learning for Ride Sharing Services. In: Proceedings of 2020 IEEE 22nd International Conference on High Performance Computing and Communications; IEEE 18th International Conference on Smart City; IEEE 6th International Conference on Data Science and Systems (HPCC\/SmartCity\/DSS), pp. 758\u2013763. https:\/\/doi.org\/10.1109\/HPCC-SmartCity-DSS50907.2020.00099","DOI":"10.1109\/HPCC-SmartCity-DSS50907.2020.00099"},{"key":"904_CR11","unstructured":"Demetrescu C (2010) The 9th DIMACS Implementation Challenge. http:\/\/users.diag.uniroma1.it\/challenge9\/download.shtml"},{"key":"904_CR12","doi-asserted-by":"crossref","unstructured":"Geisberger R, Sanders P, Schultes D, Delling D (2008) Contraction hierarchies: faster and simpler hierarchical routing in road networks. In: Experimental Algorithms, pp. 319\u2013333","DOI":"10.1007\/978-3-540-68552-4_24"},{"key":"904_CR13","unstructured":"Goldberg AV, Harrelson C (2005) Computing the Shortest Path: A Search Meets Graph Theory. In: Proceedings of the sixteenth annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 156\u2013165"},{"key":"904_CR14","doi-asserted-by":"publisher","DOI":"10.1145\/2827872","author":"FM Harper","year":"2015","unstructured":"Harper FM, Konstan JA (2015) The movielens datasets: history and context. ACM Trans Interact Intell Syst. https:\/\/doi.org\/10.1145\/2827872","journal-title":"ACM Trans Interact Intell Syst"},{"key":"904_CR15","doi-asserted-by":"crossref","unstructured":"Huang, X., Jensen, C.S., Saltenis, S.: Multiple k Nearest Neighbor Query Processing in Spatial Network Databases. In: Proceedings of the 10th East European Conference on advances in databases and information systems (ADBIS 2006), pp. 266\u2013281 (2006)","DOI":"10.1007\/11827252_21"},{"issue":"3","key":"904_CR16","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1109\/69.687976","volume":"10","author":"N Jing","year":"1998","unstructured":"Jing N, Huang Y-W, Rundensteiner EA (1998) Hierarchical encoded path views for path query processing: an optimal model and its performance evaluation. IEEE Trans Know Data Eng 10(3):409\u2013432. https:\/\/doi.org\/10.1109\/69.687976","journal-title":"IEEE Trans Know Data Eng"},{"issue":"5","key":"904_CR17","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1109\/TKDE.2002.1033772","volume":"14","author":"S Jung","year":"2002","unstructured":"Jung S, Pramanik S (2002) An efficient path computation model for hierarchically structured topographical road maps. IEEE Trans Knowl Data Eng 14(5):1029\u20131046. https:\/\/doi.org\/10.1109\/TKDE.2002.1033772","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"904_CR18","doi-asserted-by":"crossref","unstructured":"Karypis G, Kumar V (1995) Analysis of Multilevel Graph Partitioning. In: Proceedings of the IEEE\/ACM SC95 Conference (SC 1995)","DOI":"10.1145\/224170.224229"},{"key":"904_CR19","doi-asserted-by":"publisher","unstructured":"Kesarwani A, Chauhan SS, Nair AR (2020) Fake News Detection on Social Media using K-Nearest Neighbor Classifier. In: 2020 International Conference on Advances in Computing and Communication Engineering (ICACCE), pp. 1\u20134. https:\/\/doi.org\/10.1109\/ICACCE49060.2020.9154997","DOI":"10.1109\/ICACCE49060.2020.9154997"},{"key":"904_CR20","unstructured":"Kobayashi S, Matsugu S, Shiokawa H (2021) Fast Indexing Algorithm for Efficient kNN Queries on Complex Networks. In: Proceedings of the 2021 IEEE\/ACM International Conference on advances in social networks analysis and mining (ASONAM 2021), pp. 343\u2013347"},{"key":"904_CR21","doi-asserted-by":"publisher","unstructured":"Ko\u00e7ak Y, \u00d6zyer T, Alhajj R (2016) Classification of HIV Data by Constructing a Social Network with Frequent Itemsets. In: 2016 IEEE\/ACM International Conference on advances in social networks analysis and mining (ASONAM 2016), pp. 949\u2013953. https:\/\/doi.org\/10.1109\/ASONAM.2016.7752354","DOI":"10.1109\/ASONAM.2016.7752354"},{"key":"904_CR22","first-page":"545","volume":"3","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 on Knowl Data Eng 3:545\u2013560","journal-title":"IEEE Trans on Knowl Data Eng"},{"key":"904_CR23","unstructured":"Leskovec J, Krevl A (2014) SNAP Datasets: stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"key":"904_CR24","doi-asserted-by":"crossref","unstructured":"Li H, Zhang Q, Lu K (2015) Integrating Mobile Sensing and Social Network for Personalized Health-Care Application. In: Proceedings of the 30th Annual ACM Symposium on applied computing (SAC 2015), pp. 527\u2013534","DOI":"10.1145\/2695664.2695767"},{"key":"904_CR25","doi-asserted-by":"crossref","unstructured":"Li Z, Chen L, Wang Y (2019) G*-Tree: An Efficient Spatial Index on Road Networks. In: Proceedings of the 35th IEEE international conference on data engineering (ICDE 2019), pp. 268\u2013279","DOI":"10.1109\/ICDE.2019.00032"},{"key":"904_CR26","unstructured":"Ma S, Zheng Y, Wolfson O (2013) T-share: A Large-scale Dynamic Taxi Ridesharing Service. In: Proceedings of 2013 IEEE 29th International Conference on Data Engineering (ICDE 2013), pp. 410\u2013421"},{"key":"904_CR27","doi-asserted-by":"publisher","unstructured":"Maehara, T., Akiba, T., Iwata, Y., Kawarabayashi, K.: Computing Personalized PageRank Quickly by Exploiting Graph Structures. In: Proceedings of VLDB Endowment (PVLDB) 7(12), 1023\u20131034 (2014). https:\/\/doi.org\/10.14778\/2732977.2732978","DOI":"10.14778\/2732977.2732978"},{"key":"904_CR28","first-page":"188","volume":"29","author":"S Matsugu","year":"2021","unstructured":"Matsugu S, Shiokawa H, Kitagawa H (2021) Fast algorithm for attributed community search. J Inf Process 29:188\u2013196","journal-title":"J Inf Process"},{"key":"904_CR29","doi-asserted-by":"crossref","unstructured":"Matsugu, S., Shiokawa, H., Kitagawa, H.: Fast and Accurate Community Search Algorithm for Attributed Graphs. In: Proceedings of the 31st International Conference on database and expert systems applications (DEXA 2020), pp. 233\u2013249 (2020)","DOI":"10.1007\/978-3-030-59003-1_16"},{"key":"904_CR30","doi-asserted-by":"publisher","unstructured":"Mei S, Li H, Fan J, Zhu X, Dyer CR (2014) Inferring air pollution by sniffing social media. In: 2014 IEEE\/ACM International Conference on advances in social networks analysis and mining (ASONAM 2014), pp. 534\u2013539. https:\/\/doi.org\/10.1109\/ASONAM.2014.6921638","DOI":"10.1109\/ASONAM.2014.6921638"},{"key":"904_CR31","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.knosys.2016.09.004","volume":"112","author":"M Ni","year":"2016","unstructured":"Ni M, Li T, Li Q, Zhang H, Ye Y (2016) FindMal: a file-to-file social network based malware detection framework. Knowl Based Syst 112:142\u2013151. https:\/\/doi.org\/10.1016\/j.knosys.2016.09.004","journal-title":"Knowl Based Syst"},{"key":"904_CR32","doi-asserted-by":"crossref","unstructured":"Okabe A, Boots B, Sugihara K, Chiu SN (2000) Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd edn. Series in Probability and Statistics. John Wiley and Sons, Inc., 605 Third Ave. New York, NY, United States","DOI":"10.1002\/9780470317013"},{"issue":"1","key":"904_CR33","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s41019-017-0034-4","volume":"2","author":"M Onizuka","year":"2017","unstructured":"Onizuka M, Fujimori T, Shiokawa H (2017) Graph partitioning for distributed graph processing. Data Sci Eng 2(1):94\u2013105. https:\/\/doi.org\/10.1007\/s41019-017-0034-4","journal-title":"Data Sci Eng"},{"key":"904_CR34","doi-asserted-by":"crossref","unstructured":"Samet H, Sankaranarayanan J, Alborzi H (2008) Scalable Network Distance Browsing in Spatial Databases. In: Proceedings of the 2008 ACM SIGMOD International Conference on management of data (SIGMOD), pp. 43\u201354","DOI":"10.1145\/1376616.1376623"},{"key":"904_CR35","doi-asserted-by":"crossref","unstructured":"Samet H, Sankaranarayanan J, Alborzi H (2008) Scalable Network Distance Browsing in Spatial Databases. In: Proceedings of the 2008 ACM SIGMOD international conference on management of data (SIGMOD), pp. 43\u201354","DOI":"10.1145\/1376616.1376623"},{"key":"904_CR36","doi-asserted-by":"publisher","unstructured":"Sankaranarayanan J, Samet H, Alborzi H (2009) Path oracles for spatial networks. In: Proceedings of VLDB Endowment (PVLDB) 2(1):1210\u20131221. https:\/\/doi.org\/10.14778\/1687627.1687763","DOI":"10.14778\/1687627.1687763"},{"issue":"1","key":"904_CR37","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1109\/TNET.2007.899021","volume":"16","author":"Y Shavitt","year":"2008","unstructured":"Shavitt Y, Tankel T (2008) Hyperbolic embedding of internet graph for distance estimation and overlay construction. IEEE\/ACM Trans Netw 16(1):25\u201336","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"11","key":"904_CR38","first-page":"9639","volume":"35","author":"H Shiokawa","year":"2021","unstructured":"Shiokawa H (2021) Scalable affinity propagation for massive datasets. Proce AAAI Conf Artif Intell (AAAI 2021) 35(11):9639\u20139646","journal-title":"Proce AAAI Conf Artif Intell (AAAI 2021)"},{"issue":"11","key":"904_CR39","first-page":"1178","volume":"8","author":"H Shiokawa","year":"2015","unstructured":"Shiokawa H, Fujiwara Y, Onizuka M (2015) SCAN++: efficient algorithm for finding clusters, hubs and outliers on large-scale graphs. PVLDB 8(11):1178\u20131189","journal-title":"PVLDB"},{"key":"904_CR40","doi-asserted-by":"crossref","unstructured":"Shiokawa, H.: Fast ObjectRank for Large Knowledge Databases. In: Proceedings of the 20th International Semantic Web Conference (ISWC 2021) (2021)","DOI":"10.1007\/978-3-030-88361-4_13"},{"key":"904_CR41","doi-asserted-by":"crossref","unstructured":"Shiokawa H, Amagasa T, Kitagawa H (2019) Scaling Fine-grained Modularity Clustering for Massive Graphs. In: Proceedings of the Twenty-Eighth international joint conference on artificial intelligence (IJCAI 2019), pp. 4597\u20134604","DOI":"10.24963\/ijcai.2019\/639"},{"key":"904_CR42","doi-asserted-by":"crossref","unstructured":"Shiokawa H, Fujiwra Y, Onizuka M (2013) Fast Algorithm for Modularity-based Graph Clustering. In: Proceedings of the 27th AAAI Conference on artificial intelligence (AAAI 2013), pp. 1170\u20131176","DOI":"10.1609\/aaai.v27i1.8455"},{"key":"904_CR43","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.ins.2016.02.011","volume":"348","author":"D Song","year":"2016","unstructured":"Song D, Park K (2016) A partial index for distributed broadcasting in wireless mobile networks. Inf Sci 348:142\u2013152","journal-title":"Inf Sci"},{"issue":"2","key":"904_CR44","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1109\/TKDE.2017.2760880","volume":"30","author":"N Ta","year":"2018","unstructured":"Ta N, Li G, Zhao T, Feng J, Ma H, Gong Z (2018) An efficient ride-sharing framework for maximizing shared route. IEEE Trans Knowl Data Eng 30(2):219\u2013233","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"904_CR45","doi-asserted-by":"crossref","unstructured":"Wang, J., Anirban, S., Amagasa, T., Shiokawa, H., Gong, Z., Islam, M.S.: A Hybrid Index for Distance Queries. In: Proceedings of the 21st International Conference on web information systems engineering (WISE 2020), pp. 227\u2013241 (2020)","DOI":"10.1007\/978-3-030-62005-9_17"},{"key":"904_CR46","doi-asserted-by":"publisher","unstructured":"Xu X, Yuruk N, Feng Z, Schweiger TAJ (2007) SCAN: A Structural Clustering Algorithm for Networks. In: Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD 2007), pp. 824\u2013833. https:\/\/doi.org\/10.1145\/1281192.1281280","DOI":"10.1145\/1281192.1281280"},{"issue":"4","key":"904_CR47","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1109\/TDSC.2016.2626288","volume":"15","author":"K Zhang","year":"2018","unstructured":"Zhang K, Liang X, Ni J, Yang K, Shen X (2018) Exploiting social network to enhance human-to-human infection analysis without privacy leakage. IEEE Trans Depend Secure Comput 15(4):607\u2013620. https:\/\/doi.org\/10.1109\/TDSC.2016.2626288","journal-title":"IEEE Trans Depend Secure Comput"},{"issue":"8","key":"904_CR48","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-L, Zhou L, Gong Z (2015) G-Tree: an efficient and scalable index for spatial search on road networks. IEEE Trans Knowl Data Eng 27(8):2175\u20132189","journal-title":"IEEE Trans Knowl Data Eng"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-022-00904-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-022-00904-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-022-00904-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T14:13:45Z","timestamp":1672668825000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-022-00904-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,16]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["904"],"URL":"https:\/\/doi.org\/10.1007\/s13278-022-00904-w","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"type":"print","value":"1869-5450"},{"type":"electronic","value":"1869-5469"}],"subject":[],"published":{"date-parts":[[2022,7,16]]},"assertion":[{"value":"13 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"82"}}