{"id":{"repo_id":"houston","oai_identifier":"oai:uh-ir.tdl.org:10657/3478"},"canonical_url":"https://search.dev.ndltd.org/etd/houston/oai:uh-ir.tdl.org:10657/3478","repository":{"repo_id":"houston","name":"University of Houston","base_url":"https://uh-ir.tdl.org/server/oai/request"},"display":{"title":"Transforming Point Data into Proximity Graphs","abstract":"Establishing neighborhood relationships among data points is important for several data analysis applications, for which structural information is essential. Since the early 1980’s, proximity graphs have served as one of the classical approaches to characterize neighborhood relationships; the most popular proximity graphs include Delaunay Triangulation (DT), Gabriel graphs (GG), relative neighborhood graphs (RNG), and minimum spanning tree (MST). These graphs find their applications in geographical analysis, spatial analysis, pattern recognition, evolutionary biology, computer vision, cluster analysis, and visualization. The emergence of big data has created a need for scalable algorithms to generate proximity graphs for massive datasets. In this thesis, we propose a novel approach for creating DT, GG, and RNG by leveraging the cluster computing capabilities of Apache Spark. To compute DT, we rely on the divide and conquer paradigm. We first partition the spatial dataset into a grid; next, we compute the DT for each grid partition and separate the resulting triangles into the core and boundary triangles; next, we merge the adjacent partitions recursively and re-compute boundary triangles; finally, we return the union of obtained triangles as the final result. GG and RNG are implemented on top of a DT, by removing edges from the DT. In our GG algorithm, we compute the circumcenter for every triangle and associate it with edges of the triangle. The circumcenter coordinates associated with the non-boundary edges form the Voronoi edge. We filter those Delaunay edges, which do not intersect with their corresponding Voronoi edge, to obtain a GG. Relative neighborhood graphs are formed by removing those edges, for which the distance between the endpoints of an edge is less than the distance between any other point and one of the endpoints of the edge. We evaluate our algorithms to create DT, GG, and RNG for a benchmark of datasets having between one and eight million data records. Our benchmark tests showcase the significant performance improvement obtained with our algorithms and the impact of the grid partitioning technique on the runtime. We apply our algorithms to create clusters of Texas climate data and for boundary detection on a genetic dataset.","abstract_html":"Establishing neighborhood relationships among data points is important for several data analysis applications, for which structural information is essential. Since the early 1980’s, proximity graphs have served as one of the classical approaches to characterize neighborhood relationships; the most popular proximity graphs include Delaunay Triangulation (DT), Gabriel graphs (GG), relative neighborhood graphs (RNG), and minimum spanning tree (MST). These graphs find their applications in geographical analysis, spatial analysis, pattern recognition, evolutionary biology, computer vision, cluster analysis, and visualization. The emergence of big data has created a need for scalable algorithms to generate proximity graphs for massive datasets. In this thesis, we propose a novel approach for creating DT, GG, and RNG by leveraging the cluster computing capabilities of Apache Spark. To compute DT, we rely on the divide and conquer paradigm. We first partition the spatial dataset into a grid; next, we compute the DT for each grid partition and separate the resulting triangles into the core and boundary triangles; next, we merge the adjacent partitions recursively and re-compute boundary triangles; finally, we return the union of obtained triangles as the final result. GG and RNG are implemented on top of a DT, by removing edges from the DT. In our GG algorithm, we compute the circumcenter for every triangle and associate it with edges of the triangle. The circumcenter coordinates associated with the non-boundary edges form the Voronoi edge. We filter those Delaunay edges, which do not intersect with their corresponding Voronoi edge, to obtain a GG. Relative neighborhood graphs are formed by removing those edges, for which the distance between the endpoints of an edge is less than the distance between any other point and one of the endpoints of the edge. We evaluate our algorithms to create DT, GG, and RNG for a benchmark of datasets having between one and eight million data records. Our benchmark tests showcase the significant performance improvement obtained with our algorithms and the impact of the grid partitioning technique on the runtime. We apply our algorithms to create clusters of Texas climate data and for boundary detection on a genetic dataset.","abstract_has_math":false,"creators":["Subramanyam Varalakshmi, Arjun 1991-"],"institution":"University of Houston","degree_name":"Master of Science","degree_level":"Masters","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Eick, Christoph F."],"committee_chairs":[],"committee_members":["Shi, Weidong","Yuan, Xiaojing"],"year":2018,"date_issued":"2018-05","date_published":"2018-05","updated_at":"2026-07-24T02:32:54Z","subjects":["Proximity graphs","Apache Spark","Gabriel graph","Grid partitioning","Scalable","Relative neighbor graph"],"languages":["eng"],"rights":["The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s)."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10657/3478","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Eick, Christoph F."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Shi, Weidong","Yuan, Xiaojing"]},{"key":"dc:creator","label":"Author","values":["Subramanyam Varalakshmi, Arjun 1991-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2018-11-30T17:23:21Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2018-11-30T17:23:21Z"]},{"key":"dc:date.issued","label":"Date","values":["2018-05"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Houston"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Proximity graphs","Apache Spark","Gabriel graph","Grid partitioning","Scalable","Relative neighbor graph"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s)."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10657/3478"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Establishing neighborhood relationships among data points is important for several data analysis applications, for which structural information is essential. Since the early 1980’s, proximity graphs have served as one of the classical approaches to characterize neighborhood relationships; the most popular proximity graphs include Delaunay Triangulation (DT), Gabriel graphs (GG), relative neighborhood graphs (RNG), and minimum spanning tree (MST). These graphs find their applications in geographical analysis, spatial analysis, pattern recognition, evolutionary biology, computer vision, cluster analysis, and visualization. The emergence of big data has created a need for scalable algorithms to generate proximity graphs for massive datasets. In this thesis, we propose a novel approach for creating DT, GG, and RNG by leveraging the cluster computing capabilities of Apache Spark. To compute DT, we rely on the divide and conquer paradigm. We first partition the spatial dataset into a grid; next, we compute the DT for each grid partition and separate the resulting triangles into the core and boundary triangles; next, we merge the adjacent partitions recursively and re-compute boundary triangles; finally, we return the union of obtained triangles as the final result. GG and RNG are implemented on top of a DT, by removing edges from the DT. In our GG algorithm, we compute the circumcenter for every triangle and associate it with edges of the triangle. The circumcenter coordinates associated with the non-boundary edges form the Voronoi edge. We filter those Delaunay edges, which do not intersect with their corresponding Voronoi edge, to obtain a GG. Relative neighborhood graphs are formed by removing those edges, for which the distance between the endpoints of an edge is less than the distance between any other point and one of the endpoints of the edge. We evaluate our algorithms to create DT, GG, and RNG for a benchmark of datasets having between one and eight million data records. Our benchmark tests showcase the significant performance improvement obtained with our algorithms and the impact of the grid partitioning technique on the runtime. We apply our algorithms to create clusters of Texas climate data and for boundary detection on a genetic dataset."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Transforming Point Data into Proximity Graphs"]}]}],"canonical_facts":{"dc:contributor.advisor":["Eick, Christoph F."],"dc:contributor.committeemember":["Shi, Weidong","Yuan, Xiaojing"],"dc:creator":["Subramanyam Varalakshmi, Arjun 1991-"],"dc:date.accessioned":["2018-11-30T17:23:21Z"],"dc:date.available":["2018-11-30T17:23:21Z"],"dc:date.issued":["2018-05"],"dc:description.abstract":["Establishing neighborhood relationships among data points is important for several data analysis applications, for which structural information is essential. Since the early 1980’s, proximity graphs have served as one of the classical approaches to characterize neighborhood relationships; the most popular proximity graphs include Delaunay Triangulation (DT), Gabriel graphs (GG), relative neighborhood graphs (RNG), and minimum spanning tree (MST). These graphs find their applications in geographical analysis, spatial analysis, pattern recognition, evolutionary biology, computer vision, cluster analysis, and visualization. The emergence of big data has created a need for scalable algorithms to generate proximity graphs for massive datasets. In this thesis, we propose a novel approach for creating DT, GG, and RNG by leveraging the cluster computing capabilities of Apache Spark. To compute DT, we rely on the divide and conquer paradigm. We first partition the spatial dataset into a grid; next, we compute the DT for each grid partition and separate the resulting triangles into the core and boundary triangles; next, we merge the adjacent partitions recursively and re-compute boundary triangles; finally, we return the union of obtained triangles as the final result. GG and RNG are implemented on top of a DT, by removing edges from the DT. In our GG algorithm, we compute the circumcenter for every triangle and associate it with edges of the triangle. The circumcenter coordinates associated with the non-boundary edges form the Voronoi edge. We filter those Delaunay edges, which do not intersect with their corresponding Voronoi edge, to obtain a GG. Relative neighborhood graphs are formed by removing those edges, for which the distance between the endpoints of an edge is less than the distance between any other point and one of the endpoints of the edge. We evaluate our algorithms to create DT, GG, and RNG for a benchmark of datasets having between one and eight million data records. Our benchmark tests showcase the significant performance improvement obtained with our algorithms and the impact of the grid partitioning technique on the runtime. We apply our algorithms to create clusters of Texas climate data and for boundary detection on a genetic dataset."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10657/3478"],"dc:language.iso":["eng"],"dc:rights":["The author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s)."],"dc:subject":["Proximity graphs","Apache Spark","Gabriel graph","Grid partitioning","Scalable","Relative neighbor graph"],"dc:title":["Transforming Point Data into Proximity Graphs"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["University of Houston"]},"updated_at":"2026-07-24T02:32:54Z"}