Contemporary search engines use a variety of techniques to personalize search results based on users' past queries. While studies have found that users generally prefer personalized search results to non-personalized ones, recent surveys also indicate growing reservations with respect to personalization because of its privacy implications. In this paper, we take a deeper look at privacy considerations of users during web search and explore how users' preferences for privacy and personalization interact when undertaking this activity. We conduct an empirical study over Google search, involving 25 participants in India and their respective web search histories. Our finding is that users exhibit a slight preference for personalization in their search results but are usually willing to "give up" personalization when searching for topics they deem sensitive. We discuss implications of these results for the design of privacy-preserving tools for web search.

Recent studies have highlighted user concerns with respect to third-party tracking and online behavioral advertising (OBA) and the need for better consumer choice mechanisms to address these phenomena. We re-investigate the question of perceptions of third-party tracking while situating it in the larger context of how online ads, in general, are perceived by users. Via in-depth interviews with 53 Web users in India, we find that although concerns for third-party tracking and OBA remain noticeable amongst this population, other aspects of online advertising---like the possibility of being shown ads with embarrassing and suggestive content---are voiced as greater concerns than the concern of being tracked. Current-day blocking tools are insufficient to redress the situation: users demand selective filtering of ad content (as opposed to blocking out all ads) and are not satisfied with mechanisms that only control tracking and OBA. We conclude with design recommendations for enduser tools to control online ad consumption keeping in mind the concerns brought forth by our study.

Online service platforms (OSPs), such as search engines, news-websites, ad-providers, etc., serve highly personalized content to the user, based on the profile extracted from her history with the OSP. In this paper, we capture OSP's personalization for an user in a new data structure called the personalization vector (?), which is a weighted vector over a set of topics, and present efficient algorithms to learn it.

Viral Marketing, the idea of exploiting social interactions of users to propagate awareness for products, has gained considerable focus in recent years. One of the key issues in this area is to select the best seeds that maximize the influence propagated in the social network. In this paper, we define the seed selection problem (called t-Influence Maximization, or t-IM) for multiple products. Specifically, given the social network and t products along with their seed requirements, we want to select seeds for each product that maximize the overall influence. As the seeds are typically sent promotional messages, to avoid spamming users, we put a hard constraint on the number of products for which any single user can be selected as a seed. In this paper, we design two efficient techniques for the t-IM problem, called Greedy and FairGreedy. The Greedy algorithm uses simple greedy hill climbing, but still results in a 1/3-approximation to the optimum. Our second technique, FairGreedy, allocates seeds with not only high overall influence (close to Greedy in practice), but also ensures fairness across the influence of different products. We also design efficient heuristics for estimating the influence of the selected seeds, that are crucial for running the seed selection on large social network graphs. Finally, using extensive simulations on real-life social graphs, we show the effectiveness and scalability of our techniques compared to existing and naive strategies.

In this paper, we develop a framework for achieving scalable and communication-efficient dissemination of content in pub/sub systems. To maximize communication sharing across subscriptions, our routing framework groups subscriptions based on similarity, and transmits content matching one or more subscriptions in a group over a single dissemination tree for the group. We develop a cost model that uses published content samples in conjunction with the knowledge of consumer subscriptions to estimate the communication cost of a set of routing trees for subscription groups. The problem of computing a communication-optimal set of routing trees is then formulated as an optimization problem that seeks to find trees with the minimum cost. It turns out that the problem of computing a minimum-cost tree for a subscription group is a new generalization of the well-known Steiner tree problem, and an interesting problem in its own right. We develop an approximation algorithm that uses low-stretch spanning trees to compute a tree whose communication cost is within a polylogarithmic factor of the optimum. We use this to compute trees for various subscription- grouping configurations generated using a greedy clustering strategy, and select the one with the lowest cost. Our experimental study demonstrates the effectiveness of our content-aware routing approach compared to traditional routing based on content oblivious spanning trees.

We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits while providing minimal descriptions of the estimated target trajectory. Using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution in localizing a target's trajectory is of the order of 1/ρ R , where R is the sensing radius and ρ is the sensor density per unit area. We provide a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a “lowpass” approximation of the trajectory is attainable, and explore the implications of this observation for estimating the target's velocity. We also consider nonideal sensing, employing particle filters to average over noisy sensor observations, and geometric geometric postprocessing of the particle filter output to provide an economical piecewise linear description of the trajectory. In addition to simulation results validating our approaches for both idealized and nonideal sensing, we report on lab-scale experiments using motes with acoustic sensors.

