NTSS 2011


1st Workshop on

New Trends in Similarity Search


in Conjunction with the EDBT 2011 Conference, Uppsala, Sweden

Important Dates | Submission Guidelines | Keynote TalkWorkshop Committee | PC | Useful Resources

Workshop Flyer

NTSS 2011 Best Paper: "Large Scale Dist-Based Metric Indexing Structure for Approximate Information Retrieval by Content" by Stansilav Barton, Valerie Gouet-Brunet, Marta Rukoz

Workshop Programme - March 25th, 2011

    09:00 to 10:00  - Invited Talk by Matthias Renz titled "Similarity Search in Uncertain Databases: Challenges, Techniques and New Trends" PDF PPT

    10:00  to 10:25  - Research Paper: Large Scale Disk-Based Metric Indexing Structure for Approximate Information Retrieval by Content  PDF

                                    By Stanislav Barton, Valérie Gouet-Brunet and Marta Rukoz

    10:25 to 10:50  - Research Paper: Finding the k-closest pairs in metric spaces PDF

                                    By Hisashi Kurasawa, Atsuhiro Takasu and Jun Adachi

    10:50 to 11:05  - Break

    11:05 to 11.30  - Research Paper: Restricting the Overlap of Top-N Sets in Schema Matching PDF

                                    By Eric Peukert and Erhard Rahm

    11:30 to 11:55 - Research Paper: A Unifying Probability Measure for Logic-Based Similarity Conditions on Uncertain Relational Data PDF

                                   By Sebastian Lehrack and Ingo Schmitt

   11:55  to 12:20 - Research Paper: Empirical Evaluation of Excluded Middle Vantage Point Forest on Biological Sequences Workload PDF

                                  By Weijia Xu, Lee Thompson and Daniel Miranker

   12:20 to 12:50  - Discussion

Similarity Search is an active area of research with large advances in numeric space similarity search over the last two decades. However, many real world applications deal with complex objects that have attributes of many different types - numeric, string, categorical, set valued etc. The prevalence of large amounts of non-numeric data necessitates designing of new similarity measures, indexing techniques and querying techniques. This includes addressing the challenge of efficiently performing similarity search on various attribute types leveraging different kinds of index structures. In this workshop, we seek papers addressing novel problems that arise in real world applications of similarity search.

Specific topics of interest include (but are in no way, limited to)

  • Similarity Measures
    • Similarity Measures for heterogeneous attribute types (e.g., set values, numeric, string, categorical, time series etc.)
    • Similarity Measures that lead to metric spaces, arbitrary metric spaces, non-metric or (dis)similarity spaces
    • Learning of similarity Measures (e.g., using partially specified supervised information, relevance feedback, active learning etc.)
    • Aggregation of attribute similarities to object similarities (e.g., weighted sum type monotonic aggregates, and non-monotonic aggregates)
  • Indexing for Similarity Search
    • Indexes for various similarity measures and aggregation functions
    • Indexes for handling heterogeneous attributes (e.g., certain objects could have a combination of numeric, categorical, string and set-valued attributes)
    • Indexing for various similarity operators
  • Queries for Similarity Search 
    • Top-k, Skyline, Reverse kNN, Reverse Skyline, Range Queries
    • Other novel operators for Similarity Search
    • Complex Similarity Queries
  • Approximate Similarity Search
  • Scalability (dataset size, number of dimensions etc.) and Performance Studies
  •  Clustering for Similarity Search
  • Practical Experiences
  • \Similarity Search in Relational Database Systems
    • Leveraging traditional SQL style queries for Similarity Search
  • Distributed and Parallel Similarity Search
  • Novel and Domain-Specific Applications of Similarity Search
  • Similarity Search on Uncertain Databases
  • Similarity Search on Streaming Data

Keynote Talk top

We are pleased to announce that the Workshop Program will include a Keynote Talk by Matthias Renz on Similarity Search in Uncertain Databases covering challenges, techniques and new trends in this topic. 

Important Dates top


        Manuscripts Due: January 24, 2011

          Notification of Acceptance: February 14, 2011

          Final Revised Manuscript (for Accepted Papers): February 20, 2011

          Workshop:  March 25, 2011

Submission Guidelines top

We invite original, unpublished manuscripts of up to 6 pages inclusive of all references and figures. Vision papers and descriptions of work-in-progress are welcome as short paper submissions of up to 4 pages. Papers must be in English and formatted according to the ACM double-column format. Manuscripts to be submitted through the EasyChair System here

Workshop Committee top


Workshop Chairs

        Prasad M Deshpande, IBM Research – India

        Deepak P, IBM Research – India

Steering Committee

        Gautam Das, University of Texas at Arlington, USA

        Raghu Krishnapuram, IBM Research – India


Program Committee top

    Debapriyo Majumdar, IBM Research - India

       Karin Murthy, IBM Research - India

       Patrick Lambrix, Linköping University, Sweden 

       Martin Theobald, Max-Planck-Institut für Informatik, Germany

       Peer Kröger, Ludwig-Maximilians-Universität München, Germany

       Demetris Zeinalipour, University of Cyprus, Cyprus

       Reynold C.K. Cheng, University of Hong Kong, Hong Kong

       Reza Akbarinia, INRIA, France

       Evaggelia Pitoura, University of Ioannina, Greece