We study a class of private learning problems in which the data is a join of private and public features. This is often the case in private personalization tasks such as recommendation or ad prediction, in which features related to individuals are sensitive, while features related to items (the movies or songs to be recommended, or the ads to be shown to users) are publicly available and do not require protection. A natural question is whether private algorithms can achieve higher utility in the presence of public features. We give a positive answer for multi-encoder models where one of the encoders operates on public features. We develop new algorithms that take advantage of this separation by only protecting certain sufficient statistics (instead of adding noise to the gradient). This method has a guaranteed utility improvement for linear regression, and importantly, achieves the state of the art on two standard private recommendation benchmarks, demonstrating the importance of methods that adapt to the private-public feature separation.

We study the problem of multi-task learning under user-level differential privacy, in which n users contribute data to m tasks, each involving a subset of users. One important aspect of the problem, that can significantly impact quality, is the distribution skew among tasks. Tasks that have much fewer data samples than others are more susceptible to the noise added for privacy. It is natural to ask whether algorithms can adapt to this skew to improve the overall utility. We give a systematic analysis of the problem, by studying how to optimally allocate a user’s privacy budget among tasks. We propose a generic algorithm, based on an adaptive reweighting of the empirical loss, and show that in the presence of distribution skew, this gives a quantifiable improvement of excess empirical risk. Experimental studies on recommendation problems that exhibit a long tail of small tasks, demonstrate that our methods significantly improve utility, achieving the state of the art on two standard benchmarks.

We consider the problem of training private recommendation models with access to public item features. Training with Differential Privacy (DP) offers strong privacy guarantees, at the expense of loss in recommendation quality. We show that incorporating public item features during training can help mitigate this loss in quality. We propose a general approach based on collective matrix factorization (CMF), that works by simultaneously factorizing two matrices: the user feedback matrix (representing sensitive data) and an item feature matrix that encodes publicly available (non-sensitive) item information.

Matrix factorization learned by implicit alternating least squares (iALS) is a popular baseline in recommender system research publications. iALS is known to be one of the most computationally efficient and scalable collaborative filtering methods. However, recent studies suggest that its prediction quality is not competitive with the current state of the art, in particular autoencoders and other item-based collaborative filtering methods. In this work, we revisit four well-studied benchmarks where iALS was reported to perform poorly and show that with proper tuning, iALS is highly competitive and outperforms any method on at least half of the comparisons. We hope that these high quality results together with iALS’s known scalability spark new interest in applying and further improving this decade old technique.

We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method that achieves: i) (nearly) optimal sample complexity for matrix completion (in terms of number of items, users), and ii) the best known privacy/utility trade-off both theoretically, as well as on benchmark data sets. In particular, we provide the first global convergence analysis of ALS with noise introduced to ensure DP, and show that, in comparison to the best known alternative (the Private Frank-Wolfe algorithm by Jain et al. (2018)), our error bounds scale significantly better with respect to the number of items and users, which is critical in practical problems. Extensive validation on standard benchmarks demonstrate that the algorithm, in combination with carefully designed sampling procedures, is significantly more accurate than existing techniques, thus promising to be the first practical DP embedding model.

Being able to efficiently and accurately select the top-$k$ elements with differential privacy is an integral component of various private data analysis tasks. In this paper, we present the oneshot Laplace mechanism, which generalizes the well-known Report Noisy Max \cite{dwork2014algorithmic} mechanism to reporting noisy top-$k$ elements. We show that the oneshot Laplace mechanism with a noise level of $\widetilde{O}(\sqrt{k}/\eps)$ is approximately differentially private. Compared to the previous peeling approach of running Report Noisy Max $k$ times, the oneshot Laplace mechanism only adds noises and computes the top $k$ elements once, hence much more efficient for large $k$. In addition, our proof of privacy relies on a novel coupling technique that bypasses the composition theorems so without the linear dependence on $k$ which is inherent to various composition theorems. Finally, we present a novel application of efficient top-$k$ selection in the classical problem of ranking from pairwise comparisons.

Many recent advances in neural information retrieval models, which predict top-K items given a query, learn directly from a large training set of (query, item) pairs. However, they are often insufficient when there are many previously unseen (query, item) combinations, often referred to as the cold start problem. Furthermore, the search system can be biased towards items that are frequently shown to a query previously, also known as the 'rich get richer' (a.k.a. feedback loop) problem. In light of these problems, we observed that most online content platforms have both a search and a recommender system that, while having heterogeneous input spaces, can be connected through their common output item space and a shared semantic representation. In this paper, we propose a new Zero-Shot Heterogeneous Transfer Learning framework that transfers learned knowledge from the recommender system component to improve the search component of a content platform. First, it learns representations of items and their natural-language features by predicting (item, item) correlation graphs derived from the recommender system as an auxiliary task. Then, the learned representations are transferred to solve the target search retrieval task, performing query-to-item prediction without having seen any (query, item) pairs in training. We conduct online and offline experiments on one of the world's largest search and recommender systems from Google, and present the results and lessons learned. We demonstrate that the proposed approach can achieve high performance on offline search retrieval tasks, and more importantly, achieved significant improvements on relevance and user interactions over the highly-optimized production system in online experiments.

