LUDWIGMAXIMILIANSUNIVERSITYMUNICHDEPARTMENTINSTITUTE FORINFORMATICSDATABASE
SYSTEMS
GROUP

Data Mining and the 'Curse of Dimensionality'
iDB Workshop 2011

Arthur ZimekL
d i M i ili
U iität MühLudwig-Maximilians-Universität
MünchenMunich, Germany
http://www.dbs.ifi.lmu.de/~zimek
zimek@dbs.ifi.lmu.de
zimek@dbs ifi lmu deDATABASE
SYSTEMSGROUP

Outline1. The Curse of Dimensionality
2. Shared-Neighbor Distances
3. Subspace Outlier Detection
4. Subspace Clustering
5. Conclusions

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality

The “curse of dimensionality”: one buzzword for many
problemsbl[KKZ09]• First aspect: Optimization Problem (Bellman).
“[The]] curse off dimensionality
“[Th
di
i
lit […
[ is]i ] a malediction
l di ti thatth t hhas plaguedldthe scientists from earliest days.” [Bel61]– The difficultyy of anyy globalgoptimizationpapproachpp
increases
exponentially with an increasing number of variables (dimensions).
– General relation to clustering: fitting of functions (each function
explaining one cluster) becomes more difficult with more degrees of
freedom.
– Direct relation to subspace clustering: number of possible subspaces
increases dramatically with increasing number of dimensions.

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality• Second aspect: Concentration effect of Lp-norms– In [BGRS99,HAK00] it is reported that the ratio of (Dmaxd – Dmind) toDmind converges to zero with increasing dimensionality d• Dmind = distance to the nearest neighbor in d dimensions• Dmaxd = distance to the farthest neighbor in d dimensions
Formally:⎡⎤⎛ Dmax d − Dmin d ⎞,0 ⎟⎟ ≤ ε ⎥ = 1∀ε > 0 : lim d →∞ Ρ ⎢dist d ⎜⎜Dmin d⎝⎠⎣⎦• Distances to near and to far neighbors become more and moresimilar with increasing
g data dimensionalityy ((loss of relative
contrast or concentration effect of distances).
• This holds true for a wide range of data distributions and distancefunctions but
functions,but…
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality

From bottom to top: minimum observed value, average minus standard deviation, average value, average plus standard
deviation, maximum observed value, and maximum possible value of the Euclidean norm of a random vector. The
expectation grows, but the variance remains constant. A small subinterval of the domain of the norm is reached inpractice. (Figure and caption: [FWV07])– The observations stated in [BGRS99,HAK00, AHK01] are valid within clusters but not
between different clusters as long as the clusters are well separated[BFG99,FWV07,HKK+10].
– This is not the main problem for subspace clustering
clustering, although it should be kept inmind for range queries.
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality• Third aspect: Relevant and Irrelevant attributes

irrelevant attribute– A subset of the features may be relevant for clustering– Groups of similar (“dense”) points may be identified when considering
these features only

relevant attribute/
relevant subspace– Different subsets of attributes may be relevant for different clusters– Separation of clusters relates to relevant attributes (helpful to discern
between clusters) as opposed to irrelevant attributes(i di ti(indistinguishable
i h bl di
distribution
t ib ti off attributett ib t valueslffor diffdifferentt clusters).
l t )Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality– Effect on clustering:• Usually the distance functions used give equal weight to all
dimensions• However, not all dimensions are of equal importance• Adding irrelevant dimensions ruins any clustering based on a
distance function that equally weights all dimensions

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality• Fourth aspect: Correlation among attributes (redundancy?)– A subset of features may be correlated– Groups of similar (“dense”) points may be identified when considering
this correlation of features only

– different correlations of attributes may be
relevant for different clusters– can result in lower intrinsic dimensionality of a data set– bad discrimination of distances can still be a problem
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUPThe Curse of Dimensionality• there are other effects of the “curse of dimensionality”• just another strange fact: the volume of hyperspheres
shrinks with increasing dimensionality!
n
π 2rn
Vn (r ) =⎛n ⎞Γ⎜ + 1⎟⎝2 ⎠Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances[HKK+10]: Can Shared-Neighbor Distances Defeat the Curse
off Dimensionality?
Di
ilit ? (SSDBM 2010)• we mainly aim at distinguishing these effects of the ’curse’:– concentrationt ti effect
ff t within
ithi didistributions
t ib ti– impediment of similarity search by irrelevant attributes– partly: impact of redundant/correlated attributes• as a remedy for similarity assessment in high dimensionaldata,, to use shared nearest neighborg((SNN)) information has
been proposed but never evaluated systematically• [HKK+10]: evaluation of the effects on primary distances(Manhattan, Euclidean, fractional Lp (L0.6 and L0.8), cosine)and secondary distances (SNN)
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances• secondary distances are defined on top of primary distances• shared nearest neighbor (SNN) information:– assess the set of s nearest neighbors for two objects x and y in termsof some primary distance (Euclidean(Euclidean, Manhattan
Manhattan, cosine
cosine…))– derive overlap of neighbors (common objects in the NN of x and y)

SNNs (x, y) = NNs (x) ∩ NNs ( y)– similarity measure

SNN s ( x, y )simcos s ( x, y ) =scosine of the angle between membership vectors for NN(x) and NN(y)• SNN has been used before in mining high-dimensional data,
but alleged quality improvement has never been evaluatedZimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances• distance measures based on SNN:

dinv s ( x, y ) = 1 − simcos s ( x, y )dacos s ( x, y ) = arccos(simcos s ( x, y ))dln s ( x, y ) = − ln(simcos s ( x, y ))– dinv: linear inversion– dacos penalizes slightly suboptimal similarities more strongly– dln more tolerant for relatively
y highg similarity
y values but approachesppinfinity for very low similarity values• for assessment of ranking quality, these formulations areequivalent as the ranking is unaffected• only dacos is a metric (if the underlying primary distance is ametric)ti )Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances• Artificial data sets: n = 10.000 items, c = 100 clusters, up to d = 640didimensions,iclusterl t sizes
irandomlyd l ddetermined.
ti d• Relevant attribute values normally distributed, irrelevant attribute values
uniformly distributed.
distributed• Data sets:– All-Relevant: all dimensions relevant for all clusters– 10-Relevant: first 10 dimensions are relevant for all clusters, the remaining dimensions
are irrelevant– Cyc
Cyc-Relevant:Relevant: ith attribute is relevant for the jth cluster when i mod c = jj, otherwise
irrelevant (here: c = 10, n = 1000)– Half-Relevant: for each cluster, an attribute is chosen to be relevant with probability
0 5 and irrelevant otherwise
0.5,– All-Dependent: derived from All-Relevant introducing correlations among attributes
X∈AllDependent, Y∈AllRelevant: Xi = Yi (1 ≤ i ≤10), Xi = ½ (Xi-10+Yi) (i > 10)– 10-Dependent:
10 D
d t derived
d i d ffrom 10-Relevant
10 R lt introducing
i t d i correlations
l ti
among attributes
tt ib tZimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances

Data sets show properties of the “curse of dimensionality”

All
Relevant
All-Relevant⎛ Xd ⎞⎟ = 0 ⇒ Dmax − Dmin → 0
lim var⎜⎜
⎟
d →∞
[
]
E
X
Dmin
d
⎝
⎠
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances

Data sets show properties of the “curse of dimensionality”

10
Relevant
10-Relevant⎛ Xd ⎞⎟ = 0 ⇒ Dmax − Dmin → 0
lim var⎜⎜
⎟
d →∞
[
]
E
X
Dmin
d
⎝
⎠
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

Shared-Neighbor Distances

DATABASE
SYSTEMS
GROUP• Using each item in turn as a query, neighborhood ranking reported int
terms
off theth A
Area underd curve (AUC) off theth ReceiverRi
OperatingO
tiCharacteristic (ROC)
L2
Area under Curve1

true possitiveROC AUC

0.9

0.8

0.7

0.6

0.5
1

false positive

one query (neighbors same/different cluster)

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

0.8

0.6
0.4
0.2
Centrality
L2 160d
Arccos 160d
L1 160d

average over all items as a query0DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances

Euclidean distance

All-Relevant

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

10-Relevant

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances

SNN based on Euclidean

All-Relevant
20/40/80/160/320/640 dimensions

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances

SNN based on Euclidean

10-Relevant
20/40/80/160/320/640 dimensions

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor DistancesMultiple Features
M

M
Multiple
Features(pixel onlyy)

Optical Digits
D

A
ALOI

some real data sets: distributions of Euclidean distances

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor DistancesMultiple Features
M

M
Multiple
Features(pixel onlyy)

Optical Digits
D

A
ALOI

some real data sets: distributions of SNN distances (Euclidean)

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Shared-Neighbor Distances

some real data sets: ranking quality

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Outlier Detection[KKSZ09]: Outlier Detection in Axis-Parallel Subspaces of High
Dimensional Data (PAKDD 2009)
general idea:• assign a set of reference points to apoint o(e.g., kk-nearest
nearest neighbors – but keep
in mind the “curse of dimensionality”:
local feature relevance vs. meaningful
di tdistances))• find the subspace spanned by thesereference points (allowing some jitter)• analyze for the point o how well it fits
to this subspace
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Outlier Detection• distance of o to thereferencef
hyperplane:hldi t (o, H ( S ) ) =distd∑ v ⋅ (o − μ )
S
i

