Efficient processing of all-k-nearest-neighbor queries in the MapReduce programming framework.
Saved in:
| Title: | Efficient processing of all-k-nearest-neighbor queries in the MapReduce programming framework. |
|---|---|
| Authors: | Moutafis, Panagiotis1 (AUTHOR) pmoutafis@uth.gr, Mavrommatis, George1 (AUTHOR) gmav@uth.gr, Vassilakopoulos, Michael1 (AUTHOR) mvasilako@uth.gr, Sioutas, Spyros2 (AUTHOR) sioutas@ceid.upatras.gr |
| Source: | Data & Knowledge Engineering. May2019, Vol. 121, p42-70. 29p. |
| Subjects: | Computer network traffic, Distributed computing, Distributed algorithms, Social networks, Quadtrees |
| Abstract: | Numerous modern applications, from social networking to astronomy, need efficient answering of queries on spatial data. One such query is the All k Nearest-Neighbor Query, or k Nearest-Neighbor Join, that takes as input two datasets and, for each object of the first one, returns the k nearest-neighbors from the second one. It is a combination of the k nearest-neighbor and join queries and is computationally demanding. Especially, when the datasets involved fall in the category of Big Data, a single machine cannot efficiently process it. Only in the last few years, papers proposing solutions for distributed computing environments have appeared in the literature. In this paper, we focus on parallel and distributed algorithms using the Apache Hadoop framework. More specifically, we focus on an algorithm that was recently presented in the literature and propose improvements to tackle three major challenges that distributed processing faces: improvement of load balancing (we implement an adaptive partitioning scheme based on Quadtrees), acceleration of local processing (we prune points during calculations by utilizing plane-sweep processing), and reduction of network traffic (we restructure and reduce the output size of the most demanding phase of computation). Moreover, by using real 2D and 3D datasets, we experimentally study the effect of each improvement and their combinations on performance of this literature algorithm. Experiments show that by carefully addressing the three aforementioned issues, one can achieve significantly better performance. Thereby, we conclude to a new scalable algorithm that adapts to the data distribution and significantly outperforms its predecessor. Moreover, we present an experimental comparison of our algorithm against other well-known MapReduce algorithms for the same query and show that these algorithms are also significantly outperformed. [ABSTRACT FROM AUTHOR] |
| Copyright of Data & Knowledge Engineering is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 136867244 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Efficient processing of all-k-nearest-neighbor queries in the MapReduce programming framework. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Moutafis%2C+Panagiotis%22">Moutafis, Panagiotis</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> pmoutafis@uth.gr</i><br /><searchLink fieldCode="AR" term="%22Mavrommatis%2C+George%22">Mavrommatis, George</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> gmav@uth.gr</i><br /><searchLink fieldCode="AR" term="%22Vassilakopoulos%2C+Michael%22">Vassilakopoulos, Michael</searchLink><relatesTo>1</relatesTo> (AUTHOR)<i> mvasilako@uth.gr</i><br /><searchLink fieldCode="AR" term="%22Sioutas%2C+Spyros%22">Sioutas, Spyros</searchLink><relatesTo>2</relatesTo> (AUTHOR)<i> sioutas@ceid.upatras.gr</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Data+%26+Knowledge+Engineering%22">Data & Knowledge Engineering</searchLink>. May2019, Vol. 121, p42-70. 29p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computer+network+traffic%22">Computer network traffic</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+computing%22">Distributed computing</searchLink><br /><searchLink fieldCode="DE" term="%22Distributed+algorithms%22">Distributed algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Social+networks%22">Social networks</searchLink><br /><searchLink fieldCode="DE" term="%22Quadtrees%22">Quadtrees</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Numerous modern applications, from social networking to astronomy, need efficient answering of queries on spatial data. One such query is the All k Nearest-Neighbor Query, or k Nearest-Neighbor Join, that takes as input two datasets and, for each object of the first one, returns the k nearest-neighbors from the second one. It is a combination of the k nearest-neighbor and join queries and is computationally demanding. Especially, when the datasets involved fall in the category of Big Data, a single machine cannot efficiently process it. Only in the last few years, papers proposing solutions for distributed computing environments have appeared in the literature. In this paper, we focus on parallel and distributed algorithms using the Apache Hadoop framework. More specifically, we focus on an algorithm that was recently presented in the literature and propose improvements to tackle three major challenges that distributed processing faces: improvement of load balancing (we implement an adaptive partitioning scheme based on Quadtrees), acceleration of local processing (we prune points during calculations by utilizing plane-sweep processing), and reduction of network traffic (we restructure and reduce the output size of the most demanding phase of computation). Moreover, by using real 2D and 3D datasets, we experimentally study the effect of each improvement and their combinations on performance of this literature algorithm. Experiments show that by carefully addressing the three aforementioned issues, one can achieve significantly better performance. Thereby, we conclude to a new scalable algorithm that adapts to the data distribution and significantly outperforms its predecessor. Moreover, we present an experimental comparison of our algorithm against other well-known MapReduce algorithms for the same query and show that these algorithms are also significantly outperformed. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Data & Knowledge Engineering is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=136867244 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1016/j.datak.2019.04.003 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 29 StartPage: 42 Subjects: – SubjectFull: Computer network traffic Type: general – SubjectFull: Distributed computing Type: general – SubjectFull: Distributed algorithms Type: general – SubjectFull: Social networks Type: general – SubjectFull: Quadtrees Type: general Titles: – TitleFull: Efficient processing of all-k-nearest-neighbor queries in the MapReduce programming framework. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Moutafis, Panagiotis – PersonEntity: Name: NameFull: Mavrommatis, George – PersonEntity: Name: NameFull: Vassilakopoulos, Michael – PersonEntity: Name: NameFull: Sioutas, Spyros IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 05 Text: May2019 Type: published Y: 2019 Identifiers: – Type: issn-print Value: 0169023X Numbering: – Type: volume Value: 121 Titles: – TitleFull: Data & Knowledge Engineering Type: main |
| ResultId | 1 |
