Performance analysis of a dual-tree algorithm for computing spatial distance histograms
- 28 October 2010
- journal article
- research article
- Published by Springer Nature in The VLDB Journal
- Vol. 20 (4) , 471-494
Abstract
Many scientific and engineering fields produce large volume of spatiotemporal data. The storage, retrieval, and analysis of such data impose great challenges to database systems design. Analysis of scientific spatiotemporal data often involves computing functions of all point-to-point interactions. One such analytics, the Spatial Distance Histogram (SDH), is of vital importance to scientific discovery. Recently, algorithms for efficient SDH processing in large-scale scientific databases have been proposed. These algorithms adopt a recursive tree-traversing strategy to process point-to-point distances in the visited tree nodes in batches, thus require less time when compared to the brute-force approach where all pairwise distances have to be computed. Despite the promising experimental results, the complexity of such algorithms has not been thoroughly studied. In this paper, we present an analysis of such algorithms based on a geometric modeling approach. The main technique is to transform the analysis of point counts into a problem of quantifying the area of regions where pairwise distances can be processed in batches by the algorithm. From the analysis, we conclude that the number of pairwise distances that are left to be processed decreases exponentially with more levels of the tree visited. This leads to the proof of a time complexity lower than the quadratic time needed for a brute-force algorithm and builds the foundation for a constant-time approximate algorithm. Our model is also general in that it works for a wide range of point spatial distributions, histogram types, and space-partitioning options in building the tree.Keywords
This publication has 30 references indexed in Scilit:
- Covariant Evolutionary Event Analysis for Base Interaction Prediction Using a Relational Database Management System for RNA2009
- GROMACS 4: Algorithms for Highly Efficient, Load-Balanced, and Scalable Molecular SimulationJournal of Chemical Theory and Computation, 2008
- Analysis of predictive spatio-temporal queriesACM Transactions on Database Systems, 2003
- The Role of Declarative Querying in BioinformaticsOMICS: A Journal of Integrative Biology, 2003
- Scalable I/O of large-scale molecular dynamics simulations: A data-compression algorithmComputer Physics Communications, 2000
- Measuring High‐Order Moments of the Galaxy Distribution from Counts in Cells: The Edgeworth ApproximationThe Astrophysical Journal, 1998
- The radial distribution function probed by X-ray absorption spectroscopyJournal of Physics: Condensed Matter, 1994
- Introduction to AlgorithmsJournal of the Operational Research Society, 1991
- Computer Simulation of Liquids.Mathematics of Computation, 1991
- The Quadtree and Related Hierarchical Data StructuresACM Computing Surveys, 1984