i

S 2
i

i =1

• the higher thisdistance, the moredeviates the point ofrom the behavior of
the reference set, themore likely it is an
outlier
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)oDATABASE
SYSTEMS
GROUP

Subspace Outlier Detection

subspace outlier degree(SOD) off a pointi t p:
dist (o, H (R( p ) ))SODR ( p ) ( p ) =v R( p)i.e., the distancenormalized
li d bby ththenumber of contributing
attributes
possible normalization to aprobability-value [0,1] inrelation to the distribution of
distancesds a ces oof aall popointss in S
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Outlier Detection

Choice of a reference set for outliers?
• recall “curse
curse of dimensionality
dimensionality”– local feature relevance Æ need for a local reference set– distances loose expressivenesspÆ how to choose a meaningful
g localreference set?

• consider k nearest neighbors in terms of the shared nearest
neighbor similarity– given a primary distance function dist (e.g. Euclidean distance)– Nk(p): k-nearest neighbors in terms of dist
– SNN similarity for two points p and q:

simSNN ( p, q ) = N k ( p ) ∩ N k (q )– reference set R(p): l-nearest neighbors of p using simSNN

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Outlier Detection

2-d sample data,comparison to• LOF [BKNS00]• ABOD [KSZ08]
SOD
LOF

ABOD

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Outlier Detection• Gaussian distribution in 3 dimensions, 20 outliers• adding
ddi 7
7, 17,
17 27,
27 47
47, 6767, 97 iirrelevantlt attributes
tt ib tZimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering[ABD+08]: Robust clustering in arbitrarily oriented subspaces(SDM 2008) (extended version: [ABD+08a])• Algorithm CASH: Clustering in Arbitrary Subspaces basedon the Hough-Transformg• Hough-transform:– developed in computer-graphics– 2-dimensional
2 di
i
l (i
(image procesing)i )• CASH:– generalization to dd-dimensional
dimensional spaces– transfer of the clustering to a new space (“Parameter-space” of theHough-transform)– restriction of the search space (from inn
innumerable
merable infinite to O(n!))– common search heuristic for Hough-transform: O(2d)→ efficient search heuristic
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering• given: D ⊆ ℜ d• findfi d lilinear subspacesbaccommodatingd ti many points
i t• Idea: map points from data space (picture space) ontofunctions in parameter space
δ

