Filters
Availability
Publication Year
Resource Type
Faculty
School/Institute
Publication Search Results
Sort
Results per page
1 - 3 of 3
-
(2022)ThesisBipartite graphs are extensively used to model relationships between two different types of entities. In many real-world bipartite graphs, relationships are naturally uncertain due to various reasons such as data noise, measurement error and imprecision of data, leading to uncertain bipartite graphs. In this thesis, we propose the (\alpha,\beta,\eta)-core model, which is the first cohesive subgraph model on uncertain bipartite graphs. To capture the uncertainty of relationships/edges, \eta-degree is adopted to measure the vertex engagement level, which is the largest integer k such that the probability of a vertex having at least k neighbors is not less than \eta. Given degree constraints \alpha and \beta, and a probability threshold \eta, the (\alpha,\beta,\eta)-core requires that each vertex on the upper or lower level have \eta-degree no less than \alpha or \beta, respectively. An (\alpha,\beta,\eta)-core can be derived by iteratively removing a vertex with \eta-degree below the degree constraint and updating the \eta-degrees of its neighbors. This incurs prohibitively high cost due to the \eta-degree computation and updating, and it is not scalable to large bipartite graphs. This motivates us to develop index-based approaches. We propose a basic full index that stores (\alpha,\beta,\eta)-core for all possible \alpha, \beta, and \eta combinations, thus supporting optimal retrieval of the vertices in any (\alpha,\beta,\eta)-core. Due to its long construction time and high space complexity, we further propose a probability-aware index to achieve a balance between time and space costs. To efficiently build the probability-aware index, we design a bottom-up index construction algorithm and a top-down index construction algorithm. Extensive experiments are conducted on real-world datasets with generated edge probabilities under different distributions, which show that (1) (\alpha,\beta,\eta)-core is an effective model; (2) index construction and query processing are significantly sped up by the proposed techniques.
-
(2024)ThesisStructural diversity of a vertex refers to the diversity of connections within its neighborhood and has been applied in various fields such as viral marketing and user engagement. The thesis studies querying the structural diversity of a vertex for any query time windows in streaming graphs. Existing studies are limited to static graphs which fail to capture vertices' structural diversities in snapshots evolving over time. We design an elegant index structure to significantly reduce the index size compared to the basic approach. We propose an optimized incremental algorithm to update the index for continuous edge arrivals. Extensive experiments on real-world streaming graphs demonstrate the effectiveness of our framework.
-
(2024)ThesisPoint cloud, as a widely used data structure, has gained significant attention due to its ability to precisely represent the shape of 3D object. One of the most important point cloud related tasks is multiview registration, which involves aligning multiple point cloud fragments. It has various applications, including scene reconstruction, robotics and autonomous. In current studies, multiview registration has often been decomposed into two stages: pairwise registration and synchronization, where each one is considered as an independent task. In this thesis, we investigate a pipeline that can leverage the information obtained from both stages. Through this way, we aim to enhance the overall effectiveness and efficiency of multiview registration. In the first stage, we focus on inspecting the pairwise registration methods. To provide accurate pairwise registration results, we adopt a deep learning-based model that retrieves the point-wise features. In the proposed model, we employ an encoder-decoder framework which incorporates self- and cross-attentional layers. They enable effective communication between two fragments, allowing for the extraction of high-quality features which not only capture the intrinsic information within individual point cloud but also capture the contextual information across point clouds. Furthermore, we introduce two modules that can enhance the registration and integrate with the following stage. Next, we investigate the synchronization stage, which aims to recover the global registration for all the point clouds. To incorporate information from previous stage, we devise a method that evaluates the reliability of the pairwise registration results. By integrating the additional information and modules into iteratively reweighted least square algorithm, our method can gradually refine the transformation matrix and achieve global alignment for all point clouds. We conducted extensive experiments on benchmark datasets to evaluate the performance of our proposed methods and compared with other outstanding models. The results demonstrate the capability of our model to yield high-quality registration outcomes.