東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

Scaling Spatial Overlay Operations a...

Calderon Romero, Andres Oswaldo,

Linked to FindBook

Google Book

Amazon

博客來

Scaling Spatial Overlay Operations and Flock Pattern Discovery /

Record Type:	Electronic resources : Monograph/item
Title/Author:	Scaling Spatial Overlay Operations and Flock Pattern Discovery // Andres Oswaldo Calderon Romero.
Author:	Calderon Romero, Andres Oswaldo,
Description:	1 electronic resource (123 pages)
Notes:	Source: Dissertations Abstracts International, Volume: 86-08, Section: B.
Contained By:	Dissertations Abstracts International86-08B.
Subject:	Computer science. -
Online resource:	https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31761412
ISBN:	9798302859556

Scaling Spatial Overlay Operations and Flock Pattern Discovery /
Calderon Romero, Andres Oswaldo,

Scaling Spatial Overlay Operations and Flock Pattern Discovery /Andres Oswaldo Calderon Romero. - 1 electronic resource (123 pages)

Source: Dissertations Abstracts International, Volume: 86-08, Section: B.

This thesis proposes scalable solutions to two significant spatial problems: computing overlay operations and discovering flock patterns. Overlay operations are typically computed among polygon layers using spatial data structures designed for complex geometric relationships. One such structure is the Doubly Connected Edge List (DCEL), an edge-list format widely used in spatial applications for performing planar topological computations. The overlay operation, which combines the DCELs of two input layers, enables efficient spatial queries such as intersection, union, and difference between layers. However, existing sequential methods for computing overlays struggle to scale and often fail to process large datasets, such as the US Census tracts. In this thesis, we present a distributed, scalable approach for computing the overlay operation and its associated queries. We address the challenges inherent in distributing the overlay computation and introduce several optimizations that enhance performance, making these computations feasible for large-scale spatial datasets.The second part of this thesis extends upon the above proposed approach by introducing a novel spatial partitioner based on the kd-tree spatial index. This partitioner optimizes DCEL partitioning and overlay operations by leveraging data distributions, resulting in significantly improved performance and more efficient space utilization. Additionally, we adapt the optimization techniques developed for DCEL overlay operations to address a new problem: the polygonization of dangling edges, cut edges, and polygons.The final part of this thesis presents a scalable technique for detecting moving flock patterns in large trajectory databases. A flock pattern represents a group of entities moving closely together within a defined spatial radius over a specified time interval. Traditional sequential algorithms, though effective, struggle with high computational costs on large, dense datasets. This thesis proposes a distributed framework that leverages spatial partitioning and parallel processing to accelerate flock detection. By addressing challenges in spatial and temporal joins across large datasets, introducing partition-based parallelism, and implementing strategies to manage flock patterns spanning multiple partitions, this approach significantly reduces processing time. Experimental evaluations on synthetic datasets demonstrate substantial improvements in scalability and efficiency over conventional methods.

English

ISBN: 9798302859556Subjects--Topical Terms:

523869
Computer science.
Subjects--Index Terms:

Distributed systems

Scaling Spatial Overlay Operations and Flock Pattern Discovery /
LDR:03981nmm a22004333i 4500 001 2428648
005 20250414021923.5
006 m o d
007 cr|nu||||||||
008 261011s2024 miu||||||m |||||||eng d
020 $a 9798302859556
035 $a (MiAaPQD)AAI31761412
035 $a AAI31761412
040 $a MiAaPQD $b eng $c MiAaPQD $e rda
100 1 $a Calderon Romero, Andres Oswaldo, $e author. $3 3816004
245 1 0 $a Scaling Spatial Overlay Operations and Flock Pattern Discovery / $c Andres Oswaldo Calderon Romero.
264 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2024
300 $a 1 electronic resource (123 pages)
336 $a text $b txt $2 rdacontent
337 $a computer $b c $2 rdamedia
338 $a online resource $b cr $2 rdacarrier
500 $a Source: Dissertations Abstracts International, Volume: 86-08, Section: B.
500 $a Advisors: Tsotras, Vassilis Committee members: Magdy, Amr; Bakalov, Petko; Eldawy, Ahmed; Hristidis, Vagelis.
502 $b Ph.D. $c University of California, Riverside $d 2024.
520 $a This thesis proposes scalable solutions to two significant spatial problems: computing overlay operations and discovering flock patterns. Overlay operations are typically computed among polygon layers using spatial data structures designed for complex geometric relationships. One such structure is the Doubly Connected Edge List (DCEL), an edge-list format widely used in spatial applications for performing planar topological computations. The overlay operation, which combines the DCELs of two input layers, enables efficient spatial queries such as intersection, union, and difference between layers. However, existing sequential methods for computing overlays struggle to scale and often fail to process large datasets, such as the US Census tracts. In this thesis, we present a distributed, scalable approach for computing the overlay operation and its associated queries. We address the challenges inherent in distributing the overlay computation and introduce several optimizations that enhance performance, making these computations feasible for large-scale spatial datasets.The second part of this thesis extends upon the above proposed approach by introducing a novel spatial partitioner based on the kd-tree spatial index. This partitioner optimizes DCEL partitioning and overlay operations by leveraging data distributions, resulting in significantly improved performance and more efficient space utilization. Additionally, we adapt the optimization techniques developed for DCEL overlay operations to address a new problem: the polygonization of dangling edges, cut edges, and polygons.The final part of this thesis presents a scalable technique for detecting moving flock patterns in large trajectory databases. A flock pattern represents a group of entities moving closely together within a defined spatial radius over a specified time interval. Traditional sequential algorithms, though effective, struggle with high computational costs on large, dense datasets. This thesis proposes a distributed framework that leverages spatial partitioning and parallel processing to accelerate flock detection. By addressing challenges in spatial and temporal joins across large datasets, introducing partition-based parallelism, and implementing strategies to manage flock patterns spanning multiple partitions, this approach significantly reduces processing time. Experimental evaluations on synthetic datasets demonstrate substantial improvements in scalability and efficiency over conventional methods.
546 $a English
590 $a School code: 0032
650 4 $a Computer science. $3 523869
650 4 $a Geotechnology. $3 1018558
650 4 $a Geographic information science. $3 3432445
653 $a Distributed systems
653 $a Flocks
653 $a Movement patterns
653 $a Parallel algorithms
653 $a Spatial data
690 $a 0984
690 $a 0428
690 $a 0370
710 2 $a University of California, Riverside. $b Computer Science. $e degree granting institution. $3 3816005
720 1 $a Tsotras, Vassilis $e degree supervisor.
773 0 $t Dissertations Abstracts International $g 86-08B.
790 $a 0032
791 $a Ph.D.
792 $a 2024
856 4 0 $u https://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=31761412