Decomposable algorithm for computing k-nearest neighbours across partitioned data. Issue 4 (3rd July 2016)

• Record Type: Journal Article
• Authors: Khedr, Ahmed M.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 31:Issue 4(2016)
• Page Start: 334
• Page End: 353
• Publication Date: 2016-07-03
• Subjects: agent -- data privacy -- decomposable algorithm -- k-nearest neighbours -- vertically partitioned data -- horizontally partitioned data; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2015.1057820
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : A common constraint in distributed data is that the database cannot be moved to other network sites due to computational costs, data size, or privacy considerations. All of the existing distributed algorithms for computing k -nearest neighbours ( k -NNs) are designed for horizontally partitioned or special case of vertically partitioned data where different sites contain different attributes for a common set of entities. In this article, we present a framework including a general model and a decomposable algorithm for computing k -NN in d -dimensional space across horizontally and vertically partitioned data in the most general situation in which existing distributed databases want to cooperate for k -NN. The key is to obtain valid results, with a minimum information disclosure. The proposed algorithm preserves the privacy of the data at individual sites by requiring transmission of only minimal information to other sites. The computation is performed by exchanging minimum number of higher level summaries so that even if they are captured by an intruder to actual data tuples can ever be revealed.