ISSN 2186-7437

NII Shonan Meeting Report

No. 2013-4

Dimensionality and Scalability
Michael E. Houle
Vincent Oria
Arthur Zimek
May 20–23, 2013

National Institute of Informatics
2-1-2 Hitotsubashi, Chiyoda-Ku, Tokyo, Japan

Dimensionality and Scalability
Organizers:
Michael E. Houle (National Institute of Informatics, Japan)
Vincent Oria (New Jersey Institute of Technology, USA)
Arthur Zimek (Ludwig-Maximilians-Universität München, Germany)
May 20–23, 2013

Description of the Meeting
Background
For many fundamental operations in the areas of search and retrieval, data
mining, machine learning, multimedia, recommendation systems, and bioinformatics, the eﬃciency and eﬀectiveness of implementations depends crucially on
the interplay between measures of data similarity and the features by whichdata objects are represented.
When the number of features (the data dimensionality) is high, similarity
values tend to concentrate strongly about their means, a phenomenon commonlyreferred to as the curse of dimensionality. As the dimensionality increases,
the discriminative ability of similarity measures diminishes to the point where
methods that depend on them lose their eﬀectiveness.
One fundamental task, arising in applications of multimedia, data mining
and machine learning, and other disciplines, is that of content-based similarity
search. For such applications, features are often sought so as to provide the best
possible coverage across a range of anticipated queries. However, for any given
query, only a relatively small number of features may turn out to be relevant.
When the dimensionality is high, the errors introduced into similarity measurements by the many irrelevant feature attributes can completely overwhelm thecontributions of the relevant features.
The way in which the curse of dimensionality manifests itself varies fromdiscipline to discipline. For example:• In multimedia applications, direct representations of images and video
frames typically involve hundreds or thousands of features. The visual vocabularies currently being sought for large image corpuses or video archives
can have millions of visual words. These huge feature set sizes can lead tosevere problems for clustering, classiﬁcation, and any other applications
that require content-based similarity search.
• Data mining and analysis applications often require the identiﬁcation ofrelatively small clusters of mutually-similary data objects (nuggets). Identiﬁcation of nuggets usually entails the generation of lists of objects similar1

to query objects, to serve as candidates for cluster membership. Traditional clustering methods may be inadequate in identifying nuggets; evensubspace clustering methods that speciﬁcally target groupings based on
subsets of the feature set may be defeated by the sheer number of possible
feature combinations.
To support operations in such areas, feature selection and other dimensional
reduction techniques from machine learning are often considered in an attempt
to improve the discriminability of similarity measures, and the scalability ofmethods that depend upon them. Yet even here, the complexity of searching
through combinations of features can be prohibitive.

Dimensionality and Data Modeling
Many researchers and practitioners from diﬀerent areas who are speciﬁcallyworking on problems involving the selection of features tend to be aware of thediﬃculties involved with high-dimensional data settings. Researchers in otherareas are generally aware that the performance of their solutions depends onthe dimensionality of their data sets, but are often not clear as to why.
In general, researchers tend to evaluate the inherent diﬃculty of tasks interms of characteristics of the data set, such as the number of records, thenumber of feature dimensions, or the size of the data in bytes. However, theusual characterizations are not always indicative of the true diﬃculty involved in
the processing of tasks for that set. For any given task performed on two diﬀerent
sets with the same numbers of records, features, and bytes, the performances
could vary tremendously. On the other hand, data sets that are diﬃcult toprocess for tasks in one domain tend to be diﬃcult to process for other tasks inother domains.
Over the past decade or so, new characterizations of data sets have been
proposed so as to assess the performance of particular methods. Such characterizations include estimations of distribution, estimation of local subspacedimension, and measures of intrinsic dimensionality of data. Although the applications aﬀected by the curse of dimensionality vary widely across researchdisciplines, the characterizations and models of data that can be applied to analyze the performance of solutions are very general. Researchers from diﬀerent
disciplines, even though they work with diﬀerent types of data for very diﬀerent
purposes, can nevertheless make use of a common set of data models and datacharacterizations. With a common framework in place for the assessment of thecomplexity of data sets, general techniques developed within one discipline forcommon subtasks such as search, clustering, classiﬁcation, matching, and feature selection could conceivably be assessed for their applicability to tasks fromother disciplines. Unfortunately, across the various disciplines, most such characterizations are as yet either unknown or underused, and techniques developed
within one discipline for coping with the curse of dimensionality are constantly
being reinvented by researchers in other disciplines.

