NDLI: Efficient Similarity Search by Reducing I/O with Compressed Sketches

Please wait, while we are loading the content...

Cover Art

Title Page i

Title Page iii

Foreword

Preface

External Reviewers

Analyzing Metric Space Indexes: What For?

Combinatorial Framework for Similarity Search

Structural Entropic Difference: A Bounded Distance Metric for Unordered Trees

Curse of Dimensionality in Pivot Based Indexes

CoPhIR Image Collection under the Microscope

EGNAT: A Fully Dynamic Metric Access Method for Secondary Memory

Metric Index: An Efficient and Scalable Solution for Similarity Search

Optimal Pivots to Minimize the Index Size for Metric Access Methods

Dynamic Spatial Approximation Trees for Massive Data

Approximate Direct and Reverse Nearest Neighbor Queries, and the k-nearest Neighbor Graph

Principles of Information Filtering in Metric Spaces

Speeding Up Permutation Based Indexing with Indexing

Parallel Dynamic Batch Loading in the M-tree

Dynamic P2P Indexing and Search Based on Compact Clustering

Query Routing Mechanisms in Self-Organizing Search Systems

OBSearch: A High Performance Similarity Search Engine for Java

MiPai: Using the PP-Index to Build an Efficient and Scalable Similarity Search System

Img(Rummager): An Interactive Content Based Image Retrieval System

img(Anaktisi): A Web Content Based Image Retrieval System

Text-Based and Content-Based Image Retrieval on Flickr: DEMO

MUFIN: A Multi-feature Indexing Network

Using Tuneable Fuzzy Similarity in Non-metric Search

On the Effectiveness of Distances Measuring Protein Structure Similarity

Author Index

Publisher's Information

Efficient Similarity Search by Reducing I/O with Compressed Sketches

Content Provider	ACM Digital Library
Author	Muller-Molina, Arnoldo José Shinohara, Takeshi
Abstract	Sketches are compact bit string representations of objects. Objects that have the same sketch are stored in the same database bucket. By calculating the hamming distance of the sketches, an estimation of the similarity of their respective objects can be obtained. Objects that are close to each other are expected to have sketches with small hamming distance values. This estimation helps to schedule the order in which buckets are visited during search time. Recent research has shown that sketches can effectively approximate \$L_1\$ and \$L_2\$ distances in high dimensional settings. A remaining task is to provide a general sketch for arbitrary metric spaces. This paper presents a novel sketch based on generalized hyperplane partitioning that can be employed on arbitrary metric spaces. The core of the sketch is a heuristic that tries to generate balanced partitions. The indexing method AESA stores all the distances among database objects, and this allows it to perform a small number of distance computations. Experimental evaluations show that given a good early termination strategy, our algorithm performs up to one order of magnitude fewer distance operations than AESA in string spaces. Comparisons against other methods show greater gains. Furthermore, we experimentally demonstrate that it is possible to reduce the physical size of the sketches by a factor of ten with different run length encodings.
Starting Page	30
Ending Page	38
Page Count	9
File Format	PDF
ISBN	9780769537658
DOI	10.1109/SISAP.2009.22
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2009-08-29
Access Restriction	Subscribed
Subject Keyword	Similarity search $k$ nearest neighbor sketch compression
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient Similarity Search by Reducing I/O with Compressed Sketches

Efficient approximate nearest neighbor search with integrated binary codes

L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning

Efficient k-nearest neighbor graph construction for generic similarity measures

New K-nearest neighbor searching algorithm based on angular similarity

Flexible aggregate similarity search

Efficient k-nearest neighbor graph construction for generic similarity measures (2010)

Approximate reverse k-nearest neighbor queries in general metric spaces

Efficient filtering with sketches in the ferret toolkit

Efficient Similarity Search by Reducing I/O with Compressed Sketches

Similar Documents

Efficient Similarity Search by Reducing I/O with Compressed Sketches

Efficient approximate nearest neighbor search with integrated binary codes

L2Knng: Fast Exact K-Nearest Neighbor Graph Construction with L2-Norm Pruning

Efficient k-nearest neighbor graph construction for generic similarity measures

New K-nearest neighbor searching algorithm based on angular similarity

Flexible aggregate similarity search

Efficient k-nearest neighbor graph construction for generic similarity measures (2010)

Approximate reverse k-nearest neighbor queries in general metric spaces

Efficient filtering with sketches in the ferret toolkit

Efficient Similarity Search by Reducing I/O with Compressed Sketches