Hypersphere Dominance: An Optimal Approach Overview

In this study, the concept of hypersphere dominance is explored, discussing its definition, existing solutions, and applications in uncertain databases. The analysis covers the decision-making process based on distance calculations within hyperspheres in multi-dimensional space. Various scenarios are presented to illustrate the practical implications of hypersphere dominance.

• Hypersphere
• Dominance
• Optimal Approach
• Uncertain Databases
• Multi-dimensional

zlipf Follow

Uploaded on Apr 20, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Hypersphere Dominance: An Optimal Approach Cheng Long, Raymond Chi-Wing Wong, Bin Zhang, Min Xie The Hong Kong University of Science and Technology Prepared by Cheng Long Presented by Cheng Long 24 June, 2014 1

2. Hyperspheres A hypersphere in a d-dimensional space (center, radius) the set of all points that have their distances from the center bounded by the radius ? ? ? ? 2D: a disk 3D: a ball 2

3. Hyperspheres are commonly used Uncertain databases the location of an uncertain object Spatial databases SS-tree, SS+-tree, M-tree, VP-tree and SR-tree SS-tree: similar to R-tree with hyperrectangles replaced by hyperspheres layout of 8 objects: A-H SS-tree based on A-H 3

4. Motivating example Scenario Ada has her location uncertain, but constrained in a disk Sa. Bob has his location uncertain, but constrained in a disk Sb. Connie has her location uncertain, but constrained in a disk Sq. Question Is Ada always closer to Connie than Bob? ?? (Ada) Sq (Connie) ?? (Ada) Sb (Bob) Sb (Bob) Sq (Connie) For this specification of the locations, Ada is closer to Connie than Bob In fact, for all specifications of the locations, Ada is closer to Connie than Bob Yes No 4

5. Hypersphere dominance: definition Definition 1: Hypersphere dominance Given ??, ??, and ??, it decides whether ? ??, ? ??, ? ??, ???? ?,? < ????(?,?) Dominance condition Yes:??? ??,??,?? = ???? No: ??? ??,??,?? = ????? Basic operator used in many queries Probabilistic RkNN query [Lian and Chen, VLDBJ 09] AkNN query [Emrich et al., SSDBM 10] kNN query [Long et al., SIGMOD 14] 5

6. Hypersphere dominance: existing solutions overview MinMax [Roussopoulos et al., SIGMOD Record 95; Hjaltason and Samet, TODS 99] MBR [Emrich et al., SIGMOD 10] GP [Lian and Chen, VLDBJ 09] Trigonometric [Emrich et al., SSDBM 10] 6

7. Hypersphere dominance: existing solutions MinMax (1) Definition: ???????(??,??) the minimum distance between a point in Sa and a point in Sb Definition: ???????(??,??) the maximum distance between a point in ?? and a point in Sb ???????(??,??)= 0 (?? and ????(??, ??) ?? ?? (?? and ??????? ??,?? = ???? ??,??+ ??+ ?? and S Sb b overlap overlap) and S Sb b do not overlap do not overlap) ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???????(??,??) ???????(??,??) ???????(??,??) = 0 7

8. Hypersphere dominance: existing solutions MinMax (2) MinMax Compute ???????(??,??) Compute ???????(??,??) If???????(??,??) < ???????(??,??) Return???? Else Return????? ???????(??,??)> ???????(??,??) Sq ???????(??,??) ???????(??,??)< ???????(??,??) ?? bisector ?? and ?? ?? Sq Sb ???????(??,??) Sb ???????(??,??) ???????(??,??) MinMax MinMax returns ????? MinMax MinMax returns ???? 8 ???(??,??,??) = ???? ???(??,??,??) = ???? false negative false negative correct correct

9. Criteria of a method: 1. Correctness: No false positive 2. Soundness: No false negative 3. Efficiency: runs in O(d) where d is the number of dimensionality Hypersphere dominance: existing solutions--Insufficiency Methods MinMax MBR GP Trigonometric Our approach (Hyperbola) Correct? Yes Yes Yes No Yes Sound? No No No Yes Yes Efficient? Yes Yes Yes Yes Yes Our approach is the only only one which is correct, sound and efficient correct, sound and efficient! 9

10. For cases where it is easy the dominance condition is true For cases where it is difficult the dominance condition is true directly easy to decide whether Our approach: major idea difficult to decide whether Step 1: pre-checking Do the decision directly Step 2: dominance checking Drive an equivalent condition of ???(??,??,??) = ???? which is easier to decide Do the decision 10

11. Our approach: pre-checking Step 1: Pre-checking: If?? and Sb overlap Return????? IfSb and Sq overlap Return????? ?? and Sb overlap Sb and Sq overlap ???(??,??,??) = ????? ???(??,??,??) = ????? Sq Sq ?? ?? Sb Sb 11

12. Our approach: dominance checking (1) Step 2: Dominance checking: Derive an equivalent condition of ??? ??,??,?? = ???? and check whether the derived condition is true Dominance condition: ? ??, ? ??, ? ??,???? ?,? < ????(?,?) Equivalent condition (1): ? ??,??????? ?,?? < ??????? ?,?? Proof of the equivalence between Condition (1) and Condition (2) Proof of the equivalence between Condition (1) and Condition (2): : => : => : By contradiction <= : <= : ? ??, ? ??, ? ??,???? ?,? < ??????? ?,?? < ??????? ?,?? < ????(?,?) 12