Objectives
The goal of this meeting was to bring together researchers and students activein the areas of databases, data mining, pattern recognition, machine learning,2

statistics, multimedia, bioinformatics, visualization, and algorithmics who are
currently searching for eﬀective and scalable solutions to problems aﬀected by
the curse of dimensionality. In particular, the objectives were:• To survey the existing approaches used in dealing with the curse of dimensionality in these various disciplines, identifying their commonalities,
strengths and limitations.
• To identify promising general data characterizations useful for the design
and analysis of important subtasks common to these disciplines that arestrongly aﬀected by the curse of dimensionality, including (but not limitedto) search, classiﬁcation, clustering, and feature selection.
• To promote the adoption of theoretical analysis by researchers within thesevarious disciplines.
Participants were not expected to give presentations of fully completed research.
Instead, emphasis was placed on group input into the development of data characterizations, and the identiﬁcation of future directions for research on dimensionality and scalability.

Participants
Laurent Amsaleg, IRISA-CNRS, France
Ira Assent, Aarhus University, Denmark
Ricardo J. G. B. Campello, University of Sao Paulo, Brazil
Peter D. Eades, University of Sydney, Australia
Vladimir Estivill-Castro, Griﬃth University, Australia
Björn Þór Jónsson, Reykjavik University, Iceland
Peer Kröger, Ludwig-Maximilians-Universität München, Germany
Michael Nett, NII, Tokyo, Japan
Chong-Wah Ngo, City University of Hong Kong, China
Miloš Radovanović, University of Novi Sad, Serbia
Jörg Sander, University of Alberta, Edmonton, Canada
Shin’ichi Satoh, NII, Tokyo, Japan
Koji Tsuda, AIST, Tokyo, Japan
Takeaki Uno, NII, Tokyo, Japan
Takashi Washio, ISIR, Osaka University, Japan
Pavel Zezula, Masaryk University, Brno, Czech Republic

3Overview of Talks
The ﬁrst part of the meeting comprised survey talks to illuminate the topic of“Dimensionality and Scalability” from diﬀerent perspectives.

Scalability of Similarity Searching
Pavel Zezula, Masaryk University, Brno, Czech Republic
Similarity searching has been a research issue for many years, and searching has probably become the most important web application today. As thecomplexity of data objects grows, it is more and more diﬃcult to reason about
digital objects otherwise than through the similarity. In the presentation, we
ﬁrst discuss on concepts of similarity and searching in light of the contemporary
Big Data problem before introducing a short survey of similarity search history.
We analyze the bottlenecks of application development and discuss perspectivesof search computing for future applications. Speciﬁcally, the directions towards
similarity search cloud services and self-organizing search systems are outlined.