Modern communication networks are vulnerable to attackers who send unsolicited messages to innocent users, wasting network resources and user time. Some examples of such attacks are spam emails, annoying tele-marketing phone calls, viral marketing in social networks, etc. Existing techniques to identify these attacks are tailored to certain specific domains (like email spam filtering), but are not applicable to a majority of other networks. We provide a generic abstraction of such attacks, called the Random Link Attack (RLA), that can be used to describe a large class of attacks in communication networks. In an RLA, the malicious user creates a set of false identities and uses them to communicate with a large, random set of innocent users. We mine the social networking graph extracted from user interactions in the communication network to find RLAs. To the best of our knowledge, this is the first attempt to conceptualize the attack definition, applicable to a variety of communication networks. In this paper, we formally define RLA and show that the problem of finding an RLA is NP-complete. We also provide two efficient heuristics to mine subgraphs satisfying the RLA property; the first (GREEDY) is based on greedy set-expansion, and the second (TRWALK) on randomized graph traversal. Our experiments with a real-life data set demonstrate the effectiveness of these algorithms.

We propose a highly compact two-part representation of a given graph G consisting of a graph summary and a set of corrections. The graph summary is an aggregate graph in which each node corresponds to a set of nodes in G, and each edge represents the edges between all pair of nodes in the two sets. On the other hand, the corrections portion specifies the list of edge-corrections that should be applied to the summary to recreate G. Our representations allow for both lossless and lossy graph compression with bounds on the introduced error. Further, in combination with the MDL principle, they yield highly intuitive coarse-level summaries of the input graph G. We develop algorithms to construct highly compressed graph representations with small sizes and guaranteed accuracy, and validate our approach through an extensive set of experiments with multiple real-life graph data sets.

Modern computer systems are called on to deal with billions of events every second, whether they are executed instructions, accessed memory locations, or forwarded packets. This presents a serious challenge to those who seek to quantify, analyze, or optimize such systems, because important trends and behaviors may easily be lost in a sea of data. We present range-adaptive profiling (RAP) as a new and general-purpose profiling method capable of hierarchically efficiently classifying streams of data in hardware. Through the use of RAP, events in an input stream are dynamically classified into increasingly precise categories, based on the frequency with which they occur. The more important a class, or range of events, the more precisely it is quantified. Despite the dynamic nature of our technique, we build upon tight theoretic bounds covering both worst-case error, as well as the required memory. In the limit, it is known that error and the memory bounds can be independent of the stream size and grow only linearly with the level of precision desired. Significantly, we expose the critical constants in these algorithms and through careful engineering, algorithm redesign, and use of heuristics, we show how a high-performance profile system can be implemented for range-adaptive profiling. RAP can be used on various profiles, such as PCs, load values, and memory addresses, and has a broad range of uses, from hot-region profiling to quantifying cache miss value locality. We propose two methods of implementation of RAP, one in software and the other with specialized hardware, for which we also describe our prototype FPGA implementation. We show that with just 8KB of memory, range profiles can be gathered with an average accuracy of 98%.

We propose a low-overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An ε- cut , for any 0 < ε < 1, is a linear separation of ε n nodes in S from a distinguished node, the base station . Our main result is that, by monitoring the status of just O (1/ε) nodes in the network, the base station can detect whenever an ε- cut occurs. Furthermore, this detection comes with a deterministic guarantee that every reported cut has size at least ε n /2. Besides this combinatorial result, we also propose efficient algorithms for finding the O (1/ε) nodes that should act as sentinels , and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on random sampling.

We propose new algorithms for constructing maximum error (L∞) histograms in the data stream model. Our first algorithm (Min-Merge) achieves the following performance guarantee: using O(B) memory, it constructs a 2B-bucket histogram whose approximation error is at most the error of the optimal B-bucket histogram. Our second algorithm (Min-Increment) achieves a (1 + ε)-approximation of a B-bucket histogram using O(ε-1B log U) space, where U is the size of the domain for data values. The memory requirements of these algorithms are a significant improvement over the previous best schemes for constructing near-optimal histograms in the data stream model, making them ideal for data summary applications where memory is at a premium, such as wireless sensor networks. Our Min-Increment algorithm also extends to the sliding window model without any asymptotic increase in space. Finally, using synthetic and real-world data, we show that our algorithms are indeed as space-efficient in practice as their theoretical analysis predicts - compared to previous best algorithms, they require two or more orders of magnitude less memory for the same approximation error.

