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.

With the ubiquity of broadband, wireless and mobile networking and the diversity of user-driven social networks and social channels, we are entering an information age where people and vehicles are connected at all times, and information and influence are diffused continuously through not only traditional authoritative media such as news papers, TV and radio broadcasting, but also user-driven new channels for disseminating information and diffusing influence. Social network users and mobile travelers can influence and be influenced by the social and spatial connectivity that they share through an impressive array of social and spatial channels, ranging from friendship, activity, professional or social groups to spatial, location-aware, and mobility aware events. In this dissertation research, we argue that spatial alarms and activity-based social networks are two fundamentally new types of information and influence diffusion channels. Such new channels have the potential of enriching our professional experiences and our personal life quality in many unprecedented ways. For instance, spatial alarms enable people to share their experiences or disseminate certain points of interest by leaving location-dependent greetings, tips or graffiti and location dependent tour guide to their friends, colleagues and family members. Through social networks, people can influence their friends and colleagues by the activities they have engaged, such as reviews and blogs on certain events or products. More interestingly, the power of such spatial and social diffusion of information and influence can go far beyond our physical reach. People can utilize user-generated social and spatial channels as effective means to disseminate information and propagate influence to a much wider and possibly unknown range of audiences and recipients at any time and in any location. A fundamental challenge in embracing such new and exciting ways of information diffusion is to develop effective and scalable models and algorithms as enabling technology and building blocks. This dissertation research is dedicated towards this ultimate objective with three novel and unique contributions. First, we develop an activity driven and self-configurable social influence model and a suite of computational algorithms to compute and rank social network nodes in terms of activity-based influence diffusion over social network topologies. By activity driven we mean that the real impact of social influence and the speed of such influence propagation should be computed based on the type, the amount and the time window of the activities performed by a social network node in addition to its social connectivity (social network topology). By self-configurable we mean that the diffusion efficiency and effectiveness are dynamically adapted based on the settings and tunings of multiple spatial and social parameters such as diffusion context, diffusion location, diffusion rate, diffusion energy (heat), diffusion coverage and diffusion incentives (e.g., reward points), to name a few. We evaluate our approach through datasets collected from Facebook, Epinions, and DBLP datasets. Our experimental results show that our activity based social influence model outperforms existing topology-based social influence model in terms of effectiveness and quality with respect to influence ranking and influence coverage computation. Second, we further enhance our activity based social influence model along two dimensions. At first, we use a probabilistic diffusion model to capture the intrinsic properties of social influence such that nodes in a social network may have the choice of whether to participate in a social influence propagation process. We examine threshold based approach and independent probabilistic cascade based approach to determine whether a node is active or inactive in each round of influence diffusion. Secondly, we introduce incentives using multi-scale reward points, which are popularly used in many business settings. We then examine the effectiveness of reward points based incentives in stimulating the diffusion of social influences. We show that given a set of incentives, some active nodes may become more active whereas some inactive nodes may become active. Such dynamics changes the composition of the top-k influential nodes computed by activity-based social influence model. We make several interesting observations: First, popular users who are high degree nodes and have many friends are not necessarily influential in terms of spawning new activities or spreading ideas and information. Second, most influential users are more active in terms of their participation in the social activities and interactions with their friends in the social network. Third, multi-scale reward points based incentives can be effective to both inactive nodes and active nodes. Third, we introduce spatial alarms as the basic building blocks for location-dependent information sharing and influence diffusion. People can share and disseminate their location based experiences and points of interest to their friends and colleagues in the form of spatial alarms. Spatial alarms are triggered and delivered to the intended subscribers only when the subscribers move into the designated geographical vicinity of the spatial alarms, enabling delivering and sharing of relevant information and experience at the right location and the right time with the right subscribers. We studied how to use locality filters and subscriber filers to enhance the spatial alarm processing using traditional spatial indexing techniques. In addition, we develop a fast spatial alarm indexing structure and algorithms, called Mondrian Tree, and demonstrate that the Mondrian tree enabled spatial alarm system can significantly outperform existing spatial indexing based solutions such as R-tree, $k$-d tree, Quadtree. This dissertation consists of six chapters. The first chapter introduces the research hypothesis. We describe our activity-based social influence model in Chapter 2. Chapter 3 presents the probabilistic social influence model powered with rewards incentives. We introduce spatial alarms and the basic system architecture for spatial alarm processing in Chapter 4. We describe the design of our Mondrian tree index of spatial alarms and alarm free regions in Chapter 5. In Chapter 6 we conclude the dissertation with a summary of the unique research contributions and a list of open issues closely relevant to the research problems and solution approaches presented in this dissertation.