We explore content-based representation learning strategies tailored for large-scale, uncurated music collections that afford only weak supervision through unstructured natural language metadata and co-listen statistics. At the core is a hybrid training scheme that uses classification and metric learning losses to incorporate both metadata-derived text labels and aggregate co-listen supervisory signals into a single convolutional model. The resulting joint text and audio content embedding defines a similarity metric and supports prediction of semantic text labels using a vocabulary of unprecedented granularity, which we refine using a novel word-sense disambiguation procedure. As input to simple classifier architectures, our representation achieves state-of-the-art performance on two music tagging benchmarks.

Several machine learning models involve mapping a score vector to a probability vector. Usually, this is done by projecting the score vector onto a probability simplex, and such projections are often characterized as Lipschitz continuous approximations of the argmax function, whose Lipschitz constant is controlled by a parameter that is similar to a softmax temperature. The aforementioned parameter has been observed to affect the quality of these models and is typically either treated as a constant or decayed over time. In this work, we propose a method that adapts this parameter to individual training examples. The resulting method exhibits desirable properties, such as sparsity of its support and numerically efficient implementation, and we find that it significantly outperforms competing non-adaptive projection methods. In our analysis, we also derive the general solution of (Bregman) projections onto the (n, k)-simplex, a result which may be of independent interest.

Embedding based models have been the state of the art in collaborative filtering for over a decade. Traditionally, the dot product or higher order equivalents have been used to combine two or more embeddings, e.g., most notably in matrix factorization. In recent years, it was suggested to replace the dot product with a learned similarity e.g. using a multilayer perceptron (MLP). This approach is often referred to as neural collaborative filtering (NCF). In this work, we revisit the experiments of the NCF paper that popularized learned similarities using MLPs. First, we show that with a proper hyperparameter selection, a simple dot product substantially outperforms the proposed learned similarities. Second, while a MLP can in theory approximate any function, we show that it is non-trivial to learn a dot product with an MLP. Finally, we discuss practical issues that arise when applying MLP based similarities and show that MLPs are too costly to use for item recommendation in production environments while dot products allow to apply very efficient retrieval algorithms. We conclude that MLPs should be used with care as embedding combiner and that dot products might be a better default choice.

The recent, remarkable growth of machine learning has led to intense interest in the privacy of the data on which machine learning relies, and to new techniques for preserving privacy. However, older ideas about privacy may well remain valid and useful. This note reviews two recent works on privacy in the light of the wisdom of some of the early literature, in particular the principles distilled by Saltzer and Schroeder in the 1970s.

Machine learning techniques based on neural networks are achieving remarkable results in a wide variety of domains. Often, the training of models requires large, representative datasets, which may be crowdsourced and contain sensitive information. The models should not expose private information in these datasets. Addressing this goal, we develop new algorithmic techniques for learning and a refined analysis of privacy costs within the framework of differential privacy. Our implementation and experiments demonstrate that we can train deep neural networks with non-convex objectives, under a modest privacy budget, and at a manageable cost in software complexity, training efficiency, and model quality.