Obstacles and Some Remedies in High Dimensional Particle
FilteringTakashi Washio, ISIR, Osaka University, Japan
This review presentation focused on the impact on the curse of dimensionality to Monte Carlo based Bayesian estimation and learning, particularly, Particle
Filtering (PF). This problem contains common issues over various Monte Carloand Bayesian estimation problems.
First, concentration of measure on high-dimensional structures was discussed
as one of the major eﬀect of the curse of dimensionality. Some intuitive explanation of this eﬀect and its mathematical analysis were provided.
Second, basic principles and some techniques of the particle ﬁltering were
outlined, and an important technical issue named degeneration of the particle
weights is introduced. Furthermore, the impact of the concentration of measure on high-dimensional structures to the Bayesian estimation in the particle
ﬁltering was explained together its mathematical analysis. The review showed
two main obstacles to the high dimensional particle ﬁltering; (1) the statisticalinstability by the severe degeneration of the particle weights and (2) the large
estimation bias by the concentration of measure.
Third, the review explained three remedies to the obstacles; (A) Rao-Blackwellised particle ﬁltering techniques, (B) use of Markov Chain Monte Carlo(MCMC) for generating a posteriori distribution and (C) use of optimization
with proposal distribution. (A) relaxes the obstacles (1) and (2) by reducing
variables in PF computation, however its applicability is very limited to somespecial cases. (B) relaxes the obstacle (1) by not using particle weighting but
Metropolis Hastings algorithm, however much computation is needed to obtainits suﬃcient eﬀect. (C) relaxes the obstacles (2) by searching the maximum aposteriori probability, but no systematic framework has not been establish yet.
Finally, the review pointed out the needs of much more studies in this ﬁeld
to address many aforementioned issues.
4Subspace clustering
Ira Assent, Aarhus University, Denmark
Clustering is an established data mining technique for automatically grouping objects based on mutual similarity. As we face increasingly high-dimensionaldata, eﬀects attributed to the “curse of dimensionality” mean that in highdimensional spaces, traditional clustering methods fail to identify meaningfulclusters.
In this talk, I provide an overview over some of the approaches that have been
proposed in the data mining community. Dimensionality reduction techniques
aim at identifying a projection of the data in which most information is retained,
while noisy attributes are removed. As this necessarily requires a global view on
the relevance of attributes for all objects in the data set, subspace and projectedclustering methods have been suggested as an alternative. In a nutshell, the idea
is to identify the clusters along with their (locally) relevant subset of dimensions.
Diﬀerent approaches to identifying clusters in subspaces have been proposed.
Subspace search is a two-phase process, where the ﬁrst phase identiﬁes promising
subspaces based on some interestingness criterion, and the second phase thensubjects these interesting subspaces to traditional clustering algorithms. Subspace or projected clustering methods aim at identifying subspaces and clusters
at the same time. Bottom-up algorithms work in an apriori-style manner, using
low dimensional results to build candidates on higher dimensional dimensions inthe subspace lattice. This may lead to impractical runtimes for large and very
high-dimensional data sets, so grid-based methods partition the space either
using a ﬁxed layout or data-based hyperplanes. Alternatively, some subspaceclustering algorithms avoid bottom-up search and instead search in a best-ﬁrst
manner, which may be supported by specialized data structures. To scale evenmore, approximate algorithms combine interesting regions in low dimensional
spaces to region candidates where the number of attributes is much higher,
allowing to skip many relatively low dimensional subspaces in-between.
Finally, I will give some examples of application areas such as time series ordocument mining, where high-dimensionality also is an issue, but where special
properties of the data may allow more speciﬁc solutions to the problem.

Outlier Detection in High-Dimensional Data
Arthur Zimek, Ludwig-Maximilians-Universität München, Germany
High dimensional data in Euclidean space pose special challenges to data
mining algorithms. These challenges are often indiscriminately subsumed under
the term “curse of dimensionality”, more concrete aspects being the so-called“distance concentration eﬀect”, the presence of irrelevant attributes concealing
relevant information, or simply eﬃciency issues.
Albeit the infamous “curse of dimensionality” has been credited for many
problems and has indiscriminately been used as a motivation for many new
approaches, we should try to understand the problems occurring in high dimensional data in more detail. For example, there is a widespread mistaken belief
that every point in high dimensional space is an outlier. This – misleading,to say the least – statement has been suggested as a motivation for the ﬁrst

5

approach specialized to outlier detection in subspaces of high dimensional data,
recurring superﬁcially to a fundamental paper on the “curse of dimensionality”.
We will show in this talk that it is not as simple as that. We go into detail ofsome eﬀects of the “curse of dimensionality” and discern truths and widespread
misconceptions regarding high dimensional data with respect to outlier detection. Important aspects are
1. the concentration of distances
2. the eﬀect of diﬀerent proportions of irrelevant attributes
3. numerical discrimination of outlier scores vs. ranking of outlier scores
4. combinatorial issues (data snooping)
5. hubness
We discuss these eﬀects and their consequences for outlier detection.

Scalability Problems in Bioinformatics
Koji Tsuda, National Institute of Advanced Industrial Science and Technology(AIST), Tokyo, Japan
In the last 10-15 years there has been a great increase of interest in spaceeﬃcient (succinct) data structures that are compressed up to the information
theoretic lower bound. Compared to pointer-based naive data structures, thememory usage can be smaller up to 20-30 fold. I brieﬂy present basics of succinct
data structures and our recent work of indexing 25 million chemical graphs for
similarity search in memory. In addition, fast all pairs similarity search methods
called SketchSort and SlideSort are discussed.

