Ding, Bolin. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 53-56). / Abstracts in English and Chinese. / Abstract --- p.i / Acknowledgement --- p.ii / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Overview of Research --- p.4 / Chapter 1.2 --- Summary of Results and Thesis Outline --- p.6 / Chapter 2 --- Problem Statement --- p.7 / Chapter 3 --- Literature Review --- p.10 / Chapter 3.1 --- Hardness Results --- p.10 / Chapter 3.2 --- Approximation Algorithms --- p.11 / Chapter 3.2.1 --- Spanning and Cleanup --- p.11 / Chapter 3.2.2 --- d-Star Tree or d-Level Tree --- p.11 / Chapter 3.2.3 --- Randomized Rounding --- p.12 / Chapter 3.3 --- Existing Systems --- p.13 / Chapter 3.3.1 --- RIU (Retrieve Information Unit) --- p.14 / Chapter 3.3.2 --- BANKS --- p.14 / Chapter 3.4 --- Summary --- p.16 / Chapter 4 --- Algorithm Based on Height-Bounded Trees --- p.17 / Chapter 4.1 --- Naive Dynamic Programming Algorithm --- p.19 / Chapter 4.2 --- Performance Ratio and Complexity --- p.23 / Chapter 5 --- Best-First Dynamic Programming Algorithm --- p.26 / Chapter 5.1 --- An Efficient Best-First Algorithm --- p.28 / Chapter 5.2 --- Time/Space Complexity --- p.35 / Chapter 5.3 --- Finding Top-k Group Steiner Trees --- p.36 / Chapter 5.4 --- Other Important Issues --- p.38 / Chapter 5.4.1 --- Comparison with an Unpublished Work --- p.39 / Chapter 5.4.2 --- General Cost Functions --- p.40 / Chapter 5.4.3 --- Keyword Queries with Logical Operators --- p.41 / Chapter 5.4.4 --- Handling Directed Graph --- p.42 / Chapter 5.4.5 --- Graph Size and Graph Maintenance --- p.42 / Chapter 5.4.6 --- Indexing and Pruning Strategy --- p.43 / Chapter 6 --- Experimental Studies --- p.45 / Chapter 6.1 --- Exp-1 Scalability --- p.46 / Chapter 6.2 --- Exp-2 Number of Keywords --- p.48 / Chapter 6.3 --- Exp-3 GST-k Testing --- p.49 / Chapter 6.4 --- Exp-4 MDB (A Directed Graph Dataset) --- p.50 / Chapter 7 --- Conclusions --- p.51 / Bibliography --- p.53

The emerging new services for GPS and mobile users have developed applications that access and exploit spatial objects with new components (e.g. text and social network). Web objects, including blogs, tweets, photos and videos, are embedded into a map by the APIs of map service providers, where textual messages are associated with geographic information. Location-based social networking services, arising from Facebook and Foursquare, allow users to browse and share their traces of locations among the social networks. Among this class of applications, the highlight is that the retrieved spatial objects (e.g. points of interest and moving users) are featured with new components. Integrating such new components into the spatial query processing has produced large amounts of promising results. However, handling new components along with the retrieval of spatial objects increases the complexity of such joint query processing significantly. Thus, management over data from such multiple domains has been received considerable attention from database research community. In this thesis, we introduce three interesting problems and study their sophisticated solutions for processing spatial objects with new components: (i) category-aware optimal route query (CORQ), (ii) social and spatial ranking query (SSRQ), and (iii) efficient notification of meeting point (ENMP) query. Our results for (i) and (ii) facilitate the retrieval of spatial objects from multiple domains while our solutions for (iii) provide effective tools for synchronous management of multiple moving users from a social network. Category-aware optimal route queries (CORQ) are generalized from the traveling salesman problem and enable users to retrieve shortest routes covering selected categories. Social and spatial ranking queries (SSRQ) are relevant to spatial object recommendations using social information and allow users to obtain the spatial objects that not only are near their locations but also impress them with high social influence. Efficient notification of meeting point (ENMP) queries are variants of aggregate nearest neighbor queries and provide real-time rearrangement for multiple moving users according to their locations. Query processing in such multiple domains is complicated due to the mixture of domain information and their integration within one search. Naïve algorithms for these problems incur either numerous expensive evaluations or massive communication cost, which render them inapplicable to large datasets. Our main research purpose is to design efficient and effective solutions for the proposed problems, that avoid the aforementioned shortcomings of naïve algorithms. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

The effectiveness of keyword-based search engines depends largely on the ability of a user to formulate proper queries that are both expressive and selective. However, web search queries issued by casual users are often short and with limited expressiveness. Query recommendation is a popular technique employed by search engines to help users refine their queries. Traditional similarity-based methods, however, often result in redundant and monotonic recommendations. We identify five basic requirements of a query recommendation system, namely relevancy, redundancy-free, diversity, ranking and efficiency. In particular, we focus on the requirements of redundancy-free and diversified recommendations. We propose the DQR framework, which mines a search log to achieve two goals: (1) It clusters search log queries to extract query concepts, based on which recommended queries are selected. Through query construction from the query concepts, we are able to avoid recommendation redundancy. (2) It employs a probabilistic model and a greedy heuristic algorithm to achieve recommendation diversification. Through a comprehensive user study we compare DQR against five other recommendation methods on real search log datasets. Our experiment shows that DQR outperforms the other methods in terms of relevancy, diversity, and ranking performance of the recommendations. At the same time, DQR also achieves high efficiency performance. / published_or_final_version / Computer Science / Master / Master of Philosophy

Dissertation (Ph.D.)--Worcester Polytechnic Institute. / Keywords: database optimization; stream query processing. Includes bibliographical references (leaves 226-234 ).

Dissertation (Ph.D.)--Worcester Polytechnic Institute. / Keywords: Query optimization, data streams, runtime query adaptations, continuous queries, plan migration, distributed query processing, window constraints. Includes bibliographical references (p. 313 - 319 ).

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

Thesis (Ph.D.)--York University, 2004. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 230-238). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://wwwlib.umi.com/cr/yorku/fullcit?pNQ99202

published_or_final_version / Computer Science / Master / Master of Philosophy

Thesis (M.Sc.)--York University, 2006. Graduate Programme in Computer Science. / Typescript. Includes bibliographical references (leaves 261-287). Also available on the Internet. MODE OF ACCESS via web browser by entering the following URL: http://gateway.proquest.com/openurl?url_ver=Z39.88-2004&res_dat=xri:pqdiss&rft_val_fmt=info:ofi/fmt:kev:mtx:dissertation&rft_dat=xri:pqdiss:MR19658

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