In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been a focus of a long line of work. For a given set of $d$ linear queries $A$ over a database $x \in \mathbb{R}^N$, we seek to find the differentially private mechanism that has the minimum mean squared error relative to the true answer $Ax$. For pure differential privacy, Hart and Talwar and Bhaskara et al. give an $O(\log^2 d)$ approximation to the optimal mechanism. Our first contribution is to give an $O(\log^2 d)$ approximation guarantee for the case of $(\varepsilon,\delta)$-approximate differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers and runs in time polynomial in $d$ and $N$. The mechanism is based on a recursive construction of a “small” enclosing ellipsoid of the sensitivity polytope $AB_1^N$, where $B_1^N$ denotes the $N$-dimensional $\ell_1$ ball. Optimality is established relative to the spectral lower bound, through a variant of the classical Bourgain--Tzafriri restricted invertibility theorem. We next consider this question in the case when the number of individuals $n=\|x\|_1$ in the database is smaller than the number of queries $d$. We call this the small database setting. Since the work of Blum, Ligett, and Roth [STOC '08: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008, pp. 609--618.] it has been known that such a restriction can allow for mechanisms with lower error. Our second main contribution is to give, for both pure and $(\varepsilon,\delta)$-privacy, differentially private mechanisms which have mean squared error within $\mbox{polylog}(d,N)$ of the optimal for any $A$ and $n$. The approximation is achieved by first applying the mechanism without considering the size of the database and then projecting the answer to the convex hull of feasible answers space $nAB_1^N$, which is guaranteed to contain the true answer $Ax$. By applying techniques from statistical estimation, we show such mechanisms can achieve the claimed approximation. When applied to counting queries, i.e., $A$ with entries in $\{0,1\}$, our mechanism achieves $\widetilde{O}(\sqrt{n})$ average error for both pure and $(\varepsilon,\delta)$-privacy. $\widetilde{O}$ hides polylogarithmic factors in all the parameters such as $d$, $n$, $N$, and $1/\delta$. Previously, such a bound was only known for $(\varepsilon,\delta)$-privacy. For pure privacy, this bound improves upon the $\widetilde{O}(n^{\frac{2}{3}})$ bound of Blum, Ligett, and Roth and matches the lower bound implied by I. Dinur and K. Nissim, Proceedings of the 22nd PODS, ACM, 2003, pp. 202--210 up to logarithmic factors. The third question we consider is the accuracy gap between the pure and approximate privacy notions. By applying tools from convex geometry, we make a connection between the hereditary discrepancy lower bound of S. Muthukrishnan and A. Nikolov, STOC '12: Proceedings of the 44th Symposium on Theory of Computing, 2012, pp. 1285--1292 for $(\varepsilon,\delta)$-privacy and the volume lower bound of Hardt and Talwar for pure privacy. We are able to show that the gap in error between the optimal mechanisms satisfying pure and $(\varepsilon,\delta)$-differential privacy is bounded by a factor of $O({polylog}(d,N))$. The connection between hereditary discrepancy and private mechanisms also enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix $A$.

We present a nearly optimal differentially private version of the well known LASSO estimator. Our algorithm provides privacy protection with respect to each training data item. The excess risk of our algorithm, compared to the non-private version, is $\widetilde{O}(1/n^{2/3})$, assuming all the input data has bounded $\ell_\infty$ norm. This is the first differentially private algorithm that achieves such a bound without the polynomial dependence on $p$ under no addition assumption on the design matrix. In addition, we show that this error bound is nearly optimal amongst all differentially private algorithms.

We study the effectiveness of learning low degree polynomials using neural networks by the gradient descent method. While neural networks have been shown to have great expressive power, and gradient descent has been widely used in practice for learning neural networks, few theoretical guarantees are known for such methods. In particular, it is well known that gradient descent can get stuck at local minima, even for simple classes of target functions. In this paper, we present several positive theoretical results to support the effectiveness of neural networks. We focus on two-layer neural networks (i.e. one hidden layer) where the top layer node is a linear function, similar to \citebarron93. First we show that for a randomly initialized neural network with sufficiently many hidden units, the gradient descent method can learn any low degree polynomial. Secondly, we show that if we use complex-valued weights (the target function can still be real), then under suitable conditions, there are no “robust local minima”: the neural network can always escape a local minimum by performing a random perturbation. This property does not hold for real-valued weights. Thirdly, we discuss whether sparse polynomials can be learned with \emphsmall neural networks, where the size is dependent on the sparsity of the target function.

We study the question of learning a sparse multivariate polynomial over the real domain. In particular, for some unknown polynomial f(x) of degree-d and k monomials, we show how to reconstruct f, within error ∊, given only a set of examples xi drawn uniformly from the n-dimensional cube (or an n-dimensional Gaussian distribution), together with evaluations f(i) on them. The result holds even in the “noisy setting”, where we have only values f(i) + g where g is noise (say modeled as a Gaussian random variable). The runtime of our algorithm is polynomial in n, k, 1/∊ and Cd where Cd depends only on d. Note that, in contrast, in the “boolean version” of this problem, where is drawn from the hypercube, the problem is at least as hard as the “noisy parity problem,” where we do not know how to break the nΩ(d) time barrier, even for k = 1, and some believe it may be impossible to do so.

We consider the problem of privately releasing a low dimensional approximation to a set of data records, represented as a matrix A in which each row corresponds to an individual and each column to an attribute. Our goal is to compute a subspace that captures the covariance of A as much as possible, classically known as principal component analysis (PCA). We assume that each row of A has ℓ2 norm bounded by one, and the privacy guarantee is defined with respect to addition or removal of any single row. We show that the well-known, but misnamed, randomized response algorithm, with properly tuned parameters, provides nearly optimal additive quality gap compared to the best possible singular subspace of A. We further show that when ATA has a large eigenvalue gap -- a reason often cited for PCA -- the quality improves significantly. Optimality (up to logarithmic factors) is proved using techniques inspired by the recent work of Bun, Ullman, and Vadhan on applying Tardos's fingerprinting codes to the construction of hard instances for private mechanisms for 1-way marginal queries. Along the way we define a list culling game which may be of independent interest.

In this paper, we study incentive mechanisms for retrieving information from networked agents. Following the model in [Kleinberg and Raghavan 2005], the agents are represented as nodes in an infinite tree, which is generated by a random branching process. A query is issued by the root, and each node possesses an answer with an independent probability p=1/n. Further, each node in the tree acts strategically to maximize its own payoff. In order to encourage the agents to participate in the information acquisition process, an incentive mechanism is needed to reward agents who provide the information as well as agents who help to facilitate such acquisition.

We study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries and has been the focus of a long line of work. For a given set of d linear queries over a database x ∈ RN, we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, [5, 32] give an O(log2 d) approximation to the optimal mechanism. Our first contribution is to give an efficient O(log2 d) approximation guarantee for the case of (ε,δ)-differential privacy. Our mechanism adds carefully chosen correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of [44], using tools from convex geometry. We next consider the sparse case when the number of queries exceeds the number of individuals in the database, i.e. when d > n Δ |x|1. The lower bounds used in the previous approximation algorithm no longer apply --- in fact better mechanisms are known in this setting [7, 27, 28, 31, 49]. Our second main contribution is to give an efficient (ε,δ)-differentially private mechanism that, for any given query set A and an upper bound n on |x|1, has mean squared error within polylog(d,N) of the optimal for A and n. This approximation is achieved by coupling the Gaussian noise addition approach with linear regression over the l1 ball. Additionally, we show a similar polylogarithmic approximation guarantee for the optimal ε-differentially private mechanism in this sparse setting. Our work also shows that for arbitrary counting queries, i.e. A with entries in {0,1}, there is an ε-differentially private mechanism with expected error ~O(√n) per query, improving on the ~O(n2/3) bound of [7] and matching the lower bound implied by [15] up to logarithmic factors.

We study algorithms for matching user tracks, consisting of time-ordered location points, to paths in the road network. Previous work has focused on the scenario where the location data is linearly ordered and consists of fairly dense and regular samples. In this work, we consider the multi-track map matching, where the location data comes from different trips on the same route, each with very sparse samples. This captures the realistic scenario where users repeatedly travel on regular routes and samples are sparsely collected, either due to energy consumption constraints or because samples are only collected when the user actively uses a service. In the multi-track problem, the total set of combined locations is only partially ordered, rather than globally ordered as required by previous map-matching algorithms. We propose two methods, the iterative projection scheme and the graph Laplacian scheme, to solve the multi-track problem by using a single-track map-matching subroutine. We also propose a boosting technique which may be applied to either approach to improve the accuracy of the estimated paths. In addition, in order to deal with variable sampling rates in single-track map matching, we propose a method based on a particular regularized cost function that can be adapted for different sampling rates and measurement errors. We evaluate the effectiveness of our techniques for reconstructing tracks under several different configurations of sampling error and sampling rate.

We study the optimality of the minimax risk of truncated series estimators over symmetric convex polytopes. We show that the optimal truncated series estimator is within O(log m) factor of the optimal if the polytope is defined by m hyperplanes. This represents the first such bounds towards general convex bodies. In proving our result, we first define a geometric quantity, called the approximation radius, for lower bounding the minimax risk. We then derive our bounds by establishing a connection between the approximation radius and the Kolmogorov width, the quantity that provides upper bounds for the truncated series estimator. Besides, our proof contains several ingredients which might be of independent interest: 1. The notion of approximation radius depends on the volume of the body. It is an intuitive notion and is flexible to yield strong minimax lower bounds; 2. The connection between the approximation radius and the Kolmogorov width is a consequence of a novel duality relationship on the Kolmogorov width, developed by utilizing some classical results from convex geometry [1], [18], [6].

Map matching is the procedure for determining the path of a user on a map from a sequence of location data (which we refer to as track). This process serves as a common preprocessing step for reasoning about traffic on the road network as well as for providing better location-based services [3, 5, 1]. Converting a track to a topological path on a map not only makes it easier to reason about paths, but also leads to reduced storage requirements and more efficient operations on the same. Some examples of such operations are comparison, querying and retrieval of tracks based on similarity to other tracks [1].

This paper uncovers a new phenomenon in web search that we call domain bias --- a user's propensity to believe that a page is more relevant just because it comes from a particular domain. We provide evidence of the existence of domain bias in click activity as well as in human judgments via a comprehensive collection of experiments. We begin by studying the difference between domains that a search engine surfaces and that users click. Surprisingly, we find that despite changes in the overall distribution of surfaced domains, there has not been a comparable shift in the distribution of clicked domains. Users seem to have learned the landscape of the internet and their click behavior has thus become more predictable over time. Next, we run a blind domain test, akin to a Pepsi/Coke taste test, to determine whether domains can shift a user's opinion of which page is more relevant. We find that domains can actually flip a user's preference about 25% of the time. Finally, we demonstrate the existence of systematic domain preferences, even after factoring out confounding issues such as position bias and relevance, two factors that have been used extensively in past work to explain user behavior. The existence of domain bias has numerous consequences including, for example, the importance of discounting click activity from reputable domains.

Motivated by trends in popularity of products, we present a formal model for studying trends in our choice of products in terms of three parameters: (1) their innate utility; (2) individual boredom associated with repeated usage of an item; and (3) social influences associated with the preferences from other people. Different from previous work, in this paper we introduce boredom to explain the cyclic pattern in individual and social choices. We formally model boredom and show that a rational individual would make cyclic choices when considering the boredom factor. Furthermore, we extend the model to social choices by showing that a society that votes for a particular style or product can be viewed as a single individual cycling through different choices.

Influence maximization is the problem of finding a small set of most influential nodes in a social network so that their aggregated influence in the network is maximized. In this paper, we study influence maximization in the linear threshold model, one of the important models formalizing the behavior of influence propagation in social networks. We first show that computing exact influence in general networks in the linear threshold model is #P-hard, which closes an open problem left in the seminal work on influence maximization by Kempe, Kleinberg, and Tardos, 2003. As a contrast, we show that computing influence in directed a cyclic graphs (DAGs) can be done in time linear to the size of the graphs. Based on the fast computation in DAGs, we propose the first scalable influence maximization algorithm tailored for the linear threshold model. We conduct extensive simulations to show that our algorithm is scalable to networks with millions of nodes and edges, is orders of magnitude faster than the greedy approximation algorithm proposed by Kempe et al. and its optimized versions, and performs consistently among the best algorithms while other heuristic algorithms not design specifically for the linear threshold model have unstable performances on different real-world networks.

We study the problem of allocating shared resources, such as bandwidth in computer networks and computational resources in shared clusters, among multiple users by the proportional-share market mechanism. Under this mechanism, each user partitions his budget among the multiple resources and receives a fraction of each resource proportional to his bid. We first formulate the resource allocation game under the proportional-share mechanism and study the efficiency and fairness of the equilibrium in this game. We present analytic and simulation results demonstrating that the proportional-share mechanism achieves a reasonable balance of high degrees of efficiency and fairness at the equilibrium.

An unweighted graph has density rho and growth rate k if the number of nodes in every ball with radius r is bounded by rhork. The communication graphs of wireless networks and peer-to-peer networks often have constant bounded density and small growth rate. In this paper, we study the trade-off between two quality measures for routing in growth-restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load-balancing ratio, which measures the evenness of the traffic distribution. We show that if the routing algorithm is required to use paths with stretch factor c, then its load-balancing ratio is bounded by O(rho1/k(n/c)1-1/k), and the bound is tight in the worst case. We show the application and extension of the trade-off to the wireless network routing and VLSI layout design. We also present a load-balanced routing algorithm with the stretch factor constraint in an online setting, in which the routing requests come one by one.

One of the main reasons of the recent success of peer to peer (P2P)file sharing systems such as BitTorrent is their built-in tit-for-tat mechanism. In this paper, we model the bandwidth allocation in a P2P system as an exchange economy and study a tit-for-tat dynamics, namely the proportional response dynamics, in this economy. In aproportional response dynamics each player distributes its good to its neighbors proportional to the utility it received from them in thelast period. We show that this dynamics not only converges but converges to a market equilibrium, a standard economic characterization of efficient exchanges in a competitive market. In addition, for some classes of utility functions we consider, it converges much faster than the classical tat process and any existingalgorithms for computing market equilibria.

We study routing algorithms on wireless networks that use only short paths, for minimizing latency, and achieve good load balance, for balancing the energy use. We consider the special case when all the nodes are located in a narrow strip with width at most /spl radic/3/2 /spl ap/ 0.86 times the communication radius. We present algorithms that achieve good performance in terms of both measures simultaneously. In particular, the routing path is at most four times the shortest path length and the maximum load on any node is at most three times that of the most load-balanced algorithm without path-length constraint. In addition, our routing algorithms make routing decisions by only local information and, as a consequence, are more adaptive to topology changes due to dynamic node insertions/deletions or due to mobility.

We present gradient landmark-based distributed routing (GLIDER), a novel naming/addressing scheme and associated routing algorithm, for a network of wireless communicating nodes. We assume that the nodes are fixed (though their geographic locations are not necessarily known), and that each node can communicate wirelessly with some of its geographic neighbors - a common scenario in sensor networks. We develop a protocol which in a preprocessing phase discovers the global topology of the sensor field and, as a byproduct, partitions the nodes into routable tiles - regions where the node placement is sufficiently dense and regular that local greedy methods can work well. Such global topology includes not just connectivity but also higher order topological features, such as the presence of holes. We address each node by the name of the tile containing it and a set of local coordinates derived from connectivity graph distances between the node and certain landmark nodes associated with its own and neighboring tiles. We use the tile adjacency graph for global route planning and the local coordinates for realizing actual inter- and intra-tile routes. We show that efficient load-balanced global routing can be implemented quite simply using such a scheme.

In this paper we formulate the fixed budget resource allocation game to understand the performance of a distributed market-based resource allocation system. Multiple users decide how to distribute their budget bids) among multiple machines according to their individual preferences to maximize their individual utility. We look at both the efficiency and the fairness of the allocation at the equilibrium, where fairness is evaluated through the measures of utility uniformity and envy-freeness. We show analytically and through simulations that despite being highly decentralized, such a system converges quickly to an equilibrium and unlike the social optimum that achieves high efficiency but poor fairness, the proposed allocation scheme achieves a nice balance of high degrees of efficiency and fairness at the equilibrium.

