AI Paper Atlas

Research map / Learning theory and algorithms / Clustering

A New Burrows Wheeler Transform Markov Distance

Edward Raff, Charles Nicholas, Mark McLean

AAAI 2020 · Learning theory and algorithms › Clustering · approach: Clustering approximation algorithms · 13 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
Represent each sequence with BWT-derived Markov transition features and cluster in Euclidean spacemalware family clustering · Kaggle Bytes, Kaggle ASM, Drebin APK, Drebin TAR, and VS20FV-Measure: Kaggle Bytes k=10·C: 0.414 -> 0.546; Kaggle ASM k=10·C: 0.531 -> 0.562; Drebin APK k=10·C: 0.326 -> 0.412; Drebin TAR k=Improved
Use BWMD instead of LZJD for nearest-neighbor malware classification1-NN malware classification · Kaggle Bytes and Kaggle ASMbalanced accuracy: Kaggle Bytes: 97.9 (1.4) -> 96.4 (2.2); Kaggle ASM: 97.1 (1.7) -> 97.0 (1.8)Hurt
Use BWMD instead of LZJD for nearest-neighbor malware classification1-NN malware classification · Drebin APK and Drebin TARbalanced accuracy: Drebin APK: 81.0 (4.0) -> 55.3 (4.4); Drebin TAR: 87.9 (2.1) -> 76.3 (3.6)Hurt
Use BWMD instead of LZJD for large-corpus nearest-neighbor searchEMBER retrieval · EMBERAUC: 99.7% -> 98.3%Hurt
Index BWMD Euclidean embeddings with DCI rather than brute-force searchBWMD · EMBER test setquery time: 834× faster than BWMD with a brute force searchImproved
Use BWMD rather than EBWT for clustering variable-length genomic scaffold sequencessingle-link DNA clustering · Genomic scaffold DNAclustering quality: 28 minutes -> 47 secondsImproved
Use BWMD rather than LZJD for malware clusteringmalware family clustering · VS20F training setclustering time: 7.76 hours -> 27 minutesImproved
Ignore sequence length in the distance by comparing normalized BWT transition distributionsBWMD · u=a^n1 and v=a^n2, n2>n1distance: bwmd(u,v)=0Improved
Use BWMD transition distributions to compare sequences with disjoint alphabetsBWMD · Sequences with no shared charactersdistance: bwmd(u,v)=1Improved

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy