IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v252y2016i3p985-994.html

An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters

Author

Listed:
  • Yang, Xinan
  • Vernitski, Alexei
  • Carrea, Laura

Abstract

Bloom filters are a data structure for storing data in a compressed form. They offer excellent space and time efficiency at the cost of some loss of accuracy (so-called lossy compression). This work presents a yes–no Bloom filter, which as a data structure consisting of two parts: the yes-filter which is a standard Bloom filter and the no-filter which is another Bloom filter whose purpose is to represent those objects that were recognized incorrectly by the yes-filter (that is, to recognize the false positives of the yes-filter). By querying the no-filter after an object has been recognized by the yes-filter, we get a chance of rejecting it, which improves the accuracy of data recognition in comparison with the standard Bloom filter of the same total length. A further increase in accuracy is possible if one chooses objects to include in the no-filter so that the no-filter recognizes as many as possible false positives but no true positives, thus producing the most accurate yes–no Bloom filter among all yes–no Bloom filters. This paper studies how optimization techniques can be used to maximize the number of false positives recognized by the no-filter, with the constraint being that it should recognize no true positives. To achieve this aim, an Integer Linear Program (ILP) is proposed for the optimal selection of false positives. In practice the problem size is normally large leading to intractable optimal solution. Considering the similarity of the ILP with the Multidimensional Knapsack Problem, an Approximate Dynamic Programming (ADP) model is developed making use of a reduced ILP for the value function approximation. Numerical results show the ADP model works best comparing with a number of heuristics as well as the CPLEX built-in solver (B&B), and this is what can be recommended for use in yes–no Bloom filters. In a wider context of the study of lossy compression algorithms, our research is an example showing how the arsenal of optimization methods can be applied to improving the accuracy of compressed data.

