The demand for pervasive access of location-related information (e.g., local traffic, restaurant locations, navigation maps, weather conditions, pollution index, etc.) fosters a tremendous application base of "Location Based Services (LBSs)". Without loss of generality, we model location-related information as "spatial objects" and the accesses of such information as "Location-Dependent Spatial Queries" (LDSQs) in LBS systems. In this thesis, we address the efficiency issue of LDSQ processing through several innovative techniques. First, we develop a new client-side data caching model, called "Complementary Space Caching (CSC)", to effectively shorten data access latency over wireless channels. This is motivated by an observation that mobile clients, with only a subset of objects cached, do not have sufficient knowledge to assert whether or not certain object access from the remote server are necessary for given LDSQs. To address this problem, our CSC requests each client to cache a global data view, that is composed of (i) cached spatial objects and (ii) complementary regions that cover the locations of all the non-cached objects. With a global data view cached, CSC enables clients to assert the completeness of LDSQ results locally. Second, we investigate two new types of complex LDSQs, namely, "Nearest Surrounder" (NS) "Queries" and "Skyline Queries." Both of them have a wide application base. An NS query returns spatial objects along with disjointed angular ranges within which they are the nearest to a given query point. A skyline query retrieves non-dominated spatial objects. An object o is said to be dominated if there is another object o' that is strictly better than o for at least one attribute and is not worse than o for all the other attributes. We conduct in-depth analysis and propose novel techniques to efficiently answer these new queries. Third, we propose an LDSQ processing framework, namely "ROAD," to support efficient access of spatial objects on a road network. ROAD adopts a search space pruning technique that has not been explored before in this context. In ROAD, a large road network is organized as a hierarchy of interconnected regional sub-networks called "Rnets," i.e., search subspaces. Further, with two novel concepts, namely, (i) "shortcuts," that allow jumps across Rnets to accelerate the search traversal, and (ii) "object abstracts", that provide search guidance during traversals, searches supported by ROAD can bypass those Rnets that contain no object of interest. Also, ROAD is flexible to support various LDSQs and objects. We conduct extensive empirical studies to evaluate the performance of our proposed approaches. The experiment results demonstrate the efficiency of our approaches and their superiority over state-of-the-art approaches in corresponding domains. [The dissertation citations contained here are published with the permission of ProQuest LLC. Further reproduction is prohibited without permission. Copies of dissertations may be obtained by Telephone (800) 1-800-521-0600. Web page: http://www.proquest.com/en-US/products/dissertations/individuals.shtml.]