y

p1

δ

picture spacex

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

parameter spaceαDATABASE
SYSTEMS
GROUP

Subspace Clustering• ei, 1 ≤ i ≤ d: orthonormal-basis• x = (x( 1,…,xd)T: d-dimensionald diil vectort ontot hhypersphereharounddthe origin with radius r• ui: unit-vector
unit vector in direction of projection of x onto subspacespan(ei,…,ed)• α1,…,αd-1: αi angle between ui and ei
e3
x
u3

α3=0

u2

α2 u1
α1

e2

⎛ i −1⎞xi = r ⋅ ⎜⎜ ∏ sin (α j )⎟⎟ ⋅ cos(α i )⎝ j =1⎠e1

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clusteringrr
Lengthδ of the normal vector δ ⋅ n with n = 1 and angles
α1,…,αd-1
d 1 for the line through point p:⎛ i −1⎞f p (α1 , K , α d −1 ) = p, n = ∑ pi ⋅⎜⎜ ∏ sin (α j )⎟⎟ ⋅ cos(α i )i =1⎝ j =1⎠d

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering• Properties of the transformation– Point in the data space = sinusoidal curve in parameter space– Point in parameter space = hyper-plane in data space– Points on a common hyper-plane in data space = sinusoidal curves through acommon point in parameter space– Intersections of sinusoidal curves in parameter space = hyper-plane throughthe corresponding points in data space

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering• dense regions in parameter spacep⇔ linear structures in data space(hyperplanes with λ ≤ d-1)
• exact solution: find all intersection
points– infeasible– too exact• approximative solution: grid-based
clustering in parameter space→ find grid cells intersected by atleast m sinusoids– search space bounded but in O(rd)– ppure clusters requireqlarge
g value for r(grid solution)
Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering

efficient search heuristic for dense regions in parameter space••••construct a g
grid byy recursively
y splittingpg the pparameter spacep((best-firstsearch)
identify dense grid cells as intersected by many parametrization functions
d
dense
grid
id cellll representst (d(d-1)-dimensional1) diil lilinear structuret ttransform corresponding data objects in corresponding (d-1)-dimensional
space
and repeat
the search recursivelyypp

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering• grid cell representing less than m points can be excluded→ early pruning of a search path• grid cell intersected by at least m sinusoids after s recursive
splits represents a correlation cluster (with λ ≤ dd-1)
1)– remove points of the cluster (and corr. sinusoids) from remaining cells

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering• search heuristic: linear in number of points, but ~ O(d3)depth of search s,s number c of pursued paths (ideally: c cluster):– priority search: O(s⋅c)– determination of curves intersecting
g a cell: O(n( ⋅d3)– overall: O(s⋅c⋅n⋅d3)(note: PCA generally in O(d3))

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering(a) Data set(b) CASH: Cluster 1-5(c) 4C: Cluster 1-8(d) ORCLUS: Cluster 1-5

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Subspace Clustering• stability with increasing number of noise objects

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Conclusions• The curse of dimensionality does not count in general as an
excuse for everything – depends on the number and natureof distributions in a data set• the nature of each particular problem needs to be studied in
its own• part of the curse: it’s always different than expected• if you ever think,
hi k you hhave solved
l d theh problems
bloff theh curse:watch out for the curse striking back!

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Some Advice• do not take everything for granted which is stated in theliterature• consider claims in the literature:– is there enoughg evidence to support
pp the claims?
– is the interpretation of the claims clear?
– challenge them or support them

• papers report the strengths – youo shoshouldld tr
try to find ooutt theweaknesses and to improve• have fun!

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Literature[ABD+08] E. Achtert, C. Böhm, J. David, P. Kröger, and A. Zimek.
Robust clustering in arbitrarily oriented subspaces.
In Proceedings of the 8th SIAM International Conference on Data Mining (SDM),
Atlanta, GA, 2008
[ABD+08a] E. Achtert, C. Böhm, J. David, P. Kröger, A. Zimek:
Gl b l C
GlobalCorrelationl ti Cl
Clustering
t i B
Based
d on th
the H
Hough
hT
TransformfStatistical Analysis and Data Mining, 1(3): 111-127, 2008.
[ABK+06] E. Achtert, C. Böhm, H.-P. Kriegel, P. Kröger, and A. Zimek.
Deriving quantitative models for correlation clusters
clusters.
In Proceedings of the 12th ACM International Conference on Knowledge Discovery
and Data Mining (SIGKDD), Philadelphia, PA, 2006.
[[ABK+07c]] E. Achtert,, C. Böhm,, H.-P. Kriegel,g , P. Kröger,g , and A. Zimek.
Robust, complete, and efficient correlation clustering.
In Proceedings of the 7th SIAM International Conference on Data Mining (SDM),
Minneapolis, MN, 2007.
[AHK01] C.
C C
C. A
Aggarwal,l A
A. Hi
Hinneburg,
b
and
dD
D. K
Keim.
i
On the surprising behavior of distance metrics in high dimensional space.
In Proceedings of the 8th International Conference on Database Theory (ICDT),
London, U.K., 2001.

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Literature[Bel61]

R. Bellman.
AdaptivepControl Processes. A Guided Tour. Princeton Universityy Press, 1961.
[BFG99] K. P. Bennett, U. Fayyad, and D. Geiger.
Density-based indexing for approximate nearest-neighbor queries.
In Proceedings
g of the 5th ACM International Conference on Knowledge
g Discoveryyand Data Mining (SIGKDD), San Diego, CA, 1999.
[BGRS99] K. Beyer, J. Goldstein, R. Ramakrishnan, and U. Shaft.
When is “nearest neighbor” meaningful?
In Proceedings of the 7th International Conference on Database Theory (ICDT),
Jerusalem, Israel, 1999.
[BKNS00] M. M. Breunig, H.-P. Kriegel, R.T. Ng, J. Sander.
LOF: Identifying Density-based
Density based Local Outliers.
Outliers
In Proceedings of the ACM International Conference on Management of Data
(SIGMOD), Dallas, TX, 2000.
[[FWV07]
0 ] D. Francois,a co s, V. Wertz,
e ,aandd M. Verleysen.
e eyse
The concentration of fractional distances.
IEEE Transactions on Knowledge and Data Engineering, 19(7): 873-886, 2007.

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMS
GROUP

Literature[HAK00]A. Hinneburg, C. C. Aggarwal, and D. A. Keim.
What is the nearest neighborgin highg dimensional spaces?
p
In Proceedings of the 26th International Conference on Very Large Data Bases(VLDB), Cairo, Egypt, 2000.
[HKK+10] M. Houle, H.-P. Kriegel, P. Kröger, E. Schubert, and A. Zimek.
Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?
In Proceedings of the 22nd International Conference on Scientific and Statistical
Data Management (SSDBM), Heidelberg, Germany, 2010.
[KKSZ09] H.-P. Kriegel, P. Kröger, E. Schubert, A. Zimek:
Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data.
In Proc. 13th Pacific-Asia Conference on Knowledge Discovery and Data Mining(PAKDD) Bangkok(PAKDD),
Bangkok, Thailand
Thailand, 2009
2009.

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)

DATABASE
SYSTEMSGROUP[KKZ09][KSZ08]

Literature
H.-P. Kriegel, P. Kröger, and A. Zimek.
Clustering High Dimensional Data: A Survey on Subspace Clustering, Patternbased Clustering, and Correlation Clustering.
ACM Transactions on Knowledge Discovery from Data (TKDD), Volume 3, Issue 1(March 2009), Article No. 1, pp. 1-58, 2009.
H P Kriegel
H.-P.
Kriegel, M.
M Schubert,
Schubert A
A. Zimek
Zimek.
Angle-Based Outlier Detection in High-dimensional Data.
In Proceedings of the 14th ACM International Conference on Knowledge Discovery
and Data Mining (SIGKDD), Las Vegas, NV, 2008.

Zimek: Data Mining and the 'Curse of Dimensionality’ (iDB Workshop 2011)