SI2-SSE: Scalable Big Data Clustering by Random Projection Hashing

本项目计划开发一种分布式算法，用于高维数据集的安全聚类。数据聚类的可扩展性使健康和生物学领域受益匪浅。诸如微阵列聚类、蛋白质-蛋白质相互作用聚类、医疗资源决策、医学图像处理和流行病学事件聚类等生物信息学问题都将受益于更大的数据集规模。正在开发的算法，称为随机投影哈希或RPHash，利用局域敏感哈希（LSH）和多探针随机投影方面的计算可扩展性和线性可实现的并行速度增益。此外，RPHash通过对数据进行破坏性操作来提供数据匿名化，从而防止超出标准最佳实践数据库安全方法的去匿名化攻击。RPHash将部署在运行MapReduce的Hadoop （MRv2）实现的商业可用云资源上。通用云处理解决方案的开发允许研究人员使用几乎无限的商业处理资源来扩展他们的处理需求。RPHash算法使用了数据挖掘中的各种最新技术以及在分布式系统上实现算法可伸缩性的新方法。RPHash的基本思路是将多探针随机投影与离散空间量化相结合。然后将高密度区域视为质心候选区域。为了遵循常见的参数化k-means方法，将选择最上面的k个区域。对随机的、因此不确定的聚类算法的关注在计算中有些不常见，但在不适定的、组合限制性的问题（如聚类和分区）中很常见。尽管理论结果表明k-means具有指数级的最坏情况复杂度，但在k-means和其他类似算法下，许多现实世界的问题往往会得到更好的解决。

This project plans to develop a distributed algorithm for secure clustering of high dimensional data sets. Fields in health and biology are significantly benefited by data clustering scalability. Bioinformatic problems such as Micro Array clustering, Protein-Protein interaction clustering, medical resource decision making, medical image processing, and clustering of epidemiological events all serve to benefit from larger dataset sizes. The algorithm under development, called Random Projection Hash or RPHash, utilizes aspects of locality sensitive hashing (LSH) and multi-probe random projection for computational scalability and linear achievable gains from parallel speed. Furthermore, RPHash provides data anonymization through destructive manipulation of the data preventing de-anonymization attacks beyond standard best practices database security methods. RPHash will be deployable on commercially available cloud resources running the Hadoop (MRv2) implementation of MapReduce. The exploitation of general purpose cloud processing solutions allows researchers to scale their processing needs using virtually limitless commercial processing resources.The RPHash algorithm uses various recent techniques in data mining along with a new approach toward achieving algorithmic scalability on distributed systems. The basic intuition of RPHash is to combine multi-probe random projection with discrete space quantization. Regions of high density are then regarded as centroid candidates. To follow common parameterized, k-means methods, the top k regions will be selected. The focus on a randomized, and thus non-deterministic, clustering algorithm is somewhat uncommon in computing, but common for ill-posed, combinatorially restrictive problems such as clustering and partitioning. Despite theoretical results showing that k-means has an exponential worst case complexity, many real world problems tend to fair much better under k-means and other similar algorithms.