published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2008. / Includes bibliographical references (p. 95-101).

Thesis (Ph. D.)--Florida State University, 2005. / Advisor: Dr. Gregory Riccardi, Florida State University, College of Arts and Sciences, Dept. of Computer Science. Title and description from dissertation home page (viewed June 7, 2005). Document formatted into pages; contains ix, 102 pages. Includes bibliographical references.

This thesis examines the portrayal of Aboriginal Peoples in two Saskatchewan daily newspapers. This research is based on the question: "How is the notion of Aboriginal Peoples socially constructed in the print media?" Previous research indicates that media portrayals of minority groups are often partial and stereotypical. Such portrayals are partly responsible for linking the unacceptable behavior of minority groups to phenotypic traits, and thereby contributing to the social significance of "race." Discourse analysis is used to analyze 437 newspaper articles that were collected using a full-text keyword search of the EBSCO Host database, which indexes articles from the Leader Post and the Star Phoenix. In general, the results reveal that Aboriginal peoples are regularly portrayed as problematic; either as having problems themselves, or as causing problems for non-Aboriginal peoples. The results support the view that race is socially constructed and demonstrate that "race," through media discourse, can become a socially acceptable explanation for social problems.

This thesis examines the portrayal of Aboriginal Peoples in two Saskatchewan daily newspapers. This research is based on the question: "How is the notion of Aboriginal Peoples socially constructed in the print media?" Previous research indicates that media portrayals of minority groups are often partial and stereotypical. Such portrayals are partly responsible for linking the unacceptable behavior of minority groups to phenotypic traits, and thereby contributing to the social significance of "race." Discourse analysis is used to analyze 437 newspaper articles that were collected using a full-text keyword search of the EBSCO Host database, which indexes articles from the Leader Post and the Star Phoenix. In general, the results reveal that Aboriginal peoples are regularly portrayed as problematic; either as having problems themselves, or as causing problems for non-Aboriginal peoples. The results support the view that race is socially constructed and demonstrate that "race," through media discourse, can become a socially acceptable explanation for social problems.

Cai, Junpu. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 49-51). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Introduction --- p.1 / Chapter 2 --- Related Works --- p.6 / Chapter 3 --- Problem Definition --- p.10 / Chapter 4 --- Preliminary Study --- p.14 / Chapter 5 --- Algorithms --- p.17 / Chapter 5.1 --- Result Caching algorithm --- p.17 / Chapter 5.1.1 --- Caching Algorithm --- p.18 / Chapter 5.1.2 --- Implementation and Maintenance --- p.20 / Chapter 5.2 --- Query Processing algorithm --- p.20 / Chapter 5.2.1 --- Join Types --- p.21 / Chapter 5.2.2 --- Operators in the Operator Tree --- p.23 / Chapter 5.2.3 --- Comparison with previous work --- p.27 / Chapter 5.2.4 --- Operator Tree (OT) for one CN --- p.28 / Chapter 5.2.5 --- Generic Operator Network (ON) --- p.30 / Chapter 6 --- Empirical Study --- p.37 / Chapter 6.1 --- Result Caching --- p.38 / Chapter 6.2 --- Comparison of Bushy and Left Deep Plans --- p.41 / Chapter 6.3 --- Comparison of ON and previous methods --- p.44 / Chapter 7 --- Conclusion and Future Work --- p.47 / Bibliography --- p.49

In this thesis, for the schema-based approaches, we propose an efficient algorithm to general all relational algebra expressions in order to find all the connected trees in an RDB. We also study an efficient algorithm to evaluate all the expressions using semijoins in RDBMS . We show that our method can also be extended to answer continuous keyword queries in a relational data stream. We further propose novel algorithms that find sets of tuples that are reachable from a root tuple within a radius, and algorithms that find multi-center subgraphs within a radius. Our algorithms use SQL queries only in order to make fully use of RDBMS. We show that the current commercial RDBMSs are powerful enough to support such keyword queries in RDBs efficiently without any additional new indexing to be built and maintained. The main idea behind our approach is tuple reduction. For the graph-based approaches, we propose an efficient algorithm to find all/top- K multi-center subgraphs in polynomial delay. We also introduce a new kind of keyword query, namely, structural statistics by keywords, to summarize keyword search results into several dimensions. We conducted extensive performance studies using two large real datasets IMDB and DBLP to show the efficiency and effectiveness of all our approaches. / Keyword search in relational databases (RDBs) has been extensively studied recently. A keyword search (or a keyword query) in RDBs is specified by a set of keywords to explore the interconnected tuple structures in an RDB that cannot be easily identified using SQL on RDBMSs. In brief, it finds how the tuples containing the given keywords are connected via sequences of connections (foreign key references) among tuples in an RDB. Such interconnected tuple structures can be found as connected trees up to a certain size, sets of tuples that are reachable from a root tuple within a radius, or even multi-center subgraphs within a radius. In the literature, there are two main approaches, namely schema-based approaches and graph-based approaches. The schema-based approaches are to generate a set of relational algebra expressions and evaluate every such expression using SQL on an RDBMS directly or in a middleware on top of an RDBMS indirectly. Due to a large number of relational algebra expressions needed to process, most of the existing works take a middleware approach without fully utilizing RDBMSs. The graph-based approaches are to materialize an RDB as a graph and find the interconnected tuple structures using graph-based algorithms in memory. / Qin, Lu. / Adviser: Jeffrey Xu Yu. / Source: Dissertation Abstracts International, Volume: 73-02, Section: B, page: . / Thesis (Ph.D.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 133-138). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Electronic reproduction. [Ann Arbor, MI] : ProQuest Information and Learning, [201-] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstract also in Chinese.

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques

Thesis (Ph.D.)--Hong Kong University of Science and Technology, 2007. / Includes bibliographical references (leaves 89-94). Also available in electronic version.