A Comparative Study of Dual-Tree Algorithms for Computing Spatial Distance Histograms. (17th March 2018)

• Record Type: Journal Article
• Authors: Mou, Chengcheng; Chen, Shaoping; Tu, Yi-Cheng
• Editors: Bhandarkar, Suchi
• Is Part Of: Computer journal. Volume 62:Number 1(2019)
• Page Start: 42
• Page End: 62
• Publication Date: 2018-03-17
• Subjects: scientific databases -- query processing -- spatial distance histogram -- performance -- quad-tree -- oct-tree -- kd-tree; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxy017
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The 2-body correlation function (2-BCF) is a group of statistical measurements that found applications in many scientific domains. One type of 2-BCF named the Spatial Distance Histogram (SDH) is of vital importance in describing the physical features of natural systems. While a naïve way of computing SDH requires quadratical time, efficient algorithms based on resolving nodes in spatial trees have been developed. A key decision in the design of such algorithms is to choose a proper underlying data structure: our previous work utilizes quad-tree (oct-tree for 3D data) and, in this paper, we study a kd-tree-based solution. Although it is easy to see that both implementations have the same time complexityO ( N 2 d − 1 d ), where d is the number of dimensions of the dataset, a thorough comparison of their actual running time under different scenarios is conducted. In particular, we present an analytical model to rigorously quantify the running time of dual-tree algorithms. Our analysis suggests that the kd-tree-based implementation outperforms the quad-/oct-tree solution under a wide range of data sizes and query parameters. Specifically, such performance advantage is shown as a speedup up to 1.23× over the quad-tree algorithm for 2D data, and 1.39× over the oct-tree for 3D data, respectively. Results of extensive experiments run on synthetic and real datasets confirm our findings.