Top

Soft Computing

Published in:

26-09-2018 | Focus

An efficient index structure for distributed k-nearest neighbours query processing

Authors: Min Yang, Kun Ma, Xiaohui Yu

Published in: Soft Computing | Issue 8/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Many location-based services are supported by the moving k-nearest neighbour (k-NN) query, which continuously returns the k-nearest data objects for a query point. Most of existing approaches to this problem have focused on a centralized setting, which show poor scalability to work around massive-scale and distributed data sets. In this paper, we propose an efficient distributed solution for k-NN query over moving objects to tackle the increasingly large scale of data. This approach includes a new grid-based index called Block Grid Index (BGI), and a distributed k-NN query algorithm based on BGI. There are three advantages of our approach: (1) BGI can be easily constructed and maintained in a distributed setting; (2) the algorithm is able to return the results set in only two iterations. (3) the efficiency of k-NN query is improved. The efficiency of our solution is verified by extensive experiments with millions of nodes.

previous article Scalable detection of botnets based on DGA

next article Information retrieval methodology for aiding scientific database search

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Ab Malek MSB, Ahmadon MAB, Yamaguchi S, Gupta BB (2016) Implementation of parallel model checking for computer-based test security design. In: International conference on information and communication systems

Alex R, Laio A (2014) Machine learning. Clustering by fast search and find of density peaks. Science 344(6191):1492–1496CrossRef

Bamba B, Liu Ling, Iyengar A, Yu PS (2009) Distributed processing of spatial alarms: a safe region-based approach. In: 29th IEEE international conference on distributed computing systems, 2009. ICDCS ’09, pp 207–214

Cahsai A, Ntarmos N, Anagnostopoulos C, Triantafillou P (2017) Scaling \(k\)-nearest neighbours queries (the right way). In: IEEE international conference on distributed computing systems, pp 1419–1430

Chaudhuri S, Gravano L (1999) Evaluating top-k selection queries. In: VLDB, vol 99, pp 397–410

Eldawy A, Mokbel MF (2013) A demonstration of SpatialHadoop: an efficient mapreduce framework for spatial data. Proc VLDB Endow 6(12):1230–1233CrossRef

Gedik B, Liu L (2004) Mobieyes: distributed processing of continuously moving queries on moving objects in a mobile system. In: EDBT, pp 523–524

Hjaltason GR, Samet H (1999) Distance browsing in spatial databases. ACM Trans Database Syst: TODS 24(2):265–318CrossRef

Lu W, Shen Y, Chen S, Ooi BC (2012) Efficient processing of \(k\) nearest neighbor joins using MapReduce. Proc VLDB Endow 5(10):1016–1027CrossRef

Plageras AP, Stergiou C, Kokkonis G, Psannis KE, Ishibashi Y, Kim BG, Gupta BB (2017) Efficient large-scale medical data (eHealth Big Data) analytics in internet of things. In: Business informatics, pp 21–27

Raptopoulou K, Papadopoulos A, Manolopoulos Y (2003) Fast nearest-neighbor query processing in moving-object databases. GeoInformatica 7(2):113–137CrossRef

Roussopoulos N, Kelley S, Vincent F (1995) Nearest neighbor queries. In: ACM sigmod record, vol 24. ACM, pp 71–79

Seidl T, Kriegel H-P (1998) Optimal multi-step \(k\)-nearest neighbor search. In: ACM SIGMOD record, vol 27. ACM, pp 154–165

Šidlauskas D, Šaltenis S, Jensen CS (2012) Parallel main-memory indexing for moving-object query and update workloads. In: Proceedings of the 2012 ACM SIGMOD international conference on management of data. ACM, pp 37–48

Song Z, Roussopoulos N (2001) \(K\)-nearest neighbor search for moving query point. In: Advances in spatial and temporal databases. Springer, pp 79–96

Tao Y, Papadias D, Shen Q (2002) Continuous nearest neighbor search. In: Proceedings of the 28th international conference on very large data bases. VLDB Endowment, pp 287–298

Tripathi S, Gupta B, Almomani A, Mishra A, Veluru S (2013) Hadoop based defense solution to handle distributed denial of service (DDoS) attacks. J Inf Secur 04(3):150–164

Wang H, Zimmermann R, Ku WS (2006) Distributed continuous range query processing on moving objects. Database and expert systems applications. Springer, Berlin, pp 655–665

Wu W, Guo W, Tan K L (2007) Distributed processing of moving \(k\)-nearest-neighbor query on moving objects. In: 2014 IEEE 30th international conference on data engineering. IEEE, pp 1116–1125

Wu H, Wang L, Jiang T (2018) Secure and efficient \(k\)-nearest neighbor query for location-based services in outsourced environments. Sci China (Inf Sci) 61(3):039101CrossRef

Xia Y, Wang R, Zhang X, Bae H-Y (2017) Grid-based \(k\)-nearest neighbor queries over moving object trajectories with MapReduce. Int J Database Theory Appl 10:1–12CrossRef

Yu C, Ooi BC, Tan K-L, Jagadish H (2001) Indexing the distance: an efficient method to knn processing. In: VLDB, vol 1, pp 421–430

Yu X, Pu KQ, Koudas N (2005) Monitoring \(k\)-nearest neighbor queries over moving objects. In: 21st international conference on data engineering, 2005. ICDE 2005. Proceedings. IEEE, pp 631–642

Yu Z, Liu Y, Yu X, Pu KQ (2015) Scalable distributed processing of \(k\) nearest neighbor queries over moving objects. IEEE Trans Knowl Data Eng 27(5):1383–1396CrossRef

Zhang C, Li F, Jestes J (2012) Efficient parallel kNN joins for large data in MapReduce. In: International Conference on Extending Database Technology, pp 38-49

Zheng B, Xu J, Lee W-C, Lee L (2006) Grid-partition index: a hybrid method for nearest-neighbor queries in wireless location-based services. VLDB J 15(1):21–39CrossRef

Title: An efficient index structure for distributed k-nearest neighbours query processing
Authors: Min Yang
Kun Ma
Xiaohui Yu
Publication date: 26-09-2018
Publisher: Springer Berlin Heidelberg
Published in: Soft Computing / Issue 8/2020
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-018-3548-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 8/2020

Fuzzy Bezier splines with application to fuzzy functional integral equations

A watermarking scheme based on rotating vector for image content authentication

Wajsberg algebras arising from binary block codes

Information retrieval methodology for aiding scientific database search

An improved MPPT control strategy based on incremental conductance method

Optimal control of DAB converter backflow power based on phase-shifting strategy

Premium Partner