Similarity Search and Applications

1. Front Matter

   PDF

2. Invited Papers

   1. Effective Principal Component Analysis

      • Santosh S. Vempala

      Pages 1-7

   2. Future Trends in Similarity Searching

      • Pavel Zezula

      Pages 8-24

3. New Scenarios and Approaches

   1. Snake Table: A Dynamic Pivot Table for Streams of k-NN Searches

      • Juan Manuel Barrios, Benjamin Bustos, Tomáš Skopal

      Pages 25-39

   2. Algorithmic Exploration of Axiom Spaces for Efficient Similarity Search at Large Scale

      • Tomáš Skopal, Tomáš Bartoš

      Pages 40-53

   3. Polyphasic Metric Index: Reaching the Practical Limits of Proximity Searching

      • Eric Sadit Tellez, Edgar Chavez, Karina Figueroa

      Pages 54-69

4. Improving Metric Data Structures

   1. Efficient Similarity Search in Metric Spaces with Cluster Reduction

      • Luis G. Ares, Nieves R. Brisaboa, Alberto Ordóñez Pereira, Oscar Pedreira

      Pages 70-84

   2. Cut-Region: A Compact Building Block for Hierarchical Metric Indexing

      • Jakub Lokoč, Přemysl Čech, Jiří Novák, Tomáš Skopal

      Pages 85-100

   3. Static-to-Dynamic Transformation for Metric Indexing Structures

      • Bilegsaikhan Naidan, Magnus Lie Hetland

      Pages 101-115

5. Facing Scalability Issues

   1. DSACL+-tree: A Dynamic Data Structure for Similarity Search in Secondary Memory

      • Luis Britos, A. Marcela Printista, Nora Reyes

      Pages 116-131

   2. Scalable Distributed Algorithm for Approximate Nearest Neighbor Search Problem in High Dimensional General Metric Spaces

      • Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, Vladimir Krylov

      Pages 132-147

   3. Parallel Approaches to Permutation-Based Indexing Using Inverted Files

      • Hisham Mohamed, Stéphane Marchand-Maillet

      Pages 148-161

6. Searching in Specific Spaces

   1. Super-Linear Indices for Approximate Dictionary Searching

      • Leonid Boytsov

      Pages 162-176

   2. Visual Image Search: Feature Signatures or/and Global Descriptors

      • Jakub Lokoč, David Novák, Michal Batko, Tomáš Skopal

      Pages 177-191

7. New Similarity Spaces

   1. Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance

      • Tomáš Bartoš, Tomáš Skopal

      Pages 192-208

   2. A Multivariate Correlation Distance for Vector Spaces

      • Richard Connor, Robert Moss

      Pages 209-225

   3. Fast Similarity Computation in Factorized Tensors

      • Michael E. Houle, Hisashi Kashima, Michael Nett

      Pages 226-239

8. Demo Papers

   1. SIR: The Smart Image Retrieval Engine

      • Jakub Lokoč, Tomáš Grošup, Tomáš Skopal

      Pages 240-241

   2. SimTandem: Similarity Search in Tandem Mass Spectra

      • Jiří Novák, Jakub Galgonek, David Hoksza, Tomáš Skopal

      Pages 242-243

   3. Erratum: Parallel Approaches to Permutation-Based Indexing Using Inverted Files

      • Hisham Mohamed, Stéphane Marchand-Maillet

      Pages E1-E2

This book constitutes the proceedings of the 5th International Conference on Similarity Search and Applications, SISAP 2012, held in Toronto, Canada, in August 2012. The 14 full papers presented in this volume, together with 2 demo papers and 2 invited talks, were carefully reviewed and selected from 19 submissions. The papers deal with many of the most relevant aspects of similarity searching and are organized in topical sections named: new scenarios and approaches; improving metric data structures; facing scalability issues; searching in specific spaces; and new similarity spaces.

• approximation
• distance-based search
• image retrieval
• indexing
• non-metric spaces
• data structures
• algorithm analysis and problem complexity

• Department of Computer Science, University of Chile, Chile

  Gonzalo Navarro

• Department of Mathematics and Statistics, University of Ottawa, Ottawa, Canada

  Vladimir Pestov

Policies and ethics