Sizing sketches: A rank-based analysis for similarity search

Zhe Wang, Wei Dong, William Josephson, Qin Lv, Moses Charikar, Kai Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

31 Scopus citations


Sketches are compact data structures that can be used to estimate properties of the original data in building large-scale search engines and data analysis systems. Recent theoretical and experimental studies have shown that sketches constructed from feature vectors using randomized projections can effectively approximate L1 distance on the feature vectors with the Hamming distance on their sketches. Furthermore, such sketches can achieve good filtering accuracy while reducing the metadata space requirement and speeding up similarity searches by an order of magnitude. However, it is not clear how to choose the size of the sketches since it depends ondata type, dataset size, and desired filtering quality. In real systems designs, it is necessary to understand how to choose sketch size without the dataset, or at least without the whole datase. This paper presents an analytical model and experimental results to help system designers make such design decisions. We present arank-based filtering model that describes the relationship between sketch size and data set size based on the dataset distance distribution. Our experimental results with several datasets including images, audio, and 3D shapes show that the model yields good, conservative predictions. We show that the parameters of the model can be set with a small sample data set and the resulting model can make good predictions for a large dataset. We illustrate how to apply the approach with a concrete example.

Original languageEnglish (US)
Title of host publicationSIGMETRICS'07 - Proceedings of the 2007 International Conference on Measurement and Modeling of Computer Systems
Number of pages12
StatePublished - 2007
Externally publishedYes
EventSIGMETRICS'07 - 2007 International Conference on Measurement and Modeling of Computer Systems - San Diego, CA, United States
Duration: Jun 12 2007Jun 16 2007

Publication series

NamePerformance Evaluation Review
ISSN (Print)0163-5999


OtherSIGMETRICS'07 - 2007 International Conference on Measurement and Modeling of Computer Systems
Country/TerritoryUnited States
CitySan Diego, CA

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


  • Feature-rich data
  • Similarity search
  • Sketch


Dive into the research topics of 'Sizing sketches: A rank-based analysis for similarity search'. Together they form a unique fingerprint.

Cite this