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

Thesis (M. Phil.)--University of Hong Kong, 2007. / Title proper from title frame. Also available in printed format.

Thesis (M.S.)--University of Texas at Dallas, 2007. / Includes vita. Includes bibliographical references (leaves 27-28)

With the continued proliferation of location-based services, a growing number of web-accessible data objects are geo-tagged and have text descriptions. Spatial keyword top-k queries retrieve k such objects with the best score according to a ranking function that takes into account a query location and query keywords. However, it is in some cases difficult for users to specify appropriate query parameters. After a user issues an initial query and gets back the result, the user may find that some expected objects are missing and may wonder why. Answering the resulting why-not questions can aid users in retrieving better results and thus improve the overall utility of the query functionality. While spatial keyword querying has been studied intensively, no proposals exist for how to offer users explanations of why such expected objects are missing from results. In this dissertation, we take the first step to study the why-not questions on spatial keyword top-k queries. We provide techniques that allow different revisions of spatial keyword queries such that their results include one or more desired, but missing objects. Detailed problem analysis and extensive experimental studies consistently demonstrate the effectiveness and robustness of our proposed techniques in a broad range of settings.

published_or_final_version / Computer Science / Master / Master of Philosophy

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

Analytical database queries are at the core of business intelligence and decision support. To analyze the vast amounts of data available today, query execution needs to be orders of magnitude faster. Hardware advances have made a profound impact on database design and implementation. The large main memory capacity allows queries to execute exclusively in memory and shifts the bottleneck from disk access to memory bandwidth. In the new setting, to optimize query performance, databases must be aware of an unprecedented multitude of complicated hardware features. This thesis focuses on the design and implementation of highly efficient database systems by optimizing analytical query execution for all layers of modern hardware. The hardware layers include the network across multiple machines, main memory and the NUMA interconnection across multiple processors, the multiple levels of caches across multiple processor cores, and the execution pipeline within each core. For the network layer, we introduce a distributed join algorithm that minimizes the network traffic. For the memory hierarchy, we describe partitioning variants aware to the dynamics of the CPU caches and the NUMA interconnection. To improve the memory access rate of linear scans, we optimize lightweight compression variants and evaluate their trade-offs. To accelerate query execution within the core pipeline, we introduce advanced SIMD vectorization techniques generalizable across multiple operators. We evaluate our algorithms and techniques on both mainstream hardware and on many-integrated-core platforms, and combine our techniques in a new query engine design that can better utilize the features of many-core CPUs. In the era of hardware becoming increasingly parallel and datasets consistently growing in size, this thesis can serve as a compass for developing hardware-conscious databases with truly high-performance analytical query execution.

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.

Thesis (Ph. D.)--Worcester Polytechnic Institute. / Keywords: XML; XQuery; incremental view maintenance. Includes bibliographical references (leaves 256-263).

Thesis (M. Phil.)--University of Hong Kong, 2010. / Includes bibliographical references (leaves 74-80). Also available in print.