LACM-Tree: Exact Similarity Search via Learning-Enhanced Clustered Metric Trees with Distance-Table Compression Techniques - Ali Impron; Linda Sutriani; Adi Kusjani; Agung Wilis Nurcahyo; Fadhlih Girindra Putra; Muhammad Haries (Journal of Intelligent Software Systems, 2026)
Unmanned aerial vehicle (UAV)-based agricultural and forestry monitoring generates large volumes of imagery, creating a need for efficient similarity search over the high-dimensional embeddings produced by deep learning models. Classical metric indexing methods such as the M-tree, Slim-tree, and the Clustered Metric Tree (CM-tree) provide exact search with support for dynamic operations, but their performance degrades in high dimensions because the quadratic size of the pairwise distance table erodes the effective node capacity. This paper identifies distance-table compression as the key enabler for extending the CM-tree to high-dimensional embeddings. The core contribution is the Compressed Distance Table (CDT): 8-bit quantization of the pairwise distance table combined with an error-margin pruning rule that provably preserves result completeness (Theorem 1). Under an iso-memory configuration in which the per-node table budget is held constant, CDT halves the total distance-table footprint and reduces node accesses by up to 53% at n = 20,000 (and 61% on skewed data) while maintaining recall of exactly 1.000, verified by an auditing protocol that found zero unsafe prunings across more than 24,000 quantized pruning decisions. Three lighter-weight extensions—cost-oriented pivot selection (LPS), density-adaptive splitting (DAS), and multi-pivot bound tightening (MBT)—are evaluated in a controlled component-wise ablation that serves as a diagnostic study of learning-augmented metric trees. The ablation shows that these components are not additive: DAS in particular degrades performance through split-induced fragmentation, and the mechanism of this negative interaction is analyzed in detail. All results are obtained from a complete open prototype with directly measured distance computations and node accesses, on datasets up to 20,000 objects and 256 dimensions. The findings position distance-table compression—rather than learned heuristics—as the most robust path toward exact, dynamic, memory-efficient metric indexing for embedding workloads.