III: Small: Parallel Similarity Comparison and Duplicate Detection with Incremental Computing

全对相似性比较是许多数据密集型挖掘和搜索应用的核心算法之一，如网页间的近重复检测、垃圾邮件检测、广告点击分析、相似新闻/新鲜内容分组、相似产品购买推荐和搜索查询。在大型数据集上进行相似度搜索非常耗时，并且当数据不断更新时变得更具挑战性。开发高性能算法和软件以满足许多使用相似度计算的消费者和商业应用程序中不断增长的速度需求是非常重要的。本课题研究数据周期性或动态更新时的高效且经济的并行算法。开发了在机器集群上划分数据和平衡计算的技术，以优化输入/输出操作、通信和计算资源使用。由于数据经常是不断更新的，利用以前计算的结果来处理更新的数据可以消除大量不必要的操作，并将整个计算过程加快一个数量级。该项目在一组机器上开发高效的软件。该项目从用于网络数据分析和搜索的增量重复检测开始，并继续在其他几个应用程序中进行相似性比较。在这些应用中评估开发软件的性能。这项研究有潜力开发出完全优化的解决方案，大大降低了成本，提高了执行相似性分析的各种大数据应用的速度。开发的软件将提供给应用程序开发人员或数据工程师，以进行大规模计算，而不涉及管理并行性的复杂性。项目网站（http://www.cs.ucsb.edu/projects/psc/）用于发布结果。该教育计划包括研究指导、改善本科生和研究生的教学，以及与高中生一起工作等外展活动。

All-pairs similarity comparison is one of the core algorithms in many data-intensive mining and search applications such as near duplicate detection among web pages, spam detection, advertisement click analysis, similar news/fresh content grouping, and recommendation for similar product purchases and search queries. Conducting similarity search on large datasets is time consuming and becomes more challenging when data are being updated continuously. It is important to develop high performance algorithms and software to meet the increasing speed demands in many consumer and business applications using similarity computation. This project studies efficient and cost-effective parallel algorithms when data are being updated periodically or dynamically. Techniques for partitioning data and balancing computation on a cluster of machines are developed to optimize input/output operations, communication, and computing resource usage. As data are often updated continuously, leveraging previously computed results to handle updated data can eliminate a large amount of unnecessary operations and speedup the entire computation process by an order of magnitude. The project develops efficient software on a cluster of machines. The project starts with incremental duplicate detection for web data analysis and search, and continues to work on similarity comparison in several other applications. Performance of developed software is evaluated in those applications.This research has the potential to develop fully-optimized solutions with significantly reduced cost and increased speed for a variety of big data applications that perform similarity analysis. Developed software will be made available for application developers or data engineers to conduct large-scale computation without involving the complexity of managing parallelism. The project web site (http://www.cs.ucsb.edu/projects/psc/) is used for dissemination of results. The educational plan contains research mentoring, undergraduate and graduate instruction improvement, and outreach activities such as working with high school students.