13. Our approach: dominance checking (5) Equivalent condition (2): ? ??,??????? ?,?? < ??????? ?,?? ??????? ?,??= ???? ?,??+ ??+ 0 = ???? ?,??+ ?? ?in????(?,??) = ???? ?,?? ?? 0 = ???? ?,?? ?? Equivalent condition (3): ? ??,???? ?,c? ???? ?,?? > ??+ ?? 13

14. Space partitioning: Boundary ?: ???? ?,?? ???? ?,?? = ??+ ?? Region ??: ???? ?,?? ???? ?,?? > ??+ ?? Our approach: dominance checking (3) Region ??: ???? ?,?? ???? ?,?? < ??+ ?? Equivalent condition (3): ? ??,???? ?,c? ???? ?,?? > ??+ ?? Equivalent condition (4): ? ??,? is in Region ?? (?? is in Region ??) Boundary Boundary ?: ???? ?,?? ???? ?,?? = ??+?? Sq Region Region R Ra a cq Sa ca Region Region R Rb b Sb cb 14

15. Our approach: dominance checking (4) Equivalent condition (4): ?? is in Region ?? Equivalent condition (5): ?? is in Region ?? and ???? ????? ??,? > ?? ?? is Region ?? Boundary Boundary ?: ???? ?,?? ???? ?,?? = ??+?? Sq Region Region R Ra a cq rq ?? is in Region ?? Sa ca Region Region R Rb b ???? ????? ??,? > ?? ???? ????? ??,? Sb cb 15

16. Space partitioning: Boundary ?: ???? ?,?? ???? ?,?? = ??+ ?? Region ??: ???? ?,?? ???? ?,?? > ??+ ?? Region ??: ???? ?,?? ???? ?,?? < ??+ ?? Our approach (2) Equivalent condition (5): ?? is in Region ?? and ???? ????? ??,? > ?? Compute ???? ????? ??,? constraint: ???? ?,?? ???? ?,?? = ??+ ?? objective: minimize ????(??,?) We use the Lagrange Multiplier (LM) method. Details could be found in the paper sound efficient correct Each condition transformation takes O(d) time and the cost of LM is also O(d) The condition (3) is equivalent to the dominance condition 16

17. Criteria of a method: 1. Correctness: No false positive (FP) 2. Soundness: No false negative (FN) 3. Efficiency: runs in O(d) where d is the number of dimensionality Empirical study: set-up Datasets: Real datasets: NBA, Color, Texture, and Forest Synthetic datasets Algorithms: MinMax, MBR, GP, Trigonometric, Hyperbola (our method) Measures: precision = TP/(TP+FP) recall = TP/(TP+FN) running time A sound sound method has the recall always equal to 1 A correct correct method has the precision always equal to 1 equal to 1 17 equal to 1

18. Methods Correct? Sound? Efficient? MinMax Yes No Yes MBR Yes No Yes Empirical study: results (precision, NBA) GP Yes No Yes Trigonometric No Yes Yes Our approach Yes Yes Yes All algorithms except Trigonometric have precisions = 1. 18

19. Methods Correct? Sound? Efficient? MinMax Yes No Yes MBR Yes No Yes Empirical study: results (recall, NBA) GP Yes No Yes Trigonometric No Yes Yes Our approach Yes Yes Yes Only our approach (Hyperbola) and Trigonometirc have recalls = 1. 19

20. Empirical study: results (running time, NBA) MinMax < GP < Hyperbola (our method) < MBR < Trigonometric 20

21. Conclusion First solution for the hypersphere dominance problem, which is correct, sound and efficient for any dimension An application study: kNN Experiments 21

22. Q & A 22

23. The following slides are for backup use only 23

24. Hyperspheres in uncertain databases Song and Roussopoulos [SSTD 01] Cheng et al. [TKDE 04] Chen and Cheng [ICDE 07] Beskales et al. [PVLDB 08] 24

25. Definition 1: Hypersphere dominance Given ??, ??, and ??, Dominance condition Yes:??? ??,??,?? = ???? No: ??? ??,??,?? = ????? Our approach (1) it decides whether ? ??, ? ??, ? ??, ???? ?,? < ????(?,?) Major idea: Derive an equivalent condition of ??? ??,??,?? = ???? and check whether the derived condition is true Dominance condition: ? ??, ? ??, ? ??,???? ?,? < ????(?,?) Equivalent condition (1): : ? ??,??????? ?,?? < ??????? ?,?? Equivalent condition (2): ? ??,???? ?,c? ???? ?,?? > ??+ ?? Equivalent condition (3): ???? ??,?? ???? ??,?? > ??+ ?? and ???? ????? ??,? > ?? ? ?: ???? ?,?? ???? ?,?? = ??+ ?? 25

26. An application study: kNN qeury kNN query: Given a set D of ? hyperspheres, ?1, ?2, , ??, a query hypershere ??, and an integer ?, the query finds a set of hyperspheres in D each of which is not dominated by ?? wrt ?? where ?? is the hypersphere in D with the k-th smallest maximum distance from ??. Solution: A best-first search algorithm based on SS-tree Some pruning strategies 26

27. Boundary Boundary ?: ???? ?,?? ???? ?,?? = 0 Sq Region Region R Ra a cq Sa (??) Region Region R Rb b Sb (??) Illustration 1: 2D space, ?? and ?? are two points (i.e., ?? = 0, ?? = 0) 27