We propose a new routing graph, the restricted Delaunay graph (RDG), for mobile ad hoc networks. Combined with a node clustering algorithm, the RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: 1) it is planar; 2) between any two graph nodes there exists a path whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the minimum length possible; and 3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We show by simulation that the RDG outperforms previously proposed routing graphs in the context of the Greedy perimeter stateless routing (GPSR) protocol. Finally, we investigate theoretical bounds on the quality of paths discovered using GPSR.

We extend the classic notion of well-separated pair decomposition [P. B. Callahan and S. R. Kosaraju, J. ACM, 42 (1975), pp. 67--90] to theunit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points in the plane and for any constant $c\geq 1$, there exists a c-well-separated pair decomposition with O(n log n) pairs, and the decomposition can be computed in O(n log n) time. We also show that for the unit-ball graph metric in k dimensions where $k\geq 3$, there exists a c-well-separated pair decomposition with O(n 2-2/k ) pairs, and the bound is tight in the worst case. We present the application of the well-separated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.

We study wireless network routing algorithms that use only short paths, for minimizing latency, and achieve good load balance, for balancing the energy use. We consider the special case when all the nodes are located in a narrow strip with width at most /spl radic/3/2 /spl ap/ 0.86 times the communication radius. We present algorithms that achieve good performance in terms of both measures simultaneously. In addition, our algorithms only use local information and can deal with dynamic change and mobility efficiently.

