基于EMD距离的数据流分布式相似性查询处理关键技术研究

In the era of big data, besides dealing with large volume of data, a more challenging work for data analysis is to cope with fast generating streaming data, since the data generated in many practical applications are time-sensitive. Similarity query over data streams which returns all similar data objects for the query object, is one of the important operations in analyzing and mining streaming data, having been widely used in the applications of duplicated object detection and object classification. The similarity function used in the similarity query is a vital factor affecting the quality of query results. Recent studies have shown that compared to the Lp norms, the Earth Mover’s Distance (EMD) captures the data similarities being more consistent with human similarity perception. However, the computation of EMD suffers from a cubic time complexity, hampering its use in the rapid analysis over data streams. The emergence of novel distributed data stream processing platforms provides a possibility of handling the EMD-based similarity queries in real time. Based on the novel distributed data stream processing platforms, this project conducts research on effective key technologies for distributed similarity queries over data streams based on Earth Mover’s Distance, including EMD-based distributed processing model for data streams, query optimization strategies and system-level optimization mechanisms. This project also tends to build a prototype system for demonstrating the effectiveness and efficiency of the proposed key technologies. As a summary, this project has very important theoretical significance and applied value, inspiring new possibility of achieving real-time processing for other compute-intensive data stream analysis applications.

大数据时代的数据分析不但要应对大数据规模之“大”，更要应对大数据产生之“快”，因为许多实际应用中的数据具有时效性。数据流的相似性查询是数据流分析挖掘的重要操作，能够返回和查询对象相似的流数据对象，被广泛应用于对象去重和分类。相似性度量函数是影响查询结果质量的重要因素。研究表明，相比于Lp范式距离，EMD距离量化的数据相似性更符合人们的直观认识。然而求解EMD距离却具有高达三次方的计算复杂度，阻碍了其在数据流快速分析中的应用。新型分布式数据流处理平台的出现为实时处理基于EMD距离的相似性查询提供了可能。本课题基于新型分布式数据流处理平台，研究高效的基于EMD距离的数据流分布式相似性查询处理关键技术，包括基于EMD距离的数据流分布式处理模型、查询优化策略以及系统优化机制，并结合以上技术实现一个原型系统。本课题具有重要的理论意义和应用价值，可以为其它计算密集型数据流分析应用提供实时处理实施范例。

本项目研究了基于EMD距离的数据流分布式相似性查询处理的关键技术，并实现了相关系统。关键技术包括：基于EMD距离的相似性查询处理系统代价模型、基于EMD距离的数据流分布式查询处理逻辑模型和物理映射模型、基于数据局部性的数据流分组映射机制和查询优化技术、面向分布式计算节点负载均衡的数据流分组映射调整机制、面向EMD距离的数据流分布式存储和索引方法以及分布式计算系统计算资源的动态弹性调整机制。基于真实数据对所提出的关键技术进行评估表明所提出的关键技术使基于EMD距离的数据流分布式相似性查询处理的处理吞吐率比相关分布式处理技术最高提升了1.5倍，并且随着相似性阈值的增大该提升比率还会进一步增大。该项目的研究成果可以广泛应用于基于EMD距离的视频流相似性检测和监控视频流对象跟踪等重要应用场景。该项目的研究成果还具有重要的理论意义，将为一些复杂数据流分析操作（例如聚类）提供分布式并行处理的参考范例，使分布式计算在更好地服务于那些需要保证“时效性”的数据分析应用。