{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-7034"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-7034","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"A Comparative Study of Dual-tree Algorithms for Computing Spatial Distance Histogram","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Mou, Chengcheng"],"institution":"University of South Florida","degree_name":"MS in Computer Science (M.S.C.S.)","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Yicheng Tu, Ph.D.","Sagar Pandit, Ph.D.","Yan Zhang, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-01-01T08:00:00Z","date_published":"2015-01-01T08:00:00Z","updated_at":"2026-11-19T08:41:04Z","subjects":["Scientific Databases","Query Processing","Performance","Quad-tree","Oct-tree","k-d tree","Computer Engineering"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/5836","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/5836","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://digitalcommons.usf.edu/do/oai/?verb=GetRecord&metadataPrefix=oai_etdms&identifier=oai%3Adigitalcommons.usf.edu%3Aetd-7034","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yicheng Tu, Ph.D.","Sagar Pandit, Ph.D.","Yan Zhang, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Mou, Chengcheng"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-01-01T08:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science","Computer Science and Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","M.S.C.S."]},{"key":"thesis:degree_name","label":"Degree Name","values":["MS in Computer Science (M.S.C.S.)"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of South Florida"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Scientific Databases","Query Processing","Performance","Quad-tree","Oct-tree","k-d tree","Computer Engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights.license","label":"Dc Rights License","values":["default"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://digitalcommons.usf.edu/etd/5836"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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."]},{"key":"dc:title","label":"Title","values":["A Comparative Study of Dual-tree Algorithms for Computing Spatial Distance Histogram"]}]}],"canonical_facts":{"dc:contributor":["Yicheng Tu, Ph.D.","Sagar Pandit, Ph.D.","Yan Zhang, Ph.D."],"dc:creator":["Mou, Chengcheng"],"dc:date":["2015-01-01T08:00:00Z"],"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."],"dc:identifier":["https://digitalcommons.usf.edu/etd/5836"],"dc:rights.license":["default"],"dc:subject":["Scientific Databases","Query Processing","Performance","Quad-tree","Oct-tree","k-d tree","Computer Engineering"],"dc:title":["A Comparative Study of Dual-tree Algorithms for Computing Spatial Distance Histogram"],"thesis:degree_discipline":["Computer Science","Computer Science and Engineering"],"thesis:degree_level":["Thesis","M.S.C.S."],"thesis:degree_name":["MS in Computer Science (M.S.C.S.)"],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:41:04Z"}