Back to search

University of South Florida

A Comparative Study of Dual-tree Algorithms for Computing Spatial Distance Histogram

Abstract

dc:description

Particle simulation has become an important research technique in many scientific and engineering fields in latest years. However, these simulations will generate countless data, and database they required would therefore deal with very challenging tasks in terms of data management, storage, and query processing. The two-body correlation function (2-BCFs), a statistical learning measurement to evaluate the datasets, has been mainly utilized to measure the spatial distance histogram (SDH). By using a straightforward method, the process of SDH query takes quadratic time. Recently, a novel algorithm has been proposed to compute the SDH based on the concept of density map (DM), and it reduces the running time to ϴ(N(3/2)) for two-dimensional data and ϴ (N(5/3) ) for three-dimensional data, respectively. In the DM-SDH algorithm, there are two types of DMs that can be plugged in for computation: Quad-tree (Oct-tree for three-dimensional data) and k-d tree data structure. In this thesis paper, by using the geometric method, we prove the unre- solvable ratios on the k-d tree. Further, we analyze and compare the difference in the performance in each potential case generated by these DM-SDH algorithms. Experimental results confirm our analysis and show that the k-d tree structure has better performance in terms of time complexity in all cases. However, our qualitative analysis shows that the Quad-tree (Oct-tree) has an advantage over the k-d tree on aspect of space complexity.

Degree

thesis:*
Name thesis:degree_name
MS in Computer Science (M.S.C.S.)
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Computer Science
Grantor
University of South Florida
Year dc:date
2015

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Mou, Chengcheng
Contributors dc:contributor
  • Yicheng Tu, Ph.D.
  • Sagar Pandit, Ph.D.
  • Yan Zhang, Ph.D.

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/5836

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Mou, Chengcheng. A Comparative Study of Dual-tree Algorithms for Computing Spatial Distance Histogram. Thesis thesis, University of South Florida, 2015. https://digitalcommons.usf.edu/etd/5836