Advances in sensing and positioning technology, fueled by wide deployment of wireless networks, have made many devices location-aware. These emerging technologies have enabled a new class of applications, known as Location-Based Services (LBS), offering both new business opportunities and a wide array of new quality of life enhancing services. One example of such services is spatial alarms, an enabling technology for location-based advertisement, location-based alerts or reminders and a host of other applications. On the other hand, the ability to locate mobile users accurately also opens door for new threats - the intrusion of location privacy. The time series of location data can be linked to personal identity, which leads to unauthorized information exposure about the individual's medical conditions, alternative lifestyles, unpopular political views or location-based spam and stalking. Thus, there are two important challenges for location-based service provisioning. How do we scale LBSs in the presence of client mobility and location dependent constraints for the multitude of new, upcoming location-based applications under a common framework? How do we provide anonymous location- based services with acceptable performance and quantifiable privacy protection in the next generation of mobile networks, systems and applications? This dissertation delivers technical solutions to address these important challenges. First, we introduce spatial alarms as the basic primitive to represent a class of locationbased services that require location-based trigger capability. Similar to time-based alarms, spatial alarms serve as spatial event reminders that enable us to express different location-based information needs supported by a variety of applications ranging from location-based advertisements, location-based personal assistants, to friend locator services like Google Latitude. We develop a generalized framework and a suite of optimization techniques for server-centric scalable processing of spatial alarms. Our architecture and algorithm development provide significant performance enhancement in terms of system scalability compared to naive spatial alarm processing techniques, while maintaining high accuracy for spatial alarm processing on the server side and reduced communication costs and energy consumption on the client side. Concretely, we develop safe period optimizations for alarm processing and introduce spatial alarm grouping techniques to further reduce the unnecessary safe period computation costs. In addition, we introduce a distributed alarm processing architecture that advocates the partitioning of the alarm processing load among the server and the relevant mobile clients to reduce the server load and minimize the client-to-server communication cost through intelligent distribution and parallelization. We also explore a variety of optimization opportunities such as incorporating non-spatial constraints into the location-based information monitoring problem and utilizing efficient indexing methods such as bitmap indexing to further enhance the performance and scalability of spatial alarm processing in the presence of mobility hotspots and skewed spatial alarm distributions. Second, we develop the PrivacyGrid framework for privacy-enhanced location service provisioning, focusing on providing customizable and personalized location privacy solutions while scaling the mobile systems and services to a large number of mobile users and a large number of service requests. The PrivacyGrid approach has three unique characteristics. First, we develop a three-tier architecture for scaling anonymous information delivery in a mobile environment while preserving customizable location privacy. Second, we develop a suite of fast, dynamic location cloaking algorithms. It is known that incorporation of privacy protection measures may lead to an inherent conflict between the level of privacy and the quality of services (QoS) provided by the location-based services. Our location cloaking algorithms can scale to higher levels of location anonymity while achieving a good balance between location privacy and QoS. Last but not the least; we develop two types of location anonymization models under the PrivacyGrid architecture, one provides the random way point mobility model based location cloaking solution, and the other provides a road network-based location privacy model powered by both location k-anonymity and segment s-anonymity. A set of graph-based location cloaking algorithms are developed, under the MobiCloak approach, to provide desired levels of privacy protection for users traveling on a road network through scalable processing of anonymous location services. This dissertation, to the best of our knowledge, is the first one that presents a systematic approach to the design and development of the spatial alarm processing framework and various optimization techniques. The concept of spatial alarms and the scaling techniques developed in this dissertation can serve as building blocks for many existing and emerging location-based and presence based information and computing services and applications. The second unique contribution made in this dissertation is its development of the PrivacyGrid architecture for scaling anonymous location based services under the random waypoint mobility model and its extension of the PrivacyGrid architecture through introducing the MobiCloak road-network based location cloaking algorithms with reciprocity support for spatially constrained network mobility model. Another unique feature of the PrivacyGrid and MobiCloak development is its ability to protect location privacy of mobile users while maintaining the end-to-end QoS for location-based service provisioning in the presence of dynamic and personalized privacy constraints.