NDLI: Compressing Locality Sensitive Hashing Tables

Content Provider	IEEE Xplore Digital Library
Author	Santoyo, F. Chavez, E. Tellez, E.S.
Copyright Year	2013
Description	Author affiliation: Fac. de Fisico-Mat., Univ. Michoacana de San Nicolas de Hidalgo, Hidalgo, Mexico (Tellez, E.S.) \|\| Inst. de Mat., Univ. Nac. Autonoma de Mexico, Mexico City, Mexico (Chavez, E.) \|\| Div. de Estudios de Posgrado de la Fac. de Ing. Electr., Univ. Michoacana de San Nicolas de Hidalgo, Hidalgo, Mexico (Santoyo, F.)
Abstract	LSH is the industry standard for proximity searching tasks on collections of data having coordinates. An LSH index applies a set of hashing functions to the representation of an object to identify proximal objects to a query, leaving distal objects apart. In other words, objects with the same hash will be mutually proximal with high probability. LSH is very fast and gives probabilistic guarantees on the quality of the results. On the other hand, mobile applications using proximity queries are becoming common place. Feature extraction can be done in a smart phone. However, the actual query rely on a wireless link because memory is a scarce resource. To tackle the above problem, we present in this paper a method to compress the LSH index while still being able to query without decompressing. The query speed is practically the same, and can even be faster. We derive a lower bound on the memory requirements for the compress representation and present an implementation using close to optimal storage. We provide an extensive experimental comparison of our compressed representation against the uncompressed one over a large database of 55 million objects. We obtained a compression ratio ranging from 70% to 80% without slowing down, in practice, the search speed.
Starting Page	41
Ending Page	46
File Size	186486
Page Count	6
File Format	PDF
ISBN	9780769550879
ISSN	15504069
DOI	10.1109/ENC.2013.12
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2013-10-30
Publisher Place	Mexico
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Indexes Memory management Approximation algorithms Probabilistic logic Measurement Electronic mail Succinct Proximity Search Indexes Locality Sensitive Hashing
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