We address the problem of distributed information aggregation and storage in a sensor network, where queries can be injected anywhere in the network. The principle we propose is that a sensor should know a "fraction" of the information from distant parts of the network, in an exponentially decaying fashion by distance. We show how a sampled scalar field can be stored in this distributed fashion, with only a modest amount of additional storage and network traffic. Our storage scheme makes neighboring sensors have highly correlated world views; this allows smooth information gradients and enables local search algorithms to work well. We study in particular how this principle of fractionally cascaded information can be exploited to answer range queries about the sampled field efficiently. Using local decisions only we are able to route the query to exactly the portions of the field where the sought information is stored. We provide a rigorous theoretical analysis showing that our scheme is close to optimal.

A graph has growth rate k if the number of nodes in any subgraph with diameter r is bounded by O(rk). The communication graphs of wireless networks and peer-to-peer networks often have small growth rate. In this paper we study the tradeoff between two quality measures for routing in growth restricted graphs. The two measures we consider are the stretch factor, which measures the lengths of the routing paths, and the load balancing ratio, which measures how evenly the traffic is distributed. We show that if the routing algorithm is required to use paths with stretch factor c, then its load balancing ratio is bounded by O((n/c)1-1/k), where k is the graph's growth rate. We illustrate our results by focusing on the unit disk graph for modeling wireless networks in which two nodes have direct communication if their distance is under certain threshold. We show that if the maximum density of the nodes is bounded by ρ, there exists routing scheme such that the stretch factor of routing paths is at most c, and the maximum load on the nodes is at most O(min(√ρn/c, n/c)) times the optimum. In addition, the bound on the load balancing ratio is tight in the worst case. As a special case, when the density is bounded by a constant, the shortest path routing has a load balancing ratio of O(√n). The result extends to k-dimensional unit ball graphs and graphs with growth rate k. We also discuss algorithmic issues for load balanced short path routing and for load balanced routing in spanner graphs.

