The ever-growing amount of online information calls for Personalization. Among the various personalization systems, recommenders have become increasingly popular in recent years. Recommenders typically use collaborative filtering to suggest the most relevant items to their users. The most prominent challenges underlying personalization are: scalability, privacy, and heterogeneity. Scalability is challenging given the growing rate of the Internet and its dynamics, both in terms of churn (i.e., users might leave/join at any time) and changes of user interests over time. Privacy is also a major concern as users might be reluctant to expose their profiles to unknown parties (e.g., other curious users), unless they have an incentive to significantly improve their navigation experience and sufficient guarantees about their privacy. Heterogeneity poses a major technical difficulty because, to be really meaningful, the profiles of users should be extracted from a number of their navigation activities (heterogeneity of source domains) and represented in a form that is general enough to be leveraged in the context of other applications (heterogeneity of target domains). In this dissertation, we address the above-mentioned challenges. For scalability, we introduce democratization and incrementality. Our democratization approach focuses on iteratively offloading the computationally expensive tasks to the user devices (via browsers or applications). This approach achieves scalability by employing the devices of the users as additional resources and hence the throughput of the approach (i.e., number of updates per unit time) scales with the number of users. Our incrementality approach deals with incremental similarity metrics employing either explicit (e.g., ratings) or implicit (e.g., consumption sequences for users) feedback. This approach achieves scalability by reducing the time complexity of each update, and thereby enabling higher throughput. We tackle the privacy concerns from two perspectives, i.e., anonymity from either other curious users (user-level privacy) or the service provider (system-level privacy). We strengthen the notion of differential privacy in the context of recommenders by introducing distance-based differential privacy (D2P) which prevents curious users from even guessing any category (e.g., genre) in which a user might be interested in. We also briefly introduce a recommender (X-REC) which employs uniform user sampling technique to achieve user-level privacy and an efficient homomorphic encryption scheme (X-HE) to achieve system-level privacy. We also present a heterogeneous recommender (X-MAP) which employs a novel similarity metric (X-SIM) based on paths across heterogeneous items (i.e., items from different domains). To achieve a general form for any user profile, we generate her AlterEgo profile in a target domain by employing an item-to-item mapping from a source domain (e.g., movies) to a target domain (e.g., books). Moreover, X-MAP also enables differentially private AlterEgos. While X-MAP employs user-item interactions (e.g., ratings), we also explore the possibility of heterogeneous recommendation by using content-based features of users (e.g., demography, time-varying preferences) or items (e.g., popularity, price).