Set2Box: Similarity Preserving Representation Learning for Sets

Abstract

Sets have been used for modeling various types of objects, and measuring similarity between them has been a key building block of a wide range of applications. However, as sets have grown in numbers and sizes, the computational cost and storage required for set similarity computation have become substantial. In this work, we propose SET2Box, which represents sets as boxes to precisely capture overlaps of sets and thus accurately estimate various similarity measures. Additionally, based on the proposed box quantization scheme, we design SET2Box+, which yields more concise but more accurate box representations of sets. Through extensive experiments on 8 real-world datasets, we show that, compared to baseline approaches, SET2Box+ is (a) Accurate: achieving up to 40.8× smaller estimation error while requiring 60% fewer bits to encode sets, (b) Concise: yielding up to 96.8× more concise representations with similar estimation error, and (c) Versatile: enabling the estimation of four set-similarity measures from a single representation of each set. For reproducibility, the source code and datasets used in the paper are available at https://github.com/geon0325/Set2Box. © 2022 IEEE.