Information Visualization
Peter D. Eades, University of Sydney, Australia
This is an introduction to Information Visualization. The talk begins withthe purposes of visualization. Then a general model for the visualization process is described, as well as some example methods. We describe methods forevaluation of visualizations, and ﬁnish with a list of challenges for the future.

Scalability in Multimedia Search and Mining
Chong-Wah Ngo, City University of Hong Kong, China
In large-scale multimedia search, there are a large number of features in highdimensional space to be dealt with. Even an image can contain hundreds of local
feature points. For a million-scale multimedia dataset, the visual search can run
forever if without a proper indexing scheme to organize the features. This talkpresents the indexing structures that have been successfully applied and adapted
for this problem, and discusses issues such as feature dimensionality, memory
consumption and query processing time. While searching against a million-scale
6

dataset is feasible, mining visual objects is an extremely diﬃcult task due to thescalability problem. This talk presents some techniques addressing this problem,
discussing reasons that there is yet to have an eﬀective and eﬃcient algorithm
for multimedia mining.

Dimensionality and Scalability Issues in Multimedia
Shin’ichi Satoh, NII, Tokyo, Japan
Dimensionality and scalability issues in multimedia are discussed. Special
emphasis was laid on image among other multimedia data, and also image searchand image semantic classiﬁcation were investigated as typical tasks. Globalfeature and local feature, aggregation strategies of local feature such as bagof visual word were discussed. Most cases features are high dimensional andsparse. Especially in image classiﬁcation task, the number of possible classes
introduces another direction of scalability issues.

How to Refine Pattern Mining
Takeaki Uno, NII, Tokyo, Japan
Pattern mining is one of the fundamentals in data mining. The aim of thepattern mining is, usually, to ﬁnd all patterns of a speciﬁed class, in the given
database. The problem has a long history of up to 20 years, and has been intensively studied. There have been proposed many problems and algorithms.
However, pattern mining algorithms are no so much used in real-world applications. One of the reasons is that the number of solutions is usually huge, andmany similar patterns appearing in similar places are found. Constraints given
by background knowledge are often used to reduce the number, but this does
not have any mechanism of automatically avoiding huge number of solutions.
In this talk, we introduce a new concept of data properlization. Data properlization adds the lost edges and deletes unnecessary edges from the data so thatthe data will have much more clarity, that is, objective structures will have noambiguity. For example, data properlization changes pseudo clique corresponding to a cluster to a clique. By applying the data properlization, the numberof cliques will be drastically reduced, and thus we can eﬃciently ﬁnd all local
structures without implicit duplications. This approach would be the ﬁrst resultin data mining that has a mechanism of reducing the number of solutions, withsimple and eﬃcient computation.

Intrinsic Dimensionality and Discriminability of Data
Michael E. Houle, NII, Tokyo, JapanFor many large-scale applications in data mining, machine learning, andmultimedia, fundamental operations such as similarity search, retrieval, classiﬁcation, clustering, and anomaly detection generally suﬀer from an eﬀect known
as the ‘curse of dimensionality’. As the dimensionality of the data increases, distance values tend to become less discriminative, due to their increasing relative
concentration about the mean of their distribution. For this reason, researchers
7have considered the analysis of structures and methods in terms of measuresof the intrinsic dimensionality of the datasets. This presentation introduces ageneralization of a discrete measure of intrinsic dimensionality, the expansion
dimension, to the case of continuous distance distributions. This notion of intrinsic dimensionality of a distribution can be shown to precisely coincide with anatural notion of the indiscriminability of distances and features. Furthermore,
for any distance distribution with diﬀerentiable cumulative density function,a fundamental relationship exists between probability density, the cumulative
density (cumulative probability divided by distance), intrinsic dimensionality,and discriminability.

Summary of Discussions
During the second part of the workshop, the participants discussed some topics
in diﬀerent groups.