We extend the classic notion of well-separated pair decomposition [10] to the (weighted) unit-disk graph metric: the shortest path distance metric induced by the intersection graph of unit disks. We show that for the unit-disk graph metric of n points in the plane and for any constant c≥1, there exists a c-well-separated pair decomposition with O(n log n) pairs, and the decomposition can be computed in O(n log n) time. We also show that for the unit-ball graph metric in k dimensions where k≥3, there exists a c-well-separated pair decomposition with O(n2-2/k) pairs, and the bound is tight in the worst case. We present the application of the well-separated pair decomposition in obtaining efficient algorithms for approximating the diameter, closest pair, nearest neighbor, center, median, and stretch factor, all under the unit-disk graph metric.

Structural comparison of large trees is a difficult task that is only partially supported by current visualization techniques, which are mainly designed for browsing. We present TreeJuxtaposer, a system designed to support the comparison task for large trees of several hundred thousand nodes. We introduce the idea of "guaranteed visibility", where highlighted areas are treated as landmarks that must remain visually apparent at all times. We propose a new methodology for detailed structural comparison between two trees and provide a new nearly-linear algorithm for computing the best corresponding node from one tree to another. In addition, we present a new rectilinear Focus+Context technique for navigation that is well suited to the dynamic linking of side-by-side views while guaranteeing landmark visibility and constant frame rates. These three contributions result in a system delivering a fluid exploration experience that scales both in the size of the dataset and the number of pixels in the display. We have based the design decisions for our system on the needs of a target audience of biologists who must understand the structural details of many phylogenetic, or evolutionary, trees. Our tool is also useful in many other application domains where tree comparison is needed, ranging from network management to call graph optimization to genealogy.

