Includes bibliographical references (p. 185-196).

In typical location-based services (LBS), moving objects (e.g., GPS-enabled mobile phones) report their locations through a wireless network. An LBS server can use the location information to answer various types of continuous queries, e.g., \Give me the ID of a battalion which is the closest to a military base within the next hour." Due to hardware limitations, location data reported by the moving objects are often uncertain. In this paper, we study efficient methods for the execution of Continuous Possible Nearest Neighbor Query (CPoNNQ) that accesses imprecise location data. A CPoNNQ is a standing query (which is active during a period of time) such that, at any time point, all moving objects that have non-zero probabilities of being the nearest neighbor of a given query point are reported. To handle the continuous nature of a CPoNNQ, a simple solution is to require moving objects to continuously report their locations to the LBS server, which evaluates the query at every time step. To save communication bandwidth and mobile devices' batteries, we develop two filter-based protocols for CPoNNQ evaluation. Our protocols install filter bounds" on moving objects, which suppress unnecessary location reporting and communication between the server and the moving objects. Through extensive experiments, we show that our protocols can effectively reduce communication and energy costs while maintaining a high query quality. / published_or_final_version / Computer Science / Master / Master of Philosophy

Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2008. / Includes bibliographical references (leaves 57-60). Also available in electronic version.

Dissertation (Ph.D.)--Worcester Polytechnic Institute. / Keywords: metadata, constraint, data stream, continuous query, optimization. Includes bibliographical references (leaves 275-283).

Thesis (Ph.D.)--George Mason University, 2008. / Vita: p. 169. Thesis director: Amihai Motro. Submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy in Computer Science. Title from PDF t.p. (viewed Aug. 27, 2008). Includes bibliographical references (p. 162-168). Also issued in print.

Thesis (M. Sc.)--University of Alberta, 2009. / Title from PDF file main screen (viewed on Sept. 8, 2009). "A thesis submitted to the Faculty of Graduate Studies and Research in partial fulfillment of the requirements for the degree of Master of Science, Department of Computing Science, University of Alberta." Includes bibliographical references.

Includes bibliographical references (p. 134-138).

Dissertation (Ph.D.)--Worcester Polytechnic Institute. / Keywords: View Updating, XML, XQuery Includes bibliographical references (leaves :195 - 202 ).

Thesis (M.S.)--Brigham Young University. Dept. of Computer Science, 2006. / Includes bibliographical references (p. 41-44).

Graphs are powerful tools for a wide range of real applications, from Biological and Chemical Databases, Social Networks, Citation Networks to Knowledge Bases. Large graph data repositories have been consistently found in recent applications. Due to the high complexity of graph queries, e.g., NP-Completeness of subgraph query, and the lack of IT expertise, hosting efficient graph query services for the owners of graph data has been a technically challenging task. And hence, they may prefer to outsource their services to third-party service providers (SPs) for scalability, elasticity and efficiency. Unfortunately, SPs may not always be trusted. Security, typically the integrity and confidentiality, of the data, has been recognized as one of the critical attributes of Quality of Services (QoS). This directly influences the willingness of both data owners and query clients to use SP’s services. To address these concerns, this thesis proposes novel techniques to solve both authentication-aware and privacy-aware subgraph query. Firstly, we study authenticated subgraph query services (Chapter 3). To support the service, we propose Merkle IFTree (MIFTree) where Merkle hash trees are applied into our Intersection-aware Feature-subgraph Tree (IFTree). IFTree aims to minimize I/O in a well-received subgraph query paradigm namely the filtering-and-verification framework. The structures required to be introduced to verification objects (VOs) and the authentication time are minimized. Subsequently, the overall response time is minimized. For optimizations, we propose an enhanced authentication method on MIFTree. Secondly, we propose structure-preserving subgraph query services (Chapter 4). A crucial step of this part is to transform the seminal subgraph isomorphism algorithm (the Ullmann’s algorithm) into a series of matrix operations. We propose a novel cyclic group based encryption (CGBE) method for private matrix operations. We propose a protocol that involves the query client and static indexes for optimizations. We prove that the structural information of both query graph and data graph are preserved under CGBE and analyze the privacy preservation in the presence of the optimizations. Thirdly, we propose asymmetric structure-preserving subgraph query processing (Chapter 5), where the data graph is publicly known and the query structure/topology is kept secret. Unlike other previous methods for subgraph queries, this part proposes a series of novel optimizations that only exploit graph structures, not the queries. Further, we propose a robust query encoding and adopt our proposed cyclic group based encryption method, so that the query processing can be transformed into a series of private matrix operations and performed securely. The effectiveness and efficiency of all the techniques presented in this thesis are experimentally evaluated with both real-world and synthetic dataset