A large number of potential applications of sensor and actuator networks (SANETs) have emerged recently, for example in the areas of energy production and distribution and health care and telemedicine. SANETs integrate the tasks of sensing and actuation, the process of controlling the operation of a physical system by setting values for parameters of interest. Of particular importance in SANETs is the ability to set actuator parameters, typically depending on values observed by the sensors, so as to achieve a system-wide objective. However, SANETs with large number of nodes or covering wide geographical areas present scalability challenges that necessitate the use of summarization techniques resulting in sub-optimal actuation values. There is therefore a clear trade-off between the level of summarization and the quality of the computed actuation parameters. This paper focuses on two interdependent problems. The first is the issue of efficient aggregation and summarization of the measurements. The second is the distributed computation of optimal actuation parameters to achieve a system-wide objective. We first consider the problem under the assumption of semi-static sensed values and then extend our model to cover the general case where sensor state changes, triggering update events. We develop algorithms for efficient summarization of these events and demonstrate that they minimally impact optimal actuation. Our work is motivated by the domain of energy distribution networks and, in particular, intelligent electrical grids.

We consider the following problem: given an on-line, possibly unbounded stream of two-dimensional points, how can we summarize its spatial distribution or shape using a small, bounded amount of memory? We propose a novel scheme, called ClusterHull, which represents the shape of the stream as a dynamic collection of convex hulls, with a total of at most m vertices, where m is the size of the memory. The algorithm dynamically adjusts both the number of hulls and the number of vertices in each hull to best represent the stream using its fixed memory budget. This algorithm addresses a problem whose importance is increasingly recognized, namely the problem of summarizing real-time data streams to enable on-line analytical processing. As a motivating example, consider habitat monitoring using wireless sensor networks. The sensors produce a steady stream of geographic data, namely, the locations of objects being tracked. In order to conserve their limited resources (power, bandwidth, storage), the sensors can compute, store, and exchange ClusterHull summaries of their data, without losing important geometric information. We are not aware of other schemes specifically designed for capturing shape information in geometric data streams, and so we compare ClusterHull with some of the best general-purpose clustering schemes such as CURE, k-median, and LSEARCH. We show through experiments that ClusterHull is able to represent the shape of two-dimensional data streams more faithfully and flexibly than the stream versions of these clustering algorithms.

Modern computer systems are called on to deal with billions of events every second, whether they are instructions executed, memory locations accessed, or packets forwarded. This presents a serious challenge to those who seek to quantify, analyze, or optimize such systems, because important trends and behaviors may easily be lost in a sea of data. We present range adaptive profiling (RAP) as a new and general purpose profiling method capable of hierarchically classifying streams of data efficiently in hardware. Through the use of RAP, events in an input stream are dynamically classified into increasingly precise categories based on the frequency with which they occur. The more important a class, or range of events, the more precisely it is quantified. Despite the dynamic nature of our technique, we build upon tight theoretic bounds covering both worst-case error as well as the required memory. In the limit, it is known that error and the memory bounds can be independent of the stream size, and grow only linearly with the level of precision desired. Significantly, we expose the critical constants in these algorithms and through careful engineering, algorithm re-design, and use of heuristics, we show how a high performance profile system can be implemented for range adaptive profiling. RAP can be used on various profiles such as PCs, load values, and memory addresses, and has a broad range of uses, from hot-region profiling to quantifying cache miss value locality. We propose two methods of implementation, one in software and the other with specialized hardware, and we show that with just 8k bytes of memory range profiles can be gathered with an average accuracy of 98%.

Recently there has been a growing interest in detecting patterns and analyzing trends in data that are generated continuously, often delivered in some fixed order and at a rapid rate, in the form of a data stream [5, 6]. When the stream consists of spatial data, its geometric "shape" can convey important qualitative aspects of the data set more effectively than many numerical statistics. In a stream setting, where the data must be constantly discarded and compressed, special care must be taken to ensure that the compressed summary faithfully captures the overall shape of the point distribution. We propose a novel scheme, ClusterHulls, to represent the shape of a stream of two-dimensional points. Our scheme is particularly useful when the input contains clusters with widely varying shapes and sizes, and the boundary shape, orientation, or volume of those clusters may be important in the analysis.

