Future Trends
in Similarity Searching
Pavel Zezula
Masaryk University
Brno, Czech Republic
Outline of the talk
• Introduction
• Many faces of similarity
• Real life and digital similarity
• On the importance of searching
• Current technology and its limitations
• Similarity search computing services
• SISAP after 5 years
August 9-10 2SISAP 2012, Toronto, Canada
Introduction
• Honor and responsibility of Keynote talks
• Technical talk versus a conceptual one
• SISAP is a narrow community – I am a part of it
• Most of my technical knowledge is summarize in
the Similarity Search book
• My objectives: current experience, where to go,
how to proceed
• Presented observations reflect my personal
experience with: similarity, search, applications
August 9-10 3SISAP 2012, Toronto, Canada
SISAP 2012, Toronto, Canada 4
Metric Searching technology
Hanan Samet
Foundation of Multidimensional and
Metric Data Structures
Morgan Kaufmann, 2006
P. Zezula, G. Amato, V. Dohnal, and M. Batko
Similarity Search: The Metric Space Approach
Springer, 2006
August 9-10
Real-life Similarity
• Are they similar?
August 9-10 5SISAP 2012, Toronto, Canada
Real-life Similarity
• Are they similar?
August 9-10 6SISAP 2012, Toronto, Canada
Real-life Similarity
• Are they similar?
August 9-10 7SISAP 2012, Toronto, Canada
Real-life Similarity
• Are they similar?
August 9-10 8SISAP 2012, Toronto, Canada
Real-Life Motivation
The social psychology view
• Any event in the history of organism is, in a sense,
unique.
• Recognition, learning, and judgment presuppose
an ability to categorize stimuli and classify
situations by similarity.
• Similarity (proximity, resemblance, communality,
representativeness, psychological distance, etc.) is
fundamental to theories of perception, learning,
judgment, etc.
August 9-10 9SISAP 2012, Toronto, Canada
Contemporary Networked Media
The digital data view
• Almost everything that we see, read, hear, write,
measure, or observe can be digital.
• Users autonomously contribute to production of global
media and the growth is exponential.
• Sites like Flickr, YouTube, Facebook host user
contributed content for a variety of events.
• The elements of networked media are related by
numerous multi-facet links of similarity.
August 9-10 10SISAP 2012, Toronto, Canada
Challenge
• Networked media is getting close to the human “fact-
bases
– the gap between physical and digital has blurred
• Similarity data management is needed to connect,
search, filter, merge, relate, rank, cluster, classify,
identify, or categorize objects across various
collections.
WHY?
It is the similarity which is in the world revealing.
August 9-10 11SISAP 2012, Toronto, Canada
Similarity & Geometry
• Figures that have the same shape but not
necessarily the same size are similar figures:
• Any two line segments are similar:
• Any two circles are similar:
A B C D
August 9-10 12SISAP 2012, Toronto, Canada
Similarity & Geometry
• Any two squares are similar:
• Any two equilateral triangles are similar:
August 9-10 13SISAP 2012, Toronto, Canada
Similarity & Geometry
• Definition:
• Two polygons are similar to each other, if:
1. Their corresponding angles are equal
2. The lengths of their corresponding sides are
proportional
August 9-10 14SISAP 2012, Toronto, Canada
Similarity & Geometry
• Example:
• <A = <E; <B = <F; <C = <G; <D = <H, and also
• AB/EF=BC/FG=CD/GH=DA/HE
B
C
A
D
E F
H G
August 9-10 15SISAP 2012, Toronto, Canada
Similarity & Geometry
• If one polygon is similar to a second polygon,
and the second polygon is similar to the third
polygon, the first polygon is similar to the
third polygon.
• In any case:
Two geometric figures are either similar or they
are not similar at all
August 9-10 16SISAP 2012, Toronto, Canada
Visual Similarity
• MPEG-7 multimedia content desc. standard
• Global feature descriptors:
– Color, shape, texture, …
– One high-dimensional vector per image
August 9-10 SISAP 2012, Toronto, Canada 17
Multiple Visual Aspects
August 9-10 SISAP 2012, Toronto, Canada 18
SISAP 2012, Toronto, Canada 19
Visual Similarity
- Local feature descriptors – SIFT, SURF, etc.
- Invariant to image scaling, small viewpoint change, rotation, noise, illumination
August 9-10
SISAP 2012, Toronto, Canada 20
Visual Similarity -finding coresspondence
August 9-10
Biometric Similarity
• Biometrics:
– methods of recognizing a person based on
physiological and behavioral characteristics
• Two types of recognition problems:
– Verification – authenticity of a person
– Identification – recognition of a person
• Examples:
– Finger prints, face, iris, retina, speech, gait, etc.
August 9-10 SISAP 2012, Toronto, Canada 21
Biometrics: Fingerprint
• Minutiae detection:
– Detect ridges (endings and branching)
– Represented as a sequence of minutiae
• P=( (r1,e1,θ1), …, (rm,em,θm) )
• Point in polar coordinates (r,e) and direction θ
• Matching of two sequences:
– Align input sequence with database one
– Compute weighted edit distance
• wins,del=620
• wrepl=[0;26] - depending on similarity of two minutiae
August 9-10 SISAP 2012, Toronto, Canada 22
Biometrics: Hand Recognition
• Hand image analysis
– Contour extraction, global registration
• Rotation, translation, normalization
– Finger registration
– Contour represented as a set of pixels
F={f1,…,fNF
}
• Matching: modified Hausdorff distance
August 9-10 SISAP 2012, Toronto, Canada 23
      FGhGFhGFH ,,,max, 
       

