Generalized compression and compressive search of large datasets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Prior, Morgan E., Howard III, Thomas, Light, Emily, Ishaq, Najib, Daniels, Noah M.
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms Information Retrieval 68P20 E.2; E.4; H.3.2; H.3.3; H.1.1
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

_version_	1866915044974919680
author	Prior, Morgan E. Howard III, Thomas Light, Emily Ishaq, Najib Daniels, Noah M.
author_facet	Prior, Morgan E. Howard III, Thomas Light, Emily Ishaq, Najib Daniels, Noah M.
contents	The Big Data explosion has necessitated the development of search algorithms that scale sub-linearly in time and memory. While compression algorithms and search algorithms do exist independently, few algorithms offer both, and those which do are domain-specific. We present panCAKES, a novel approach to compressive search, i.e., a way to perform $k$-NN and $ρ$-NN search on compressed data while only decompressing a small, relevant, portion of the data. panCAKES assumes the manifold hypothesis and leverages the low-dimensional structure of the data to compress and search it efficiently. panCAKES is generic over any distance function for which the distance between two points is proportional to the memory cost of storing an encoding of one in terms of the other. This property holds for many widely-used distance functions, e.g. string edit distances (Levenshtein, Needleman-Wunsch, etc.) and set dissimilarity measures (Jaccard, Dice, etc.). We benchmark panCAKES on a variety of datasets, including genomic, proteomic, and set data. We compare compression ratios to gzip, and search performance between the compressed and uncompressed versions of the same dataset. panCAKES achieves compression ratios close to those of gzip, while offering sub-linear time performance for $k$-NN and $ρ$-NN search. We conclude that panCAKES is an efficient, general-purpose algorithm for exact compressive search on large datasets that obey the manifold hypothesis. We provide an open-source implementation of panCAKES in the Rust programming language.
format	Preprint
id	arxiv_https___arxiv_org_abs_2409_12161
institution	arXiv
publishDate	2024
record_format	arxiv
spellingShingle	Generalized compression and compressive search of large datasets Prior, Morgan E. Howard III, Thomas Light, Emily Ishaq, Najib Daniels, Noah M. Data Structures and Algorithms Information Retrieval 68P20 E.2; E.4; H.3.2; H.3.3; H.1.1 The Big Data explosion has necessitated the development of search algorithms that scale sub-linearly in time and memory. While compression algorithms and search algorithms do exist independently, few algorithms offer both, and those which do are domain-specific. We present panCAKES, a novel approach to compressive search, i.e., a way to perform $k$-NN and $ρ$-NN search on compressed data while only decompressing a small, relevant, portion of the data. panCAKES assumes the manifold hypothesis and leverages the low-dimensional structure of the data to compress and search it efficiently. panCAKES is generic over any distance function for which the distance between two points is proportional to the memory cost of storing an encoding of one in terms of the other. This property holds for many widely-used distance functions, e.g. string edit distances (Levenshtein, Needleman-Wunsch, etc.) and set dissimilarity measures (Jaccard, Dice, etc.). We benchmark panCAKES on a variety of datasets, including genomic, proteomic, and set data. We compare compression ratios to gzip, and search performance between the compressed and uncompressed versions of the same dataset. panCAKES achieves compression ratios close to those of gzip, while offering sub-linear time performance for $k$-NN and $ρ$-NN search. We conclude that panCAKES is an efficient, general-purpose algorithm for exact compressive search on large datasets that obey the manifold hypothesis. We provide an open-source implementation of panCAKES in the Rust programming language.
title	Generalized compression and compressive search of large datasets
topic	Data Structures and Algorithms Information Retrieval 68P20 E.2; E.4; H.3.2; H.3.3; H.1.1
url	https://arxiv.org/abs/2409.12161