Search for: All records

We introduce the notion of an eps-cover for a kernel range space. A kernel range space concerns a set of points X in Rd and the space of all queries by a fixed kernel (e.g., a Gaussian kernel K(p,.) = exp(-|p-.|2), where p is in \Rd). For a point set X of size n, a query returns a vector of values Rp in Rn, where the i-th coordinate (Rp)i = K(p, xi)$ for xi in X$ An eps-cover is a subset of points Q in Rd so for any p in Rd$ that (1/n) |Rp - Rq|1 <= eps for some q in Q. This is a smooth analog of Haussler's notion of eps-covers for combinatorial range spaces (e.g., defined by subsets of points within a ball query) where the resulting vectors Rp are in {0, 1}n instead of [0, 1]n. The kernel versions of these range spaces show up in data analysis tasks where the coordinates may be uncertain or imprecise, and hence one wishes to add some flexibility in the notion of inside and outside of a query range. Our main result is that, unlike combinatorial range spaces, the size of kernel eps-covers is independent of the input size n and dimension d. We obtain a bound of 2O~(1/\eps^2), where O~(f(1 / eps)) hides log factors in (1 / eps) that can depend on the kernel. This implies that by relaxing the notion of boundaries in range queries, eventually the curse of dimensionality disappears, and may help explain the success of machine learning in very high-dimensions.We also complement this result with a lower bound of almost (1/\eps)Omega(1/\eps), showing the exponential dependence on 1/eps is necessary. 

Abstract The available spatial data are rapidly growing and also diversifying. One may obtain in large quantities information such as annotated point/place of interest (POIs), check-in comments on those POIs, geo-tagged microblog comments, and demarked regions of interest (ROI). All sources interplay with each other, and together build a more complete picture of the spatial and social dynamics at play in a region. However, building a single fused representation of these data entries has been mainly rudimentary, such as allowing spatial joins. In this paper, we extend the concept of semantic embedding for POIs (points of interests) and devise the first semantic embedding of ROIs, and in particular ones that captures both its spatial and its semantic components. To accomplish this, we develop a multipart network model capturing the relationships between the diverse components, and through random-walk-based approaches, use this to embed the ROIs. We demonstrate the effectiveness of this embedding at simultaneously capturing both the spatial and semantic relationships between ROIs through extensive experiments. Applications like popularity region prediction demonstrate the benefit of using ROI embedding as features in comparison with baselines.