Gg FfGFf GgF
gf
N
FGhgf
N
GFh min
1
,min
1
,
Remote Biometrics: Approaches
• Detection, normalization, extraction, recognition
• Face recognition
– Methods:
• Appearance-based – analyze the face as a whole
• Model-based – compare individual features (e.g., eyes, mouth)
• Gait recognition
– Less likely to be obscured, low resolution suffices
– Methods are based on shape or dynamics of the person:
• Appearance-based – analyze person’s silhouettes
• Model-based – compare features (e.g., trajectory, angular velocity)
23.1.2012 24MUFIN: Multi Feature Indexing Network
Face similarity
• Face detection
• Face recognition
• face detection – MPEG-7
August 9-10 SISAP 2012, Toronto, Canada 25
Signal Processing
• Vast amount of signals produced:
– Biomedicine data – ECG, CT
– Biometric data – personal identification
– Audio data – audio similarity, recognition
– Sub-image searching
– Financial time series – analysis, forecasting
– Time series streams
• Demand for
– a graceful handling of this data
– flexible reactions to new application needs
Search – the goals
1. We search to get results
2. We ask to find answers
3. We use filters so that the right staff finds us
4. We browse while wandering and way-finding
in restricted space
• In reality, we move fluidly between modes of
ask, browse, filter, and search
August 9-10 SISAP 2012, Toronto, Canada 27
Search – the traditional way
• Defined by software
• Buy engine, then figure out what it is good for
• It often fails because
– It is not easy to use
– It is not able to handle needed content types
August 9-10 SISAP 2012, Toronto, Canada 28
Search – some quantitative facts
• 85% of all web traffic comes from search
engines
• 450+ million searches/day are performed in
North America alone
• 70%+ of all searches are done on Google sites
Search is the most popular application
(second to E-mail??)
August 9-10 29SISAP 2012, Toronto, Canada
Search – the best first
• 60% of searchers NEVER go past 1st page of
search results
• The top three results draw 80% of the
attention
• The first few results inordinately influence
query reformulation.
August 9-10 SISAP 2012, Toronto, Canada 30
Search - as an interaction
• When we search, our next actions are reactions
to the stimuli of a previous search
• What we find is changing what we seek
• In any case, search must be:
fast, simple, and relevant
August 9-10 31SISAP 2012, Toronto, Canada
Search – basic components
• Elements of global search:
Users – goals, psychology, behavior
Interface – interaction, affordances, language
Engine – features, technology, algorithms
Content – indexing structure, metadata
Creators – tools, process, incentives
August 9-10 SISAP 2012, Toronto, Canada 32
Search – changes our cognitive habits
• Assuming information continually and
instantaneously available on the web:
1. We are increasingly handing off the job of
remembering to search engines
2. When we need answer, we do not think, we go
immediately to a nearest Web connection
3. When we expect information to be easily found
again, we do not remember it well
4. Our original memory of facts is changing to a
memory of ways to find the facts
August 9-10 SISAP 2012, Toronto, Canada 33
SISAP 2012, Toronto, Canada 34
Users and their Intent
Search is subjective and also depends on visual and
emotional attributes, e.g. shocking, funny, etc.
• Browser
– not clear end-goal; series of unrelated searches; jump
across unrelated topics; expects surprises and random
search hints
• Surfer
– moderate clarity of end-goal; exploratory actions at the
beginning; e.g. planning a holiday
• Searcher
– very clear about what is searching for; completeness and
clarity of results are important
Context
Content
Prevalent strategy
August 9-10
Evolution of Search Engine Strategies
Scalability
data volume
number of users (queries)
variety of data types
multi-aspect queries
grade
high
low
well established cutting-edge research
peer-to-peer
centralized
parallel
distributed
self-organized
August 9-10 35SISAP 2012, Toronto, Canada
Determinism
exact match ► similarity
precise ► approximate
same answer ► variable
fixed infrastr. ► mapping
The MUFIN Approach
MUFIN: MUlti-Feature Indexing Network
SEARCH
infrastructure
Scalability
P2P structure
Extensibility
metric space
Independence
Infrastructure as a service
August 9-10 36SISAP 2012, Toronto, Canada
Infrastructure Independence: MESSIF
Metric Similarity Search Implementation Framework
Metric space (D,d) Operations Storage
Centralized index structures
Distributed index structures
Communication
Net
Vectors
• Lp and quadratic form
Strings
• (weighted) edit and
protein sequence
Insert, delete,
range query,
k-NN query,
Incremental k-NN
Volatile memory
Persistent memory
Performance statistics
August 9-10 37SISAP 2012, Toronto, Canada
MUFIN
SEARCH
ENGINE
infrastructure
Scalability
M-Chord + M-Index
Extensibility
COPHIR
edge histogram
color structure
scalable color
homogeneous texture
color layout
6 x IBM server x3400 – 2 servers used
Image Search Demo
http://mufin.fi.muni.cz/imgsearch/
August 9-10 38SISAP 2012, Toronto, Canada
MUFIN demos
• http://mufin.fi.muni.cz/imgsearch/similar
• http://www.pixmac.com/
• http://mufin.fi.muni.cz/twenga/random
• http://mufin.fi.muni.cz/fingerprints/random
• http://mufin.fi.muni.cz/subseq/random
• http://mufin.fi.muni.cz/mma-faces-extended/
• http://mufin.fi.muni.cz/plugins/annotation
August 9-10 39SISAP 2012, Toronto, Canada
Limitations: Data Types
We know
• Attributes
– Numbers, strings, etc.
• Text (text-based)
– Documents, annotations
We need
• Multimedia
– Image, video, audio
• Security
– Biometrics
• Medicine
– EKG, EEG, EMG, EMR, CT, etc.
• Scientific data
– Biology, chemistry, physics,
life sciences, economics
• Others
– Motion, emotion, events, etc.
August 9-10 40SISAP 2012, Toronto, Canada
Limitations: Models of Similarity
We know
• Simple geometric models,
typically vector spaces
(metric spaces)
We need
• More complex model
• Non metric models
• Asymmetric similarity
• Subjective similarity
• Context aware similarity
• Complex similarity
• Etc.
August 9-10 41SISAP 2012, Toronto, Canada
Limitations: Queries
We know
• Simple query
– Nearest neighbor
– Range
We need
• More query types
– Reverse NN, distinct NN,
similarity join
• Other similarity-based
operations
– Filtering, classification, event
detection, clustering, etc.
• Similarity algebra
– May become the basis of a
“Similarity Data Management
System”
August 9-10 42SISAP 2012, Toronto, Canada
Limitations: Implementation Strategies
We know
• Centralized or parallel
processing
We need more
• Scalable and distributed
architectures
• MapReduce like approaches
• P2P architectures
• Cloud computing
• Self-organized architectures
• Etc.
August 9-10 43SISAP 2012, Toronto, Canada
Problems with Current Applications
1. Current applications are implemented as
complex software projects; it is costly, highly
qualified specialists are needed
2. They fitfully need massive infrastructure to
build and run multiple indices
3. Applications are much more complex than a
search, which is an important supporting
service
August 9-10 SISAP 2012, Toronto, Canada 44
Similarity
Search
Computing
effectiveness efficiency
stimuli
operators
Similarity Data Management System
August 9-10 45SISAP 2012, Toronto, Canada
findability
retrieval
Cloud
Services
Application
Areas
web
enterprise
mobile
social
Similarity Searching in Clouds
• Retrieval – effectiveness, evaluation, operations, execution, and
efficiency
• Findability – effectiveness, matching, stimuli, extraction, and
efficiency
• Cloud way of computing:
– Scalability – must balance load across servers and avoid bottlenecks
– Elasticity – to allow adding (reducing) capacity to a running system
– Availability – to provide high levels of usability and fault tolerance
– Privacy – to safeguard data that is valuable or sensitive against
unauthorized access
August 9-10 46SISAP 2012, Toronto, Canada
Five Years of SISAP Conferences
strong points
• Organized every year
• SISAP home page
• A workshop has turned into an
international conference
• We are leaders in metric
search theory and technology
• Prestigious conf. proceedings
publisher (LNCS)
• Journal publications from
SISAP conferences
weak points
• Too few submissions
• Narrow and closed community
• Few application papers
• No contacts to related
scientific events – e.g. tutorials
• We are little interested in
actual search systems
• No cooperation with industry
August 9-10 47SISAP 2012, Toronto, Canada
Next Years of SISAP Conferences
Questions to be discussed:
• Do we need a change?
• Do we want to change?
• What is to be changed and how?
• Are we able to do it?
• Who is willing to do the work?
• … ?
August 9-10 SISAP 2012, Toronto, Canada 48