Efficient Neural Clustering and Compression of Strings Through Approximate Euclidean Embeddings of the Levenshtein Distance
文献类型： 会议论文
第一作者： ünsal ?ztürk
作者： ünsal ?ztürk 1 ; Utku G?rkem Ertürk 1 ; Simone Casale-Brunet 2 ; Paolo Ribeca 3 ; Marco Mattavelli 1 ;
作者机构： 1.école Polytechnique Fédérale de Lausanne, Switzerland
2.Casale Brunet Consulting, Switzerland
3.Biomathematics and Statistics Scotland, Scotland, United Kingdom
关键词： Computational modeling;Data compression;Fasteners;Distortion;Transformers;Information retrieval;Distance measurement
会议名称： Data Compression Conference
主办单位：
页码： 575-575
摘要： Efficient information retrieval is a fundamental requirement in a wide array of applications, ranging from bioinformatics to database systems, and critically hinges on the complexity of an underlying distance metric. This work presents a novel approach to compute Levenshtein embeddings within Euclidean spaces by leveraging transformer-based models to obtain string embeddings with low distortion. L 2 embeddings of Levenshtein distance in 64-dimensions for sequences of length up to 256 are obtained by means of coarse-to-fine convolutions of learned 1,2,4-mer embeddings of the original string fed into transformer encoder stacks. These embeddings are shown to facilitate efficient retrieval and clustering processes, as well as to improve reference-based compression techniques by accelerating the search for similar sequences. Different type of experiments report: (1) the distortion of the embeddings, which characterizes the fidelity to the original Levenshtein metric by comparing the original distance with the estimated one between the corresponding L 2 embeddings; (2) the performance of top- k similar string retrieval, which assesses Jaccard similarity to verify the precision of the embedding space; (3) how well k -means over string embeddings approximates k -medoid clustering, with a comparative analysis against ground truth medoids, to evaluate the clustering efficiency of the embeddings; (4) the quality of reference-based compression, implemented by projecting a dataset of strings into the embedding space, computing a k-means clustering, and compressing the payload formed by concatenating cluster centers and the alignment tracebacks of each string to its assigned cluster center. Results of these preliminary experiments indicate that these embeddings (1) present low distortion for the target applications; (2) can be used to retrieve similar strings from a dataset of 10, 50, 100 random clusters with 40 strings per cluster, with inter-cluster distances of 5, 10, 25, 50; of strings of length 100 with more than 0.92 Jaccard similarity, (3) result in an "elbow" pattern in the inertia of the k-means clustering mirroring that of the k-medoid approximation with increasing k, and (4) achieve adequate reference based-compression through k-means clustering, with performance depending on the underlying distribution of the string dataset. These findings confirm that these string embeddings could be used to build tools for improving information retrieval in several domains.
分类号： tp311.56-53
- 相关文献
[1]FM-Directories: Extending the Burrows-Wheeler Transform for String Labeled Vertex Graphs of (Almost) Arbitrary Topology. Unsal Ozturk,Paolo Ribeca,Marco Mattavelli. 2023
[2]Research on Search Technology of Agricultural Information based on Geographical Perception. PAN Yuchun,WANG Jian,GAO Bingbo. 2013
[3]An Ontology-Based Information Retrieval Model for Vegetables E-commerce. Tao Teng-yang,Qian Ping,Zhao Ming. 2010
[4]Few-Shot Learning for Hyperspectral Imaging via Spectral-Spatial Feature Reconstruction. Shukai Liu,Danyi Chen,Fei Teng,Changqing Yin,Huijuan Zhang. 2024
[5]Database for storing and accessing diabetes related data in a standardized way. Máté Siket,András Nándor Kis,Lehel Dénes-Fazakas,Gy?rgy Eigner,Levente Kovács. 2023
[6]Review of Reinforcement Learning-Based Control Algorithms in Artificial Pancreas Systems for Diabetes Mellitus Management. Lehel Dénes-Fazakas,Gy?z? Dénes Fazakas,Gy?rgy Eigner,Levente Kovács,László Szilágyi. 2024
[7]CDOD-NET: A Crop Disease Object Detection Model Based on Haar Wavelet Network. Yunpeng Zhao,Shansong Wang,Qingtian Zeng,Weijian Ni,Hua Duan,Nengfu Xie,Fengjin Xiao. 2024
[8]An in Silico Investigation Into The Role of SK Channels in Failing Ventricular Myocytes. Marta Gomez,Jesus Carro,Esther Pueyo,Violeta Monasterio. 2022
[9]Inter-individual Differences in Cell Composition across the Ventricular Wall May Explain Variability in ECG Response to Serum Potassium and Calcium Variations. Hassaan A Bukhari,Carlos Sánchez,Pablo Laguna,Mark Potse,Esther Pueyo. 2022
[10]Translating Hungarian language dialects using natural language processing models. Barbara Simon,ádám Hartveg,Lehel Dénes-Fazakas,Gy?rgy Eigner,László Szilágyi. 2023
[11]Modeling the Canopy Directional Brightness Temperature Based on Path Length Distribution. Weihua Li,Guangjian Yan,Zhaoliang Li,Xihan Mu,Donghui Xie,Jean-Philippe Gastellu-Etchegorry. 2024
[12]Physiological Variations in CX43 and Fibrosis Deposition Affect Human Ventricular Electrophysiology Promoting Arrhythmia. Laura García-Mendívil,María Pérez-Zabalza,Ricardo M Rosales,José M Vallejo-Gil,Javier Fa?anás-Mastral,Manuel Vázquez-Sancho,Javier A Bellido-Morales,Alexánder S Vaca-Nú?ez,Carlos Ballester-Cuenca,Laura Ordovás,Esther Pueyo. 2023
[13]QRS Width and T-Peak to T-End Interval Are Prolonged in Preadolescents with Severe Intrauterine Growth Restriction at Birth when Compared to Controls. Freddy L Bueno–Palomeque,Konstantinos A Mountris,Nuria Ortigosa,Raquel Bailón,Bart Bijnens,Fàtima Crispi,Esther Pueyo,Ana Mincholé,Pablo Laguna. 2023
[14]Exploring the Impact of Acquisition and Reconstruction Parameters on an Imaging-Based Lung Cancer Risk Model. Luoting Zhuang,Anil Yadav,Grace H Kim,Seyed Mohammad Hossein Tabatabaei,Ashley Prosper,William Hsu. 2024
[15]Ventricular Conduction System Modeling for Electrophysiological Simulation of the Porcine Heart. Ricardo M Rosales,Konstantinos A Mountris,Manuel Doblaré,Manuel M Mazo,Esther Pueyo. 2022
[16]Exploring the conformational space of FRET biosensors for improved designs. Kevin Truong,Elizabeth Pham. 2008
[17]E-government research hotspots and the implication based on bibliometrics and Latent Dirichlet Allocation topic model. Jing Wang,Li Chen,Mo Wang,Yulun Song. 2021
[18]Automatic Tool for Pulmonary Artery Hemodynamic Assessment from 4D flow MRI. Maialen Stephens,ángel Gaitán,Rahul Kumar,Jorge Nuche,Irene Marco,Juan Delgado,Jesús Ruíz-Cabello,Karen López-Linares,Javier Bóbeda,Haizea Erostarbe. 2023
[19]Improved EEG Decoding Method Based on Spiking Neural Network for SSVEPs’ Classification. Yufan He,Yong Huang,Yan Li,Haoming Chu,Lirong Zheng,Ning Ma,Yuxiang Huan. 2023
[20]Parameter estimation and the space of random variables. Andrea De Gaetano,Giulia Aliffi. 2023
作者其他论文 更多>>
-
FM-Directories: Extending the Burrows-Wheeler Transform for String Labeled Vertex Graphs of (Almost) Arbitrary Topology
作者：Unsal Ozturk;Paolo Ribeca;Marco Mattavelli
关键词：Data compression;Transforms;Topology;Pattern matching
