Similarity Search and Applications: 14th International Conference, SISAP 2021, Dortmund, Germany, September 29 – October 1, 2021, Proceedings ... Applications, incl. Internet/Web, and HCI)

This book constitutes the refereed proceedings of the 14th International Conference on Similarity Search and Applications, SISAP 2021, held in Dortmund, Germany, in September/October 2021. The conference was held virtually due to the COVID-19 pandemic. The 23 full papers presented together with 5 short and 3 doctoral symposium papers were carefully reviewed and selected from 50 submissions. The papers are organized in the topical sections named: ​Similarity Search and Retrieval; Intrinsic Dimensionality; Clustering and Classification; Applications of Similarity Search; Similarity Search in Graph-Structured Data; Doctoral Symposium. Preface Organization Contents Similarity Search and Retrieval Organizing Similarity Spaces Using Metric Hulls 1 Introduction 2 Preliminaries 2.1 Hull Representation 3 Existing Metric Access Methods 4 MH-Tree – The Proposed Method 4.1 Structure and Bulk Loading 4.2 Searching in the MH Tree 4.3 Dynamicity 5 Experimental Evaluation 5.1 Ordering Leaf Nodes 5.2 Ordering Internal Nodes 5.3 Comparison 6 Conclusions References Scaling Up Set Similarity Joins Using a Cost-Based Distributed-Parallel Framework 1 Introduction 2 Distributing Filter-and-Verification-Based SSJ 2.1 Data-Dependent Cost-Based Heuristic 2.2 Data-Independent Scaling Mechanism 2.3 RAM Demand 2.4 Cost Distribution Quality 2.5 Finding Suitable Parameter Values 3 Experiments 3.1 Impact of Cost-Based Heuristic 3.2 Impact of Data-Independent Scaling Mechanism 3.3 Impact of Dataset Size 3.4 Discussion of Parameter Finding Strategy 4 Conclusion References A Triangle Inequality for Cosine Similarity 1 Introduction 2 Cosine Distance and Euclidean Distance 3 Constructing a Triangle Inequality for Cosine Similarity 3.1 Opposite Direction 3.2 Angles are Not Ptolematic 4 Experiments 4.1 Approximation Quality 4.2 Numerical Stability 4.3 Runtime Experiments 5 Conclusions References A Cost Model for Reverse Nearest Neighbor Query Processing on R-Trees Using Self Pruning 1 Introduction 2 Related Work 3 A Cost Model for Self Pruning Approaches 4 Preliminary Empirical Study 5 Discussion References How Many Neighbours for Known-Item Search? 1 Introduction 2 Known-Item Search 2.1 Problem Formulation 2.2 Ranking Model Evaluation 3 Experiments 3.1 Known-Item Search Benchmark Set 3.2 Upper Performance Estimates for kNN Browsing 3.3 A Baseline Study for Efficient Candidate Set Selection 4 Is There a Room for Competitive Metric Indexing? 5 Conclusions References On Generalizing Permutation-Based Representations for Approximate Search 1 Introduction 2 Permutation-Based Representation(s) of a Metric Object 3 Pivot Pairs Permutations 4 Experiments 4.1 Experiments on Synthetic Data 4.2 Experiments on Real-World Data 5 Conclusions References Data-Driven Learned Metric Index: An Unsupervised Approach 1 Introduction 2 Related Work 3 Indexing in Metric Spaces 4 Learned Metric Index 4.1 Training Unsupervised LMI 4.2 Searching in LMI 4.3 Machine Learning Models 5 Experiments 5.1 Building Costs 5.2 Tuning of Learned Models 5.3 Results 5.4 Summary 6 Conclusion References Towards a Learned Index Structure for Approximate Nearest Neighbor Search Query Processing 1 Introduction 2 Background 2.1 ANN Query Processing: Preliminaries and Related Work 2.2 Learned Index Structures 2.3 Contributions 3 Towards a Learned Index for ANN Search 4 Evaluation 4.1 Set-Up 4.2 Results 5 Summary References Similarity vs. Relevance: From Simple Searches to Complex Discovery 1 Introduction 1.1 Discovery of Open Datasets by Similarity 2 Related Work 2.1 Similarity Modeling 2.2 Retrieval Mechanisms 2.3 Dataset Discovery 3 Data-Transitive Similarity 3.1 Implementation 3.2 Open Dataset Testbed 4 Evaluation 4.1 Methodology 4.2 Results 4.3 Qualitative Analysis 5 Conclusion and Future Work References Non-parametric Semi-supervised Learning by Bayesian Label Distribution Propagation 1 Introduction 2 Related Work 3 Label Probability Distribution Propagation 3.1 Motivation 3.2 General Schema 3.3 kNN-Label Distribution 3.4 Abstention in Case of Insufficient Information 3.5 Propagation Algorithm 3.6 Advantages and Disadvantages of `3́9`42`"̇613A``45`47`"603AkNN-LDP 4 Experimental Evaluation 4.1 Competitors 4.2 Parameters 4.3 Datasets 4.4 Evaluation Setup 4.5 Results 4.6 Scalability 5 Conclusion References Optimizing Fair Approximate Nearest Neighbor Searches Using Threaded B+-Trees 1 Introduction 1.1 Motivation 1.2 Contributions 2 Related Work 2.1 LSH and Its Variants 2.2 Fairness in ANN Search 3 Background and Key Concepts 4 Problem Specification 5 FairLSH 5.1 Naive Approaches 5.2 Design of FairLSH-Basic 5.3 Drawbacks of FairLSH-Basic 5.4 Design of FairLSH-Advanced 6 Experimental Evaluation 6.1 Datasets 6.2 Evaluation Criteria 6.3 Parameter Settings 6.4 Discussion of the Results 7 Conclusion and Future Work References Fairest Neighbors 1 Introduction 2 Complex Queries as Multicriteria Decisions 3 Ordered Weighted Averages and Linear Ambits 4 Experiments 5 Conclusions and Future Work References Intrinsic Dimensionality Local Intrinsic Dimensionality and Graphs: Towards LID-aware Graph Embedding Algorithms 1 Introduction 2 LID and Graphs 3 NC-LID: LID-related Measure for Graph Nodes Based on Natural Communities 4 LID-elastic Node2Vec Variants 5 Experiments and Results 5.1 Natural Communities and NC-LID 5.2 Node2Vec Evaluation 5.3 LID-elastic Node2Vec Evaluation 6 Conclusions and Future Work References Structural Intrinsic Dimensionality 1 Introduction 2 The Fundamental Information Behind Local Dimensionality 2.1 Motivation for an Estimation 2.2 Expansion-Based Estimation 2.3 Concentration of Correlates 2.4 Sphere Packing 2.5 Discussion 3 Information Propagation on Neighbor Graphs 3.1 Structural Regression 3.2 Experiments 4 Structural Intrinsic Dimensionality 4.1 Experiments 5 Conclusion References Relationships Between Local Intrinsic Dimensionality and Tail Entropy 1 Introduction 2 Related Work 3 Local Intrinsic Dimensionality 4 Tail Entropy and LID 4.1 Definitions of Tail Entropy Variants 4.2 Technical Preliminaries 4.3 Cumulative Tail Entropy and LID 4.4 Tail Entropy Power and LID 5 Conclusion References The Effect of Random Projection on Local Intrinsic Dimensionality 1 Introduction 2 Local Intrinsic Dimensionality 2.1 Intrinsic Dimensionality and Indiscriminability 2.2 Two Properties of Local ID 3 Intrinsic Dimensionality After Projection 3.1 Random Projection 3.2 Proof of Theorem 4 4 Conclusion References Clustering and Classification Accelerating Spherical k-Means 1 Introduction 2 Foundations 3 Pruning with Cosine Similarity 4 Upper and Lower Bounds 5 Accelerated Spherical k-Means 5.1 Spherical Simplified Elkan's Algorithm 5.2 Spherical Elkan's Algorithm 5.3 Spherical Hamerly's Algorithm 5.4 Spherical Simplified Hamerly's Algorithm 5.5 Further k-Means Variants 5.6 Spherical k-means++ 6 Experiments 7 Conclusions References MESS: Manifold Embedding Motivated Super Sampling 1 Introduction 2 Related Work 3 Manifold Faithful Supersampling 3.1 Approaching the Embedding Function 3.2 Supersampling Pipeline 3.3 Supersampling Modules 4 Evaluation 5 Conclusions References Handling Class Imbalance in k-Nearest Neighbor Classification by Balancing Prior Probabilities 1 Introduction 2 Related Work 2.1 External Approaches 2.2 Internal Approaches and Modifications of the kNN Classifier 2.3 Cost-Sensitive Learning and k-Nearest Neighbors 2.4 Summary 3 Class-Balanced k-Nearest Neighbors Classification 3.1 Basic Weighted kNN 3.2 Balancing a Probabilistic k-Nearest Neighbor Classifier 3.3 On the Difference Between Weighted `3́9`42`"̇613A``45`47`"603AkNN and Adjustment of Prior Class Probabilities 4 Experimental Evaluation 4.1 Datasets 4.2 Compared Methods 4.3 Parameter Selection 4.4 Evaluation Measures 4.5 Results 5 Conclusion References Applications of Similarity Search Similarity Search for an Extreme Application: Experience and Implementation 1 Introduction 2 Similarity of Protein Chains 2.1 Properties of Descriptors 2.2 Similarity Score 2.3 Transformation of Qscores to Distances 2.4 Curse of Dimensionality 2.5 Distance Function Complexity 3 Gradual Similarity Search 3.1 Data Preprocessing and Sketches 3.2 First Phase of the Query Execution 3.3 Second Phase of the Query Execution 3.4 Third Phase of the Query Execution 4 Experiments 5 Conclusions References What Makes a Good Movie Recommendation? Feature Selection for Content-Based Filtering 1 Introduction 2 Related Works 3 Recommender System Used in Experiments 3.1 Recommending Approach 3.2 Movies Dataset 3.3 Features Representations 4 Evaluation and Feature Selection Methods 4.1 Comparing Recommenders Performance 4.2 Collecting Relevance Judgments 4.3 Selecting Optimal Weights 4.4 Finding the Best Set of Features 5 Experimental Results 5.1 How to Represent Features Effectively? 5.2 Which Features Are Relevant? 5.3 Which Single Feature Provides Best Recommendations? 5.4 Do We Need All Features to Get Good Recommendations? 5.5 Are Relevance Judgments Credible? 6 Conclusions References Indexed Polygon Matching Under Similarities 1 Introduction 1.1 The Problem: Indexed Polygon Matching 1.2 Summary of Results 1.3 Related Work 2 Invariants 2.1 Similarity Invariants for Polygons 2.2 Cyclic Shifts and Reversed Labeling 2.3 An Index for Matching Polygons 3 Experiments in Polygon Matching with Noise 3.1 Fixing Recall for Convex Polygons 4 Final Remarks References Clustering Adverse Events of COVID-19 Vaccines Across the United States 1 Introduction 2 Related Work 3 Problem Definition 4 Latent Adverse Event Topic Modeling 5 Spatial Clustering of Vaccine Adverse Event Topics 6 Spatial Autocorrelation 7 Experimental Evaluation 7.1 Qualitative Analysis of Topics 7.2 Spatial Anaylsis of COVID-19 Adverse Event Topics 8 Conclusions References Similarity Search in Graph-Structured Data Metric Indexing for Graph Similarity Search 1 Introduction 2 Related Work 2.1 Similarity Search in Graph Databases 2.2 Pairwise Computation of the Graph Edit Distance 3 Preliminaries 3.1 Graph Theory 3.2 Searching in Databases 4 Efficient Filtering for the General Graph Edit Distance 4.1 Index-Accelerated Lower Bound Filtering 4.2 Upper Bound Filtering and Verification 4.3 Nearest-Neighbor Queries 5 Experimental Evaluation 5.1 Setup 5.2 Results 6 Conclusions References The Minimum Edit Arborescence Problem and Its Use in Compressing Graph Collections 1 Introduction 2 Preliminaries 3 The Minimum Edit Arborescence Problem 4 Minimum Graph Edit Arborescence Problem 5 Arborescence-Based Compression 6 Experiments 7 Conclusions References Graph Embedding in Vector Spaces Using Matching-Graphs 1 Introduction and Related Work 2 Graphs and Graph Edit Distance – Basic Definitions 2.1 Graph and Subgraph 2.2 Graph Matching 3 Graph Embedding by Means of Matching-Graphs 3.1 Graph Embedding Using Matching-Graphs 3.2 Creating Matching-Graphs 4 Experimental Evaluation 4.1 Experimental Setup 4.2 Validation of Metaparameters 4.3 Test Results and Discussion 5 Conclusions and Future Work References An A*-algorithm for the Unordered Tree Edit Distance with Custom Costs 1 Introduction 2 Background and Related Work 3 Method 4 Experiments 5 Conclusion References FIMSIM: Discovering Communities by Frequent Item-Set Mining and Similarity Search 1 Introduction 2 Related Work 2.1 Clique Percolation 2.2 Local Expansion 2.3 Link Clustering 3 Community Mining Process 3.1 Preliminaries 3.2 FIMSIM: Community Mining Algorithm 4 Experiments 4.1 Dataset 4.2 Evaluation Criteria 4.3 Evaluation 5 Conclusion References Doctoral Symposium Towards an Italian Healthcare Knowledge Graph 1 Introduction 2 Planned Methodology 2.1 Language Model: Pre-training and Fine-Tuning 2.2 Entity Linking 2.3 Knowledge Graph Analysis 3 Early Results 4 Conclusion and Future Work References Progressive Query-Driven Entity Resolution 1 Introduction 2 Related Work 3 BrewER: A Progressive Query-Driven ER Framework 4 Evaluation 5 Conclusions and Next Steps References Discovering Latent Information from Noisy Sources in the Cultural Heritage Domain 1 Introduction 2 Methodology 2.1 Social Media to Our Help (?) 2.2 A Multi-modal Approach 2.3 A Specific Task: Entity and Entity Type Recognition 3 Conclusions and Future Work References Author Index