Suggested Citation

  • Yang, Xinan & Vernitski, Alexei & Carrea, Laura, 2016. "An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters," European Journal of Operational Research, Elsevier, vol. 252(3), pages 985-994.
  • Handle: RePEc:eee:ejores:v:252:y:2016:i:3:p:985-994
    DOI: 10.1016/j.ejor.2016.01.042
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221716000874
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2016.01.042?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to

    for a different version of it.

    References listed on IDEAS

    as
    1. James H. Lorie & Leonard J. Savage, 1955. "Three Problems in Rationing Capital," The Journal of Business, University of Chicago Press, vol. 28, pages 229-229.
    2. Grothey, Andreas & Yang, Xinan, 2012. "Approximate dynamic programming with Bézier Curves/Surfaces for Top-percentile Traffic Routing," European Journal of Operational Research, Elsevier, vol. 218(3), pages 698-707.
    3. Dimitris Bertsimas & Ramazan Demir, 2002. "An Approximate Dynamic Programming Approach to Multidimensional Knapsack Problems," Management Science, INFORMS, vol. 48(4), pages 550-565, April.
    4. Dan Zhang & Daniel Adelman, 2009. "An Approximate Dynamic Programming Approach to Network Revenue Management with Customer Choice," Transportation Science, INFORMS, vol. 43(3), pages 381-394, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. José García & José Lemus-Romani & Francisco Altimiras & Broderick Crawford & Ricardo Soto & Marcelo Becerra-Rozas & Paola Moraga & Alex Paz Becerra & Alvaro Peña Fritz & Jose-Miguel Rubio & Gino Astor, 2021. "A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 9(20), pages 1-19, October.
    2. Yanhong Feng & Haizhong An & Xiangyun Gao, 2018. "The Importance of Transfer Function in Solving Set-Union Knapsack Problem Based on Discrete Moth Search Algorithm," Mathematics, MDPI, vol. 7(1), pages 1-25, December.
    3. José García & Andres Leiva-Araos & Broderick Crawford & Ricardo Soto & Hernan Pinto, 2023. "Exploring Initialization Strategies for Metaheuristic Optimization: Case Study of the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 11(12), pages 1-20, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dragos Florin Ciocan & Vivek Farias, 2012. "Model Predictive Control for Dynamic Resource Allocation," Mathematics of Operations Research, INFORMS, vol. 37(3), pages 501-525, August.
    2. Sabah Bushaj & İ. Esra Büyüktahtakın, 2024. "A K-means Supported Reinforcement Learning Framework to Multi-dimensional Knapsack," Journal of Global Optimization, Springer, vol. 89(3), pages 655-685, July.
    3. Tobin, Roger L., 1999. "A fast interactive solution method for large capital expenditure selection problems," European Journal of Operational Research, Elsevier, vol. 116(1), pages 1-15, July.
    4. Jing Wu & Lijie Su & Gongshu Wang & Yang Yang, 2024. "Approximated Dynamic Programming for Production and Inventory Planning Problem in Cold Rolling Process of Steel Production," Mathematics, MDPI, vol. 12(24), pages 1-17, December.
    5. Chen, Shijie & Rahman, Md Hishamur & Marković, Nikola & Siddiqui, Muhammad Imran Younus & Mohebbi, Matthew & Sun, Yanshuo, 2024. "Schedule negotiation with ADA paratransit riders under value of time uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 184(C).
    6. Deng, Qichen & Santos, Bruno F., 2022. "Lookahead approximate dynamic programming for stochastic aircraft maintenance check scheduling optimization," European Journal of Operational Research, Elsevier, vol. 299(3), pages 814-833.
    7. Hanafi, Said & Freville, Arnaud, 1998. "An efficient tabu search approach for the 0-1 multidimensional knapsack problem," European Journal of Operational Research, Elsevier, vol. 106(2-3), pages 659-675, April.
    8. Thomas W. M. Vossen & Dan Zhang, 2015. "Reductions of Approximate Linear Programs for Network Revenue Management," Operations Research, INFORMS, vol. 63(6), pages 1352-1371, December.
    9. David Simchi-Levi & Rui Sun & Huanan Zhang, 2022. "Online Learning and Optimization for Revenue Management Problems with Add-on Discounts," Management Science, INFORMS, vol. 68(10), pages 7402-7421, October.
    10. Guang Li & Paat Rusmevichientong & Huseyin Topaloglu, 2015. "The d -Level Nested Logit Model: Assortment and Price Optimization Problems," Operations Research, INFORMS, vol. 63(2), pages 325-342, April.
    11. Gino Favero & Gherardo Piacitelli, 2024. "Irr and equivalence of cash-flow streams, loans, and portfolios of bonds," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 47(2), pages 379-399, December.
    12. E A Silver, 2004. "An overview of heuristic solution methods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(9), pages 936-956, September.
    13. Ruxian Wang & Maqbool Dada & Ozge Sahin, 2019. "Pricing Ancillary Service Subscriptions," Management Science, INFORMS, vol. 65(10), pages 4712-4732, October.
    14. D. Babusiaux, 1988. "Financing investment and calculations of profitability [Financement des investissements et calculs de rentabilité]," Working Papers hal-01534450, HAL.
    15. Marc Bertonèche & Herwig Langohr, 1977. "Le choix des investissements en situation de rationnement du capital : comparaison des solutions fournies par différents modèles théoriques," Revue Économique, Programme National Persée, vol. 28(5), pages 730-764.
    16. Osborne, Michael J., 2010. "A resolution to the NPV-IRR debate?," The Quarterly Review of Economics and Finance, Elsevier, vol. 50(2), pages 234-239, May.
    17. Chevalier, Philippe & Lamas, Alejandro & Lu, Liang & Mlinar, Tanja, 2015. "Revenue management for operations with urgent orders," European Journal of Operational Research, Elsevier, vol. 240(2), pages 476-487.
    18. Bertazzi, Luca & Bosco, Adamo & Laganà, Demetrio, 2015. "Managing stochastic demand in an Inventory Routing Problem with transportation procurement," Omega, Elsevier, vol. 56(C), pages 112-121.
    19. Christiane Barz & Jochen Gönsch & Davina Rauhaus & Siqi He, 2025. "Dynamic pricing with (extra) seat reservations under the nested logit model," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 47(4), pages 1133-1179, December.
    20. Gustavo Vulcano & Garrett van Ryzin & Wassim Chaar, 2010. "OM Practice--Choice-Based Revenue Management: An Empirical Study of Estimation and Optimization," Manufacturing & Service Operations Management, INFORMS, vol. 12(3), pages 371-392, February.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:252:y:2016:i:3:p:985-994. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.