Decomposable algorithm for computingk-nearest neighbours across partitioned data
Ahmed M. Khedr · International Journal of Parallel Emergent and Distributed Systems · 2015
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.