In this paper, we propose to study deformable necklaces --- flexible chains of balls, called beads, in which only adjacent balls may intersect. Such objects can be used to model macro-molecules, muscles, rope, and other 'linear' objects in the physical world. In this paper, we exploit this linearity to develop geometric structures associated with necklaces that are useful in physical simulations. We show how these structures can be implemented efficiently and maintained under necklace deformation. In particular, we study a bounding volume hierarchy based on spheres built on a necklace. Such a hierarchy is easy to compute and is suitable for maintenance when the necklace deforms, as our theoretical and experimental results show. This hierarchy can be used for collision and self-collision detection. In particular, we achieve an upper bound of O(nlog n) in two dimensions and O(n 2-2/d) in d-dimensions, d 3, for collision checking. To our knowledge, this is the first sub-quadratic bound proved for a collision detection algorithm using predefined hierarchies. In addition, we show that the power diagram, with the help of some additional mechanisms, can be also used to detect self-collisions of a necklace in certain ways complementary to the sphere hierarchy.

In this paper, we study the design of fault-tolerant networks for arrays and meshes by adding redundant nodes and edges. For a target graph G (linear array or mesh in this paper), a graph G' is called a k-fault-tolerant graph of G if when we remove any k nodes from G', it still contains a subgraph isomorphic to G. The major quality measures for a fault-tolerant graph are the number of spare nodes it uses and the maximum degree it has. The degree is particularly important in practice as it poses constraints on the scalability of the system. In this paper, we aim at designing fault-tolerant graphs with both a small degree and a small number of spare nodes. The fault-tolerant graphs we obtain have degree O(1) for arrays and O(log/sup 3/ k) for meshes. The number of spare nodes used are O(k log/sup 2/ k) and O(k/sup 2//log k), respectively. Compared to the previous results, the number of spare nodes used in our construction has one fewer linear factor in k.

\emph{We propose a new randomized algorithm for maintaining a set of c lusters among moving nodes in the plane. Given a specified cluster radius, our algorithm selects and maintains a variable subset of the nodes as cluster centers. This subset has the property that (1) balls of the given radius centered at the chosen nodes cover all the others and (2) the number of centers selected is a constant-factor approximation of the minimum possible. As the nodes move, an event-based kinetic data structure updates the clustering as necessary. This kinetic data structure is shown to be responsive, efficient, local, and compact. The produced cover is also smooth, in the sense that wholesale cluster re-arrangements are avoided. The algorithm can be implemented without exact knowledge of the node positions, if each node is able to sense its distance to other nodes up to the cluster radius. Such a kinetic clustering can be used in numerous applications where mobile devices must be interconnected into an ad-hoc network to collaboratively perform some task.}

Efficient collision detection is important in many robotic tasks, from high-level motion planning in a static environment to low-level reactive behavior in dynamic situations. Specially challenging are problems in which multiple robots are moving among multiple moving obstacles. In this paper we present a number of collision detection algorithms formulated under the kinetic data structures (KDS) framework, a framework for design and analyzing algorithms for objects in motion. The KDS framework leads to event-based algorithms that sample the state of different parts of the system only as often as necessary for the task at hand. Earlier work has demonstrated the theoretical efficiency of KDS algorithms. In this paper we present new algorithms and demonstrate their practical efficiency as well as by an implementable and direct comparison with classical broad and narrow phase collision detection techniques.

We propose a new routing graph, the Restricted Delaunay Graph (RDG), for ad hoc networks. Combined with a node clustering algorithm RDG can be used as an underlying graph for geographic routing protocols. This graph has the following attractive properties: (1) it is a planar graph; (2) between any two nodes there exists a path in the RDG whose length, whether measured in terms of topological or Euclidean distance, is only a constant times the optimum length possible; and (3) the graph can be maintained efficiently in a distributed manner when the nodes move around. Furthermore, each node only needs constant time to make routing decisions. We also show by simulation that the RDG outperforms the previously proposed routing graphs under the Greedy Perimeter Stateless Routing (GPSR) protocol. In addition, we investigate theoretical bounds on the quality of paths discovered using GPSR

We describe a kinetic data structure (KDS) that maintains the connected components of the union of a set of unit-radius disks moving in the plane. We assume that the motion of each disk can be specified by a low-degree algebraic trajectory; this trajectory, however, can be modified in an on-line fashion. While the disks move continuously, their connectivity changes at discrete times. Our main result is an O(n) space data structure that takes O(log n/ log log n) time per connectivity query of the form "are disks A and B in the same connected component?" A straightforward approach based on dynamically maintaining the overlap graph requires## n 2 ) space. Our data structure requires only linear space and must deal with O(n 2+# ) updates in the worst case, each requiring O(log 2 n) amortized time. This number of updates is close to optimal, since a set of n moving unit disks can undergo## n 2 ) connectivity changes. 1 Introduction Motivated by applications in mobile ...

This paper presents the Hierarchical Walk, or H-Walk algorithm, which maintains the distance between two moving convex bodies by exploiting both motion coherence and hierarchical representations. For convex polygons, we prove that H-Walk improves on the classic Lin–Canny and Dobkin–Kirkpatrick algorithms. We have implemented H-Walk for moving convex polyhedra in three dimensions. Experimental results indicate that, unlike previous incremental distance computation algorithms, H-Walk adapts well to variable coherence in the motion and provides consistent performance.

No abstract available.

Article H-Walk: hierarchical distance computation for moving convex bodies Share on Authors: Leonidas J. Guibas Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , David Hsu Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile , Li Zhang Computer Science Department, Stanford University, Stanford, CA Computer Science Department, Stanford University, Stanford, CAView Profile Authors Info & Claims SCG '99: Proceedings of the fifteenth annual symposium on Computational geometryJune 1999 Pages 265–273https://doi.org/10.1145/304893.304979Published:13 June 1999 32citation306DownloadsMetricsTotal Citations32Total Downloads306Last 12 Months7Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

this paper is to study and validate the use of the kinetic data structures proposed in [BGH97] in practice. The implementation and experimental evaluation of such structures brings to light several important issues which were not addressed in the original paper. For instance, KDSs implement the continuous maintenance of the function of interest through a discrete-event simulation. The calculation of the event times poses numerical difficulties which raise questions about the integrity of the structure if nearby events should happen out of order, or if the time of an event changes when recalculated. Also, the algorithmic measures for evaluating the quality of KDSs in [BGH97] are all worst-case measures, which may not reflect behavior under ordinary motions which occur in practice. It may well be that simple data structures do better in such situations. In order to study these issues, we have compared the KDSs of [BGH97] with simpler variants under various common data/motion distributions, each meant to generate a different amount of

A kinetic data structure for the maintenance of a multidimensional range search tree is introduced.This structure is used as a building block to obtain kinetic data structures for two classical geometric proximity problems in arbitrary dlmensions: the first structure maintains the closest pair of a set of continuously moving points, and is provably efficient.The second structure maintains a spanning tree of the moving points whose cost remains within some prescribed factor of the minimum spanning tree.

We initiate a probabilistic study of configuration functions of moving points.In our probabilistic model, a particle is given an initiaf position and a velocity drawn independently at random from the same distribution D. We show that if n particles are drawn independently at random from the uniform distribution on the square, their convex hull undergoes El(logz n) combinatorial changes in expectation, their Voronoi diagram undergoes e(n312 ) combinatorial changes, and their closest pair undergoes El(n) combinatorial changes.