Intrinsic Dimensionality w.r.t. (Subspace-)Clustering andOutlier Detection
A group including Ira, Arthur, Jörg, Björn Þór, Ricardo, Peer, Miloš, Michael
Houle, and Laurent focused on thinking about what the continuous form of
the Intrinsic Dimensionality (ID) could bring for helping to address sub-spaceclustering and/or outlier detection.
The general understanding is that ID can be estimated/measured from a
local point of view, that is by analyzing the vicinity of a speciﬁc point in space.
Then, the knowledge acquired from many points can be aggregated one way or
the other in order to return a more global information of the ID of the entire
dataset.
The ID around a point can be measured, increasing the radius used for the
analysis. This, in turn, gives a curve. A similar operation can be done to plota Φ-curve instead of an ID-curve. One direction to follow in order to get abetter understanding of the entire process is to plot several such curves using
real datasets (such as the ALOI dataset) as well as synthetic ones. Note that
determining good ways for generating such datasets is not fully clear; yet, simple
datasets such as the ones mentioned by Arthur during his talk as well as the
typical datasets addressing classical clustering problems might be used. This
well controlled environment might help discovering what is at stake with Φ- andID-curves.
Several interesting point conﬁgurations were discussed, as they might highlight speciﬁc properties of the ID stories. Three such conﬁgurations have been
discussed: assuming there is a cluster in space, how curves from two close points
within the cluster relate, from two points in the same cluster but far apart, andone point inside the cluster and another outside. As curves rely on a metric,
it might be worth studying the impact of using regular distances, ranks, thenumber of shared neighbors. Plotting curves might give insights, as well as
aggregating them into some kind of surface, possibly showing new properties(local min, max, . . . ).
While computing Φ- and ID-curves encompasses all the dimensions, it ispossible that few features only might deﬁne a subspace that is hard to capture8

from the global point of view of the ID deﬁnition. No solution to this is foreseen,
except to try to build on this in order to validate which features to pick to reachthe observed ID — but this idea remains controversial and unclear. Furthermore
this might only identify axis-parallel subspaces. A PCA based mechanism might
be needed to cope with non aligned subspaces.
Another direction is to investigate what happens when we use these new
notions in existing works such as DBSCAN, or density-based clustering andoutlier detection in general. Of course, that study should include analyzing
what happens in low-dimensional (possibly little or no impact for ID) vs. highdimensional data (possibly higher impact).
Note that some current work using a concentration measure might havestrong relationships with estimating the ID.
Note also that checking the behavior of the ID when getting close to theborders of the space is probably required. This is indeed a concern as thismight alter the number we observe w.r.t. the numbers we expect to observe, asa part of space by deﬁnition can not contain any point while radii are oblivious
to this.

Computation & Estimation of Intrinsic Dimensonality
A group including Takeaki Uno, Koji Tsuda, Takashi Washio, Peter Eades, andMichael Nett discussed some implications from a machine learning persepctive.
Support vector machines using radial base function kernels perform wellfor many practical tasks. The underlying kernel distance is parameterized in
the kernel width parameter. Usually, this parameter is chosen by supervised
preprocessing methods like cross-fold validation. However, a property that determines particularly well-performing parameter choices is yet to be discovered.
Nevertheless, we suspect that such a property may be related to the notion of
discriminability (and equivalently intrinsic dimensionality). Unfortunately, as
it is not well understood in the community what properties of the kernel distance distribution are important, we are likely forced to discover or learn suchproperties empirically through extensive experimentation.
As a second topic, we discussed how the decomposability of the distance
distribution within the model of intrinsic dimensionality proposed by Michael
Houle may be marginalized. While it is not at all clear how to interpret themarginalized contribution of probability measure of individual points in space, it
indicates that this issue is linked to the question of how intrinsic dimensionalityand distance distributions between diﬀerent points are related.

Intrinsic Dimensionality and Graphs
A group including Vlad, Koji, Takashi, and Peter formulated research questions
related to graphs:
Such questions are:• What is the relationship between ID and the “expansion” of a graph?
• What is the ID of a social network (or a scale-free network)• How does ID vary with changing distance metrics?

9

An idea was to produce some stories in low dimensions with small data toillustrate ID.
A conjecture: “A graph with low ID has a good drawing.”

