Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Robustness of Colossal Patterns

  • (d,τ)-robustness: A pattern α is (d, τ)-robust if d is the maximum number of items that can be removed from α for the resulting pattern to remain a τ-core pattern of α
  • For a (d,τ)-robust pattern α, it has Ω(2^d) core patterns
    • A colossal patterns tend to have a large number of core patterns
  • Pattern distance: For patterns α and β, the pattern distance of α and β is defined to be

\[ Dist(\alpha,\beta)=1-\frac{|D_{\alpha }\cap D_{\beta }|}{|D_{\alpha }\cup D_{\beta }|} \]

  • If two patterns α and β are both core patterns of a same pattern, they would be bounded by a “ball” of a radius specified by their core ratio τ

\[ Dist(\alpha,\beta)\leq 1-\frac{1}{2/\tau -1}=r(\tau) \]

  • Once we identify one core pattern, we will be able to find all the other core patterns by a bounding ball of radius r(τ)

Speaker notes:

Content Tools


There are currently no sources for this slide.