We explore fundamental performance limits of tracking a target in a two-dimensional field of binary proximity sensors, and design algorithms that attain those limits. In particular, using geometric and probabilistic analysis of an idealized model, we prove that the achievable spatial resolution Δ in localizing a target's trajectory is of the order of 1overρ R, where R is the sensing radius and ρ is the sensor density per unit area. Using an Occam's razor approach, we then design a geometric algorithm for computing an economical (in descriptive complexity) piecewise linear path that approximates the trajectory within this fundamental limit of accuracy. We employ analogies between binary sensing and sampling theory to contend that only a "lowpass" approximation of the trajectory is attainable, and explore the implications of this obervation for estimating the target's velocity.We show through simulation the effectiveness of the geometric algorithm in tracking both the trajectory and the velocity of the target for idealized models. For non-ideal sensors exhibiting sensing errors, the geometric algorithm can yield poor performance. We show that non-idealities can be handled well using a particle filter based approach, and that geometric post-processing of the output of the Particle Filter algorithm yields an economical path description as in the idealized setting. Finally, we report on our lab-scale experiments using motes with acoustic sensors to validate our theoretical and simulation results.

We propose a low overhead scheme for detecting a network partition or cut in a sensor network. Consider a network S of n sensors, modeled as points in a two-dimensional plane. An /spl epsiv/-cut, for any 0</spl epsiv/<1, is a linear separation of /spl epsiv/n nodes in S from a distinguished node, the base station. We show that the base station can detect whenever an /spl epsiv/-cut occurs by monitoring the status of just O(1//spl epsiv/) nodes in the network. Our scheme is deterministic and it is free of false positives: no reported cut has size smaller than 1/2/spl epsiv/n. Besides this combinatorial result, we also propose efficient algorithms for finding the O(1//spl epsiv/) nodes that should act as sentinels, and report on our simulation results, comparing the sentinel algorithm with two natural schemes based on sampling.

Heavy hitters, which are items occurring with frequency above a given threshold, are an important aggregation and summary tool when processing data streams or data warehouses. Hierarchical heavy hitters (HHHs) have been introduced as a natural generalization for hierarchical data domains, including multi-dimensional data. An item x in a hierarchy is called a ϕ-HHH if its frequency after discounting the frequencies of all its descendant hierarchical heavy hitters exceeds ϕn, where ϕ is a user-specified parameter and n is the size of the data set. Recently, single-pass schemes have been proposed for computing ϕ-HHHs using space roughly O(1/ϕ log(ϕn)). The frequency estimates of these algorithms, however, hold only for the total frequencies of items, and not the discounted frequencies; this leads to false positives because the discounted frequency can be significantly smaller than the total frequency. This paper attempts to explain the difficulty of finding hierarchical heavy hitters with better accuracy. We show that a single-pass deterministic scheme that computes ϕ-HHHs in a d-dimensional hierarchy with any approximation guarantee must use Ω(1/ϕd+1) space. This bound is tight: in fact, we present a data stream algorithm that can report the ϕ-HHHs without false positives in O(1/ϕd+1) space.

Wireless sensor networks offer the potential to span and monitor large geographical areas inexpensively. Sensors, however, have significant power constraint (battery life), making communication very expensive. Another important issue in the context of sensor-based information systems is that individual sensor readings are inherently unreliable. In order to address these two aspects, sensor database systems like TinyDB and Cougar enable in-network data aggregation to reduce the communication cost and improve reliability. The existing data aggregation techniques, however, are limited to relatively simple types of queries such as SUM, COUNT, AVG, and MIN/MAX. In this paper we propose a data aggregation scheme that significantly extends the class of queries that can be answered using sensor networks. These queries include (approximate) quantiles, such as the median, the most frequent data values, such as the consensus value, a histogram of the data distribution, as well as range queries. In our scheme, each sensor aggregates the data it has received from other sensors into a fixed (user specified) size message. We provide strict theoretical guarantees on the approximation quality of the queries in terms of the message size. We evaluate the performance of our aggregation scheme by simulation and demonstrate its accuracy, scalability and low resource utilization for highly variable input data sets.