research-article

Efficient top-k retrieval with signatures

Authors:

Timothy Chappell,

Shlomo Geva,

Anthony Nguyen,

Guido ZucconAuthors Info & Claims

ADCS '13: Proceedings of the 18th Australasian Document Computing Symposium

Pages 10 - 17

https://doi.org/10.1145/2537734.2537742

Published: 05 December 2013 Publication History

Get Access

Abstract

This paper describes a new method of indexing and searching large binary signature collections to efficiently find similar signatures, addressing the scalability problem in signature search. Signatures offer efficient computation with acceptable measure of similarity in numerous applications. However, performing a complete search with a given search argument (a signature) requires a Hamming distance calculation against every signature in the collection. This quickly becomes excessive when dealing with large collections, presenting issues of scalability that limit their applicability.

Our method efficiently finds similar signatures in very large collections, trading memory use and precision for greatly improved search speed. Experimental results demonstrate that our approach is capable of finding a set of nearest signatures to a given search argument with a high degree of speed and fidelity.

References

[1]

Andrei Z Broder. On the resemblance and containment of documents. In Compression and Complexity of Sequences 1997. Proceedings, pages 21--29. IEEE, 1997.

Digital Library

Google Scholar

[2]

Trevor Cohen, Roger Schvaneveldt, and Dominic Widdows. Reflective random indexing and indirect inference: A scalable method for discovery of implicit connections. Journal of Biomedical Informatics, 43(2): 240--256, 2010.

Digital Library

Google Scholar

[3]

Shlomo Geva and Christopher M De Vries. Topsig: topology preserving document signatures. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management, pages 333--338. ACM, 2011.

Digital Library

Google Scholar

[4]

Richard W Hamming. Error detecting and error correcting codes. Bell System technical journal, 29(2): 147--160, 1950.

Google Scholar

[5]

Kalervo Järvelin and Jaana Kekäläinen. IR evaluation methods for retrieving highly relevant documents. In Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, pages 41--48. ACM, 2000.

Digital Library

Google Scholar

[6]

Gurmeet Singh Manku, Arvind Jain, and Anish Das Sarma. Detecting near-duplicates for web crawling. In Proceedings of the 16th International Conference on World Wide Web, pages 141--150. ACM, 2007.

Digital Library

Google Scholar

[7]

Caitlin Sadowski and Greg Levin. Simhash: Hash-based similarity detection. Technical report, Technical report, Google, 2007.

Google Scholar

[8]

Malcolm Slaney and Michael Casey. Locality-sensitive hashing for finding nearest neighbors {lecture notes}. Signal Processing Magazine, IEEE, 25(2): 128--131, 2008.

Crossref

Google Scholar

[9]

Yisong Yue, Thomas Finley, Filip Radlinski, and Thorsten Joachims. A support vector method for optimizing average precision. In Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, pages 271--278. ACM, 2007.

Digital Library

Google Scholar

Cited By

View all

Wahed MGruhl DAlba AGentile ARistoski PDeLuca CWelch SLourentzou IDemartini GZuccon GCulpepper JHuang ZTong H(2021)SAUCEProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3481950(4173-4183)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3481950
Blokland BTheoharis T(2020)An indexing scheme and descriptor for 3D object retrieval based on local shape queryingComputers & Graphics10.1016/j.cag.2020.09.00192(55-66)Online publication date: Nov-2020
https://doi.org/10.1016/j.cag.2020.09.001
Roegiest ALee EPiwowarski BChevalier MGaussier EMaarek YNie JScholer F(2019)On Tradeoffs Between Document Signature Methods for a Legal Due Diligence CorpusProceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3331184.3331311(1001-1004)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1145/3331184.3331311
Show More Cited By

Index Terms

Efficient top-k retrieval with signatures
1. Information systems
  1. Information retrieval
  2. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

On the Problem of in Locality-Sensitive Hashing
Similarity Search and Applications
Abstract
A Locality-Sensitive Hash (LSH) function is called (r, cr, -sensitive, if two data-points with a distance less than r collide with probability at least while data points with a distance greater than cr collide with probability at most . These ...
Index Structures for Fast Similarity Search for Binary Vectors

This article reviews index structures for fast similarity search for objects represented by binary vectors (with components equal to 0 or 1). Structures for both exact and approximate search by Hamming distance and other similarity measures are ...
Query-specific signature selection for efficient k-nearest neighbour approximation

Finding k-nearest neighbours k-NN is one of the most important primitives of many applications such as search engines and recommendation systems. However, its computational cost is extremely high when searching for k-NN points in a huge collection of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ADCS '13: Proceedings of the 18th Australasian Document Computing Symposium

December 2013

126 pages

ISBN:9781450325240

DOI:10.1145/2537734

Conference Chairs:
Shane Culpepper
RMIT University
,
Guido Zuccon
CSIRO
,
General Chair:
Laurianne Sitbon
Queensland University of Technology

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

In-Cooperation

SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 December 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ADCS '13

ADCS '13: The Australasian Document Computing Symposium

December 5 - 6, 2013

Queensland, Brisbane, Australia

Acceptance Rates

ADCS '13 Paper Acceptance Rate 12 of 23 submissions, 52%;

Overall Acceptance Rate 30 of 57 submissions, 53%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
120
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Wahed MGruhl DAlba AGentile ARistoski PDeLuca CWelch SLourentzou IDemartini GZuccon GCulpepper JHuang ZTong H(2021)SAUCEProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3481950(4173-4183)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3481950
Blokland BTheoharis T(2020)An indexing scheme and descriptor for 3D object retrieval based on local shape queryingComputers & Graphics10.1016/j.cag.2020.09.00192(55-66)Online publication date: Nov-2020
https://doi.org/10.1016/j.cag.2020.09.001
Roegiest ALee EPiwowarski BChevalier MGaussier EMaarek YNie JScholer F(2019)On Tradeoffs Between Document Signature Methods for a Legal Due Diligence CorpusProceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/3331184.3331311(1001-1004)Online publication date: 18-Jul-2019
https://dl.acm.org/doi/10.1145/3331184.3331311
Van TLe T(2018)Content-based image retrieval using a signature graph and a self-organizing mapInternational Journal of Applied Mathematics and Computer Science10.5555/3060518.306052226:2(423-438)Online publication date: 15-Dec-2018
https://dl.acm.org/doi/10.5555/3060518.3060522
Van TLe T(2017)Content‐based image retrieval based on binary signatures cluster graphExpert Systems10.1111/exsy.1222035:1Online publication date: 2-Jul-2017
https://doi.org/10.1111/exsy.12220
Buckingham LChappell THogan JGeva S(2017)Similarity Projection: A Geometric Measure for Comparison of Biological Sequences2017 IEEE 13th International Conference on e-Science (e-Science)10.1109/eScience.2017.46(325-334)Online publication date: Oct-2017
https://doi.org/10.1109/eScience.2017.46
Van TLe T(2016)Clustering Binary Signature Applied in Content-Based Image RetrievalNew Advances in Information Systems and Technologies10.1007/978-3-319-31232-3_22(233-242)Online publication date: 2-Mar-2016
https://doi.org/10.1007/978-3-319-31232-3_22

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

On the Problem of in Locality-Sensitive Hashing

Index Structures for Fast Similarity Search for Binary Vectors

Query-specific signature selection for efficient k-nearest neighbour approximation

Comments

Information

Published In

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations