In this paper, we study the linear separability problem for stochastic geometric objects under the well-known unipoint multipoint uncertainty models. Let @math be a given set of stochastic bichromatic points, and define @math and @math . We show that the separable-probability (SP) of @math can be computed in @math time for @math and @math time for @math , while the expected separation-margin (ESM) of @math can be computed in @math time for @math . In addition, we give an @math witness-based lower bound for computing SP, which implies the optimality of our algorithm among all those in this category. Also, a hardness result for computing ESM is given to show the difficulty of further improving our algorithm. As an extension, we generalize the same problems from points to general geometric objects, i.e., polytopes and or balls, and extend our algorithms to solve the generalized SP and ESM problems in @math and @math time, respectively. Finally, we present some applications of our algorithms to stochastic convex-hull related problems.
@cite_18: 
@cite_14: We consider the problem of nearest-neighbor searching among a set of stochastic sites, where a stochastic site is a tuple ((s_i, _i) ) consisting of a point (s_i ) in a (d )-dimensional space and a probability ( _i ) determining its existence. The problem is interesting and non-trivial even in (1 )-dimension, where the Most Likely Voronoi Diagram (LVD) is shown to have worst-case complexity ( (n^2) ). We then show that under more natural and less adversarial conditions, the size of the (1 )-dimensional LVD is significantly smaller: (1) ( (k n) ) if the input has only (k ) distinct probability values, (2) (O(n n) ) on average, and (3) (O(n n ) ) under smoothed analysis. We also present an alternative approach to the most likely nearest neighbor (LNN) search using Pareto sets, which gives a linear-space data structure and sub-linear query time in 1D for average and smoothed analysis models, as well as worst-case with a bounded number of distinct probabilities. Using the Pareto-set approach, we can also reduce the multi-dimensional LNN search to a sequence of nearest neighbor and spherical range queries.
@cite_4: Nearest-neighbor search, which returns the nearest neighbor of a query point in a set of points, is an important and widely studied problem in many fields, and it has wide range of applications. In many of them, such as sensor databases, location-based services, face recognition, and mobile data, the location of data is imprecise. We therefore study nearest-neighbor queries in a probabilistic framework in which the location of each input point is specified as a probability distribution function. We present efficient algorithms for - computing all points that are nearest neighbors of a query point with nonzero probability; and - estimating the probability of a point being the nearest neighbor of a query point, either exactly or within a specified additive error.
@cite_11: 
@cite_7: 
@cite_9: Consider a set of points in d dimensions where the existence or the location of each point is determined by a probability distribution. The convex hull of this set is a random variable distributed over exponentially many choices. We are interested in finding the most likely convex hull, namely, the one with the maximum probability of occurrence. We investigate this problem under two natural models of uncertainty: the point (also called the tuple) model where each point (site) has a fixed position s i but only exists with some probability π i , for 0 < π i ≤ 1, and the multipoint model where each point has multiple possible locations or it may not appear at all. We show that the most likely hull under the point model can be computed in O(n 3) time for n points in d = 2 dimensions, but it is NP–hard for d ≥ 3 dimensions. On the other hand, we show that the problem is NP–hard under the multipoint model even for d = 2 dimensions. We also present hardness results for approximating the probability of the most likely hull. While we focus on the most likely hull for concreteness, our results hold for other natural definitions of a probabilistic hull.
@cite_1: 
@cite_6: In recent years, a number of indirect data collection methodologies have lead to the proliferation of uncertain data. Such data points are often represented in the form of a probabilistic function, since the corresponding deterministic value is not known. This increases the challenge of mining and managing uncertain data, since the precise behavior of the underlying data is no longer known. In this paper, we provide a survey of uncertain data mining and management applications. In the field of uncertain data management, we will examine traditional methods such as join processing, query processing, selectivity estimation, OLAP queries, and indexing. In the field of uncertain data mining, we will examine traditional mining problems such as classification and clustering. We will also examine a general transform based technique for mining uncertain data. We discuss the models for uncertain data, and how they can be leveraged in a variety of applications. We discuss different methodologies to process and mine uncertain data in a variety of forms.
@cite_0: 
@cite_19: 
@cite_2: We study the complexity of geometric minimum spanning trees under a stochastic model of input: Suppose we are given a master set of points s1,s_2,...,sn in d-dimensional Euclidean space, where each point si is active with some independent and arbitrary but known probability pi. We want to compute the expected length of the minimum spanning tree (MST) of the active points. This particular form of stochastic problems is motivated by the uncertainty inherent in many sources of geometric data but has not been investigated before in computational geometry to the best of our knowledge. Our main results include the following. We show that the stochastic MST problem is SPHARD for any dimension d ≥ 2. We present a simple fully polynomial randomized approximation scheme (FPRAS) for a metric space, and thus also for any Euclidean space. For d=2, we present two deterministic approximation algorithms: an O(n4)-time constant-factor algorithm, and a PTAS based on a combination of shifted quadtrees and dynamic programming. We show that in a general metric space the tail bounds of the distribution of the MST length cannot be approximated to any multiplicative factor in polynomial time under the assumption that P ≠ NP. In addition to this existential model of stochastic input, we also briefly consider a locational model where each point is present with certainty but its location is probabilistic.
@cite_5: Abstract Consider a set of n stochastic lines in R 2 , where the existence probability of each line is determined by a fixed probability distribution. For a fixed x -coordinate q , the n lines from top to bottom can be represented by an ordered n -element sequence. Consider all the ( n k ) k -element sub-sequences of that n -element sequence. Each k -element sub-sequence has an associated likelihood to be the true k -topmost lines at x -coordinate q , and the one with the largest probability is defined as the most likely k-topmost lines at q . This paper studies the most likely k -topmost lines of the arrangement of n lines taken over all the x -coordinates. Let cnt be the total number of distinct sequences of the most likely k -topmost lines over all x -coordinates. The main result established is that the expected value of cnt is O ( k n ) , which implies that it is possible to store all the distinct most likely k -topmost lines in O ( k 2 n ) expected space. An example is given showing that cnt , in the worst case, can be Θ ( n 2 ) even when k = 1 . This highlights the value of the expected bound. An algorithm is also given to compute the most likely k -topmost lines of the arrangement. Applications of this result to the stochastic Voronoi Diagram in R 1 and to the stochastic preference top- k query in R 2 are discussed.
@cite_15: 
@cite_16: A wide range of applications have recently emerged that need to manage large, imprecise data sets. The reasons for imprecision in data are as diverse as the applications themselves: in sensor and RFID data, imprecision is due to measurement errors [15, 34]; in information extraction, imprecision comes from the inherent ambiguity in natural-language text [20, 26]; and in business intelligence, imprecision is tolerated because of the high cost of data cleaning [5]. In some applications, such as privacy, it is a requirement that the data be less precise. For example, imprecision is purposely inserted to hide sensitive attributes of individuals so that the data may be published [30]. Imprecise data has no place in traditional, precise database applications like payroll and inventory, and so, current database management systems are not prepared to deal with it. In contrast, the newly emerging applications offer value precisely because they query, search, and aggregate large volumes of imprecise data to find the “diamonds in the dirt”. This wide-variety of new applications points to the need for generic tools to manage imprecise data. In this paper, we survey the state of the art of techniques that handle imprecise data, by modeling it as probabilistic data [2–4,7,12,15,23,27,36]. A probabilistic database management system, or ProbDMS, is a system that stores large volumes of probabilistic data and supports complex queries. A ProbDMS may also need to perform some additional tasks, such as updates or recovery, but these do not differ from those in conventional database management systems and will not be discussed here. The major challenge in a ProbDMS is that it needs both to scale to large data volumes, a core competence of database management systems, and to do probabilistic inference, which is a problem studied in AI. While many scalable data management systems exists, probabilistic inference is a hard problem [35], and current systems do not scale to the same extent as data management systems do. To address this challenge, researchers have focused on the specific
@cite_12: We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input point is described by a probability distribution over a finite number of possible locations including a null location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time–space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of ( )-hull that may be a useful representation of uncertain hulls.
@cite_20: 
@cite_17: 
The study of computational geometry problems under uncertainty is a relatively new topic, and has attracted a lot of attention; see @cite_6 and @cite_16 for two surveys. Different uncertainty models and related problems have been investigated in recent years. See @cite_4 @cite_1 @cite_19 @cite_17 @cite_20 @cite_15 @cite_7 @cite_0 for example. The unipoint multipoint uncertainty model, which we use in this paper, was first defined in @cite_12 @cite_18 , and has been applied in many recent papers. For instance, in @cite_2 , studied the stochastic minimum spanning tree problem, and computed its expected length. investigated the most likely convex hull problem over uncertain data in @cite_9 ; the similar topic was revisited by in @cite_12 to compute the probability that a query point is inside the uncertain hull. In @cite_14 , Suri and Verbeek studied the most likely Voronoi Diagram (LVD) in @math under the unipoint model, and the expected complexity of LVD was further improved by in @cite_5 , who explored the stochastic line arrangement problem in @math . In @cite_11 , proposed efficient algorithms for the most likely skyline problem in @math and gave NP-hardness results in higher dimensions.