zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Towards estimating expected sizes of probabilistic skylines. (English) Zbl 1290.60018
Summary: We consider the maximal vector problem on uncertain data, which has been recently posed by the study on processing skyline queries over a probabilistic data stream in the database context. Let $D_n$ be a set of $n$ points in a $d$-dimensional space and $q (0< q\leqslant 1)$ be a probability threshold; each point in $D_n$ has a probability to occur. Our problem is concerned with how to estimate the expected size of the probabilistic skyline, which consists of all the points that are not dominated by any other point in $D_n$ with a probability not less than $q$. We prove that the upper bound of the expected size is $O(\min\{n, (\ln q)(\ln n)^{d-1}\})$ under the assumptions that the value distribution on each dimension is independent and the values of the points along each dimension are distinct. The main idea of our proof is to find a recurrence about the expected size and solve it. Our results reveal the relationship between the probability threshold $q$ and the expected size of the probabilistic skyline, and show that the upper bound is poly-logarithmic when $q$ is not extremely small.
60E15Inequalities in probability theory; stochastic orderings
60C05Combinatorial probability
Full Text: DOI
[1] Kung H T, Luccio F, Preparata F P. On finding the maxima of a set of vectors. J ACM, 1975, 22: 469--476 · Zbl 0316.68030 · doi:10.1145/321906.321910
[2] Barndorff-Nielsen O, Sobel M. On the distribution of the number of admissible points in a vector random sample. Theor Probab Appl, 1966, 11: 249--269 · Zbl 0278.60007 · doi:10.1137/1111020
[3] Bentley J L, Kung H T, Schkolnick M, et al. On the average number of maxima in a set of vectors and applications. J ACM, 1978, 25: 536--543 · Zbl 0388.68056 · doi:10.1145/322092.322095
[4] Buchta C. On the average number of maxima in a set of vectors. Inf Process Lett, 1989, 33: 63--65 · Zbl 0682.68041 · doi:10.1016/0020-0190(89)90156-7
[5] Golin M J. Maxima in convex regions. In: Proceedings of the 4th Annual ACM-SIAMSymposium on Discrete Algorithms, Philadelphia, PA, USA, 1993. 352--360 · Zbl 0802.60015
[6] Börzsönyi S, Kossmann D, Stocker K. The skyline operator. In: Proceedings of the 17th International Conference on Data Engineering, Washington DC, USA, 2001. 421--430
[7] Zhang WJ, Lin XM, Zhang Y, et al. Probabilistic skyline operator over sliding windows. In: Proceedings of International Conference on Data Engineering, Los Alamitos, CA, USA, 2009. 1060--1071
[8] Pei J, Jiang B, Lin X M, et al. Probabilistic skylines on uncertain data. In: Proceedings of the 33rd International Conference on Very Large Data Bases, Vienna, Austria, 2007. 15--26
[9] Godfrey P. Skyline cardinality for relational processing. In: Foundations of Information and Knowledge Systems, Wilhelminenburg Castle, Austria, 2004. 78--97 · Zbl 1202.68137
[10] Godfrey P, Shipley R, Gryz J. Algorithms and analyses for maximal vector computation. VLDB J, 2007, 16: 5--28 · doi:10.1007/s00778-006-0029-7
[11] Lin X M, Yuan Y D, Wang W, et al. Stabbing the sky: Efficient skyline computation over sliding windows. In: Proceedings of the 21st International Conference on Data Engineering, Washington DC, USA, 2005. 502--513
[12] Knuth D E. The Art of Computer Programming, Volume 1 (3rd ed): Fundamental Algorithms. Redwood City: Addison Wesley Longman Publishing Co, Inc, 1997 · Zbl 0895.68055