Intrinsic Dimensionality and Empirical Results
A group including Peter, Vlad, Koji, and Björn Þór discussed questions regarding the relationship between theory and empirical results.
We need an underlying theory to explain our empiricial results. Such atheory might be developed around the concept of intrinsic dimensionality. For
example, something should explain the trade-oﬀ between increasing dimension
and paying penalty in search computational resources
A second issue is the need for better benchmark data sets for research into
the applications where large scale is required. Papers which describe methods
aimed at large data but only tested on small data are not valuable. Ideas
to encourage the development and curation of benchmark data sets could be
to have a special issue of a journal on benchmark data sets. More generally,
publication of methodology should be encouraged. Other possibilities might becompetitions and particular workshops. Questions are if it might be possible toraise funding for data curation? To publish benchmark data might also involve
copyright issues and privacy issues.

Dimensionality and Multimedia
The discussion group on dimensionality and multimedia included Chong-Wah
Ngo, Vincent Oria, Shin’ichi Satoh and Pavel Zezula. Michael Nett joined thegroup on the last day.
The complexity of next-generation retrieval systems originates from the requirement to organise massive and ever growing volumes of heterogeneous data
and meta-data, together with the need to co-ordinate scalable management ofsimilarity matching. The problem starts with data acquisition of weakly structured or completely unstructured data, such as images and video, which necessarily need innovative techniques for information extraction and classiﬁcation
to increase their ﬁndability. Raw multimedia data cannot be directly used when
performing tasks such as search and classiﬁcation due to the amount of data
involved, and the lack of interpretability. The content of multimedia data isoften represented as high dimensional vectors called descriptors that depend on
the media type and the application. For images, there are mainly two types ofdescriptors: global descriptors such as color histograms, and local descriptors
such as SIFT. Local features are often aggregated to form visual words witheach image represented by a bag of visual words (BoVW). With the BoVW approach, an image is represented by a sparse vector in a high-dimensional space(which can be in excess of one million dimensions). Dimensionality and scalability issues in image databases arise due to the number of dimensions used
to represent the visual features, the number of local features per image, thenumber of visual words, the number of queries and the number of users.
In principle, we consider search and object ﬁndability as two principal andsynergistic aspects of information access. They both represent the eﬀectivenessand eﬃciency challenges which need innovative theories and technologies, andmust be studied together to allow the development of qualitatively new retrieval
10tools in the future. The objective is foundational in nature in that it addresses
the theoretical limits of similarity retrieval in the context of the Big Data problem — a development of scalable solutions with low intrinsic dimensionality isessential. The research issues related to dimensionality and scalability that wehave identiﬁed are:• Local eﬀective feature selection: the multimedia ﬁeld is currently dealing
with some of the most diﬃcult datasets. Face data is a typical example
where current similarity functions cannot discriminate among data points.
One reason for the lack of discriminability is that some of the dimensions
used for representing the features can be useless in the locality of thequery. A research direction that we are proposing to investigate is tolocally identify and select the most eﬀective features to represent the data.
The research tasks involved are:
– Data representation (how to represent the database with only selected local eﬀective features and what type of similarity function
will support the data representation).
– Adaptive search (adapt the search to each query point since the data
representation will depends on the query point neighborhood).
– Indexing (which index structure and algorithms will properly support
adaptive search and local eﬀective features).
– Machine learning (How to learn only local eﬀective features using amachine learning approach).
• Annotation and scalability: it has become feasible to learn large number ofconcept classiﬁers, with a large number of labeled images (e.g. ImageNet)
and weakly labeled data freely available. The issue of scalability becomes aconcern when considering (1) how to eﬀectively learn a new classiﬁer, and(2) how to eﬃciently annotate a sample against a large pool of classiﬁers.
For (1), an interesting topic is the leveraging of the available classiﬁers
for learning a new classiﬁer that can scale in terms of learning speed andclassiﬁcation robustness. For (2), organizing the classiﬁers hierarchically
can naturally speed up the annotation, but also result in performance dropcompared to testing against all classiﬁers. Therefore, there is a tradeoﬀ
between annotation accuracy and eﬃciency. An interesting topic is to
identify the trade-oﬀ, taking into account the organization of classiﬁers
and the reliability of classiﬁers.
• Dimensionality and similarity function: how does dimensionality aﬀect
diﬀerent similarity functions, and how to design similarity functions thatcan cope with high dimensionality?
• Training and dimensionality: is training really needed in the visual word
creation? Training in high dimensional spaces may cause overﬁtting, andsubsequently a cross-domain problem. In this case, randomly selected
local features to be used as codebook can yield better results.

11