Efficient structure search in large data sets
type: CreativeWork
description: Nowadays, with the explosion of information, there has been rapid increase in the amount of data being generated and published; therefore there is an emerging need for efficiently managing and processing large data sets. Among the existing problems, structure search is an important topic with many real applications, such as substructure search in social networks and protein interaction networks and community detecting in social/collaboration networks. In this thesis, we study three important problems regarding structure search in large data sets. Firstly, we study the structure search in graph data and focus on subgraph matching over large data graphs, which extracts all subgraph isomorphic embeddings of a query graph q in a large data graph G. For the first time we address the issue of unpromising results by Cartesian products from "dissimilar" vertices. We propose a new framework by postponing the Cartesian products based on the structure of a query to minimize the redundant Cartesian products. We also devise a new linear size auxiliary data structure to generate a matching order and conduct subgraph matching. Secondly, we investigate the "community" structure search in large graphs, and emphasize on top-k influential communities, where each reported community not only is a cohesive subgraph but also has a high influence value. We propose an instance-optimal algorithm LocalSearch whose time complexity is linearly proportional to the size of the smallest subgraph that a correct algorithm needs to access without indexes. In addition, we propose techniques to make LocalSearch progressively compute and report the communities in decreasing influence value order such that k does not need to be specified. Finally, we study the structure search problem in string data sets with edit distance similarity, which retrieves all strings in a string data set that are similar to a query string with respect to a given edit distance threshold. We propose a cross pivotal based approa…
abstract: Nowadays, with the explosion of information, there has been rapid increase in the amount of data being generated and published; therefore there is an emerging need for efficiently managing and processing large data sets. Among the existing problems, structure search is an important topic with many real applications, such as substructure search in social networks and protein interaction networks and community detecting in social/collaboration networks. In this thesis, we study three important problems regarding structure search in large data sets. Firstly, we study the structure search in graph data and focus on subgraph matching over large data graphs, which extracts all subgraph isomorphic embeddings of a query graph q in a large data graph G. For the first time we address the issue of unpromising results by Cartesian products from "dissimilar" vertices. We propose a new framework by postponing the Cartesian products based on the structure of a query to minimize the redundant Cartesian products. We also devise a new linear size auxiliary data structure to generate a matching order and conduct subgraph matching. Secondly, we investigate the "community" structure search in large graphs, and emphasize on top-k influential communities, where each reported community not only is a cohesive subgraph but also has a high influence value. We propose an instance-optimal algorithm LocalSearch whose time complexity is linearly proportional to the size of the smallest subgraph that a correct algorithm needs to access without indexes. In addition, we propose techniques to make LocalSearch progressively compute and report the communities in decreasing influence value order such that k does not need to be specified. Finally, we study the structure search problem in string data sets with edit distance similarity, which retrieves all strings in a string data set that are similar to a query string with respect to a given edit distance threshold. We propose a cross pivotal based approa…
author: Bi, Fei
language: EN
keywords: Influential Community Search, Substructure Search, Subgraph Matching, String Similarity Search
license: https://purl.org/coar/access_right/c_abf2
license: https://creativecommons.org/licenses/by-nc-nd/3.0/au/
date published: 2018
date modified: 2026-07-24T05:34:44Z
provider: University of New South Wales
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: UNSW, Sydney

PropertyValue
property ID: Handle
value: http://hdl.handle.net/1959.4/60228

PropertyValue
property ID: DOI
value: 10.26190/unsworks/20432