Memory-Efficient Sequential Pattern Mining with Hybrid Tries

• URL: http://arxiv.org/abs/2202.06834v3
• Date: Sat, 27 Jul 2024 17:22:06 GMT
• Title: Memory-Efficient Sequential Pattern Mining with Hybrid Tries
• Authors: Amin Hosseininasab, Willem-Jan van Hoeve, Andre A. Cire,
• Abstract summary: This paper develops a memory-efficient approach for Sequential Pattern Mining (SPM) For large data sets, our algorithm stands out as the only capable SPM approach within 256GB of system memory, potentially saving 1.7TB in memory consumption.
• Score: 3.1747517745997014
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper develops a memory-efficient approach for Sequential Pattern Mining (SPM), a fundamental topic in knowledge discovery that faces a well-known memory bottleneck for large data sets. Our methodology involves a novel hybrid trie data structure that exploits recurring patterns to compactly store the data set in memory; and a corresponding mining algorithm designed to effectively extract patterns from this compact representation. Numerical results on small to medium-sized real-life test instances show an average improvement of 85% in memory consumption and 49% in computation time compared to the state of the art. For large data sets, our algorithm stands out as the only capable SPM approach within 256GB of system memory, potentially saving 1.7TB in memory consumption.

Related papers

• Efficient Beam Search for Large Language Models Using Trie-Based Decoding [10.302821791274129]
  We introduce a novel parallel decoding method that addresses the memory inefficiency of batch-based beam search. By sharing a single cache among all beams that share the same prefix, the proposed method not only reduces memory consumption dramatically but also enables parallel decoding across all branches. This innovative use of a prefix tree offers an efficient alternative for beam search, achieving significant memory savings while preserving inference speed, making it particularly well-suited for memory-constrained environments or large-scale model deployments.
  arXiv  Detail & Related papers  (2025-01-31T16:22:36Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• An Efficient Procedure for Computing Bayesian Network Structure Learning [0.9208007322096532]
  We propose a globally optimal Bayesian network structure discovery algorithm based on a progressively leveled scoring approach. Experimental results indicate that our method, when using only memory, not only reduces peak memory usage but also improves computational efficiency.
  arXiv  Detail & Related papers  (2024-07-24T07:59:18Z)
• Associative Memories in the Feature Space [68.1903319310263]
  We propose a class of memory models that only stores low-dimensional semantic embeddings, and uses them to retrieve similar, but not identical, memories. We demonstrate a proof of concept of this method on a simple task on the MNIST dataset.
  arXiv  Detail & Related papers  (2024-02-16T16:37:48Z)
• MCUNetV2: Memory-Efficient Patch-based Inference for Tiny Deep Learning [72.80896338009579]
  We find that the memory bottleneck is due to the imbalanced memory distribution in convolutional neural network (CNN) designs. We propose a generic patch-by-patch inference scheduling, which significantly cuts down the peak memory. We automate the process with neural architecture search to jointly optimize the neural architecture and inference scheduling, leading to MCUNetV2.
  arXiv  Detail & Related papers  (2021-10-28T17:58:45Z)
• Generative Optimization Networks for Memory Efficient Data Generation [11.452816167207937]
  We propose a novel framework called generative optimization networks (GON) that is similar to GANs, but does not use a generator. GONs use a single discriminator network and run optimization in the input space to generate new data samples, achieving an effective compromise between training time and memory consumption. We show that our framework gives up to 32% higher detection F1 scores and 58% lower memory consumption, with only 5% higher training overheads compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2021-10-06T16:54:33Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Semantically Constrained Memory Allocation (SCMA) for Embedding in Efficient Recommendation Systems [27.419109620575313]
  A key challenge for deep learning models is to work with millions of categorical classes or tokens. We propose a novel formulation of memory shared embedding, where memory is shared in proportion to the overlap in semantic information. We demonstrate a significant reduction in the memory footprint while maintaining performance.
  arXiv  Detail & Related papers  (2021-02-24T19:55:49Z)
• Memformer: A Memory-Augmented Transformer for Sequence Modeling [55.780849185884996]
  We present Memformer, an efficient neural network for sequence modeling. Our model achieves linear time complexity and constant memory space complexity when processing long sequences.
  arXiv  Detail & Related papers  (2020-10-14T09:03:36Z)
• Reinforcing Short-Length Hashing [61.75883795807109]
  Existing methods have poor performance in retrieval using an extremely short-length hash code. In this study, we propose a novel reinforcing short-length hashing (RSLH) In this proposed RSLH, mutual reconstruction between the hash representation and semantic labels is performed to preserve the semantic information. Experiments on three large-scale image benchmarks demonstrate the superior performance of RSLH under various short-length hashing scenarios.
  arXiv  Detail & Related papers  (2020-04-24T02:23:52Z)
• IMAC: In-memory multi-bit Multiplication andACcumulation in 6T SRAM Array [5.29958909018578]
  In-memory computing aims at embedding some aspects of computations inside the memory array. We present a novel in-memory multiplication followed by accumulation operation capable of performing parallel dot products within 6T array. The proposed system is 6.24x better in energy consumption and 9.42x better in delay.
  arXiv  Detail & Related papers  (2020-03-27T17:43:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.