Abstract:In recent years, multimedia data has become one of the major data types transferred and processed on the Internet. K dimensional tree is one of the most popular tree structures for searches involving a multidimensional search key, which is similar to feature points extracted from multimedia data, due to its good accuracy, scalability and fast retrieval speed. However, its slow building speed limits its application area, especially with large dataset. Fortunately, Modern processors provide tremendous computing power by integrating multiple or many cores. In this paper, we explore and analyze the existing potential parallel in KD-Tree building process. Then we present ParK, a customized parallel solution that exploits multi-core CPUs to accelerate KD-Tree building process. ParK exploits different parallel models to fully utilize computation resource in modern hardware and solves data race by presenting a new memory allocation strategy. The final experimental results show ParK achieves about 21.75X speedup compared to original serial version on 16-core server.