{"id":{"repo_id":"usf","oai_identifier":"oai:digitalcommons.usf.edu:etd-1015"},"canonical_url":"https://search.ndltd.org/etd/usf/oai:digitalcommons.usf.edu:etd-1015","repository":{"repo_id":"usf","name":"University of South Florida","base_url":"https://digitalcommons.usf.edu/do/oai/"},"display":{"title":"Performance Analysis of a Binary-Tree-Based Algorithm for Computing Spatial Distance Histograms","abstract":"The environment is made up of composition of small particles. Hence, particle simulation is an important tool in many scientific and engineering research fields to simulate the real life processes of the environment. Because of the enormous amount of data in such simulations, data management, storage and processing are very challenging tasks. Spatial Distance Histogram (SDH) is one of the most popular queries being used in this field. In this thesis, we are interested in investigating the performance of improvement of an existing algorithm for computing SDH. The algorithm already being used is using a conceptual data structure called density map which is implemented via a quad tree index. An algorithm having density maps implemented via binary tree is proposed in this thesis. After carrying out many experiments and analysis of the data, we figure out that although the binary tree approach seems efficient in earlier stage, it is same as the quad tree approach in terms of time complexity. However, it provides an improvement in computing time by a constant factor for some data inputs. The second part of this thesis is dedicated to an approach that can potentially reduce the computational time to a great extent by taking advantage of regions where data points are uniformly distributed.","abstract_html":"The environment is made up of composition of small particles. Hence, particle simulation is an important tool in many scientific and engineering research fields to simulate the real life processes of the environment. Because of the enormous amount of data in such simulations, data management, storage and processing are very challenging tasks. Spatial Distance Histogram (SDH) is one of the most popular queries being used in this field. In this thesis, we are interested in investigating the performance of improvement of an existing algorithm for computing SDH. The algorithm already being used is using a conceptual data structure called density map which is implemented via a quad tree index. An algorithm having density maps implemented via binary tree is proposed in this thesis. After carrying out many experiments and analysis of the data, we figure out that although the binary tree approach seems efficient in earlier stage, it is same as the quad tree approach in terms of time complexity. However, it provides an improvement in computing time by a constant factor for some data inputs. The second part of this thesis is dedicated to an approach that can potentially reduce the computational time to a great extent by taking advantage of regions where data points are uniformly distributed.","abstract_has_math":false,"creators":["Sharma Luetel, Sadhana"],"institution":"University of South Florida","degree_name":null,"degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Yicheng Tu, Ph.D.","Rafael Perez, Ph.D.","Rahul Tripathi, Ph.D.","Sagar Pandit, Ph.D."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2009,"date_issued":"2009-10-30T07:00:00Z","date_published":"2009-10-30T07:00:00Z","updated_at":"2026-11-19T08:32:57Z","subjects":["Spatial Distance Histogram","Particle Distance Histogram","Quad-tree","Binary tree","Uniformity","American Studies","Arts and Humanities"],"languages":["EN-US"],"rights":[],"rights_urls":[],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://digitalcommons.usf.edu/etd/16","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://digitalcommons.usf.edu/etd/16","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-1015","prefix":"oai_etdms"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Yicheng Tu, Ph.D.","Rafael Perez, Ph.D.","Rahul Tripathi, Ph.D.","Sagar Pandit, Ph.D."]},{"key":"dc:creator","label":"Author","values":["Sharma Luetel, Sadhana"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2009-10-30T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis","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":["Spatial Distance Histogram","Particle Distance Histogram","Quad-tree","Binary tree","Uniformity","American Studies","Arts and Humanities"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["EN-US"]},{"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/16"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["The environment is made up of composition of small particles. Hence, particle simulation is an important tool in many scientific and engineering research fields to simulate the real life processes of the environment. Because of the enormous amount of data in such simulations, data management, storage and processing are very challenging tasks. Spatial Distance Histogram (SDH) is one of the most popular queries being used in this field. In this thesis, we are interested in investigating the performance of improvement of an existing algorithm for computing SDH. The algorithm already being used is using a conceptual data structure called density map which is implemented via a quad tree index. An algorithm having density maps implemented via binary tree is proposed in this thesis. After carrying out many experiments and analysis of the data, we figure out that although the binary tree approach seems efficient in earlier stage, it is same as the quad tree approach in terms of time complexity. However, it provides an improvement in computing time by a constant factor for some data inputs. The second part of this thesis is dedicated to an approach that can potentially reduce the computational time to a great extent by taking advantage of regions where data points are uniformly distributed."]},{"key":"dc:title","label":"Title","values":["Performance Analysis of a Binary-Tree-Based Algorithm for Computing Spatial Distance Histograms"]}]}],"canonical_facts":{"dc:contributor":["Yicheng Tu, Ph.D.","Rafael Perez, Ph.D.","Rahul Tripathi, Ph.D.","Sagar Pandit, Ph.D."],"dc:creator":["Sharma Luetel, Sadhana"],"dc:date":["2009-10-30T07:00:00Z"],"dc:description":["The environment is made up of composition of small particles. Hence, particle simulation is an important tool in many scientific and engineering research fields to simulate the real life processes of the environment. Because of the enormous amount of data in such simulations, data management, storage and processing are very challenging tasks. Spatial Distance Histogram (SDH) is one of the most popular queries being used in this field. In this thesis, we are interested in investigating the performance of improvement of an existing algorithm for computing SDH. The algorithm already being used is using a conceptual data structure called density map which is implemented via a quad tree index. An algorithm having density maps implemented via binary tree is proposed in this thesis. After carrying out many experiments and analysis of the data, we figure out that although the binary tree approach seems efficient in earlier stage, it is same as the quad tree approach in terms of time complexity. However, it provides an improvement in computing time by a constant factor for some data inputs. The second part of this thesis is dedicated to an approach that can potentially reduce the computational time to a great extent by taking advantage of regions where data points are uniformly distributed."],"dc:identifier":["https://digitalcommons.usf.edu/etd/16"],"dc:language":["EN-US"],"dc:rights.license":["default"],"dc:subject":["Spatial Distance Histogram","Particle Distance Histogram","Quad-tree","Binary tree","Uniformity","American Studies","Arts and Humanities"],"dc:title":["Performance Analysis of a Binary-Tree-Based Algorithm for Computing Spatial Distance Histograms"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis","M.S.C.S."],"thesis:institution_name":["University of South Florida"]},"updated_at":"2026-11-19T08:32:57Z"}