{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:34:30Z","timestamp":1774686870125,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T00:00:00Z","timestamp":1618444800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. Emerg. Technol. Comput. Syst."],"published-print":{"date-parts":[[2021,4,30]]},"abstract":"<jats:p>We present fast implementations of linear interpolation operators for piecewise linear functions and multi-dimensional look-up tables. These operators are common for efficient transformations in image processing and are the core operations needed for lattice models like deep lattice networks, a popular machine learning function class for interpretable, shape-constrained machine learning. We present new strategies for an efficient compiler-based solution using MLIR to accelerate linear interpolation. For real-world machine-learned multi-layer lattice models that use multidimensional linear interpolation, we show these strategies run 5-10\u00d7 faster on a standard CPU compared to an optimized C++ interpreter implementation.<\/jats:p>","DOI":"10.1145\/3423184","type":"journal-article","created":{"date-parts":[[2021,4,15]],"date-time":"2021-04-15T11:04:42Z","timestamp":1618484682000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Fast Linear Interpolation"],"prefix":"10.1145","volume":"17","author":[{"given":"Nathan","family":"Zhang","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin","family":"Canini","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sean","family":"Silva","sequence":"additional","affiliation":[{"name":"Google, Mountain View CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maya","family":"Gupta","sequence":"additional","affiliation":[{"name":"Google Research, Mountain View CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,4,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1969.222758"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1561\/9781601987570"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1468075.1468121"},{"key":"e_1_2_1_4_1","first-page":"2927","article-title":"Fast and flexible monotonic functions with ensembles of lattices","volume":"29","author":"Canini K.","year":"2016","unstructured":"K. Canini , A. Cotter , M. M. Fard , M. R. Gupta , and J. Pfeifer . 2016 . Fast and flexible monotonic functions with ensembles of lattices . Adv. Neural Info. Process. Syst. 29 , 1 (2016), 2927 -- 2935 . K. Canini, A. Cotter, M. M. Fard, M. R. Gupta, and J. Pfeifer. 2016. Fast and flexible monotonic functions with ensembles of lattices. Adv. Neural Info. Process. Syst. 29, 1 (2016), 2927--2935.","journal-title":"Adv. Neural Info. Process. Syst."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of OSDI. USENIX, 578--594","author":"Chen Tianqi","year":"2018","unstructured":"Tianqi Chen , Thierry Moreau , Ziheng Jiang , Lianmin Zheng , Eddie Yan , Haichen Shen , Meghan Cowan , Leyuan Wang , Yuwei Hu , Luis Ceze , Carlos Guestrin , and Arvind Krishnamurthy . 2018 . TVM: An automated end-to-end optimizing compiler for deep learning . In Proceedings of OSDI. USENIX, 578--594 . Retrieved from https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/chen. Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. 2018. TVM: An automated end-to-end optimizing compiler for deep learning. In Proceedings of OSDI. USENIX, 578--594. Retrieved from https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/chen."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of ICTAI. IEEE Computer Society, 186--193","author":"Codish M.","unstructured":"M. Codish , L. Cruz-Filipe , M. Frank , and P. Schneider-Kamp . 2014. Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten) . In Proceedings of ICTAI. IEEE Computer Society, 186--193 . M. Codish, L. Cruz-Filipe, M. Frank, and P. Schneider-Kamp. 2014. Twenty-five comparators is optimal when sorting nine inputs (and twenty-nine for ten). In Proceedings of ICTAI. IEEE Computer Society, 186--193."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of MLR, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.)","volume":"97","author":"Cotter Andrew","year":"2019","unstructured":"Andrew Cotter , Maya Gupta , Heinrich Jiang , Erez Louidor , James Muller , Tamann Narayan , Serena Wang , and Tao Zhu . 2019 . Shape constraints for set functions . In Proceedings of MLR, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.) , Vol. 97 . 1388--1396. Retrieved from http:\/\/proceedings.mlr.press\/v97\/cotter19a.html. Andrew Cotter, Maya Gupta, Heinrich Jiang, Erez Louidor, James Muller, Tamann Narayan, Serena Wang, and Tao Zhu. 2019. Shape constraints for set functions. In Proceedings of MLR, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. 1388--1396. Retrieved from http:\/\/proceedings.mlr.press\/v97\/cotter19a.html."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S2046165800001544"},{"key":"e_1_2_1_9_1","unstructured":"A. Fog. 2018. Retrieved from https:\/\/www.agner.org\/optimize\/microarchitecture.pdf.  A. Fog. 2018. Retrieved from https:\/\/www.agner.org\/optimize\/microarchitecture.pdf."},{"key":"e_1_2_1_10_1","volume-title":"Advances in Neural Information Processing Systems","volume":"22","author":"Garcia Eric","year":"2009","unstructured":"Eric Garcia and Maya Gupta . 2009 . Lattice regression . In Advances in Neural Information Processing Systems , vol. 22 , Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (Eds.). Curran Associates, 594--602. Retrieved from http:\/\/papers.nips.cc\/paper\/3694-lattice-regression.pdf. Eric Garcia and Maya Gupta. 2009. Lattice regression. In Advances in Neural Information Processing Systems, vol. 22, Y. Bengio, D. Schuurmans, J. D. Lafferty, C. K. I. Williams, and A. Culotta (Eds.). Curran Associates, 594--602. Retrieved from http:\/\/papers.nips.cc\/paper\/3694-lattice-regression.pdf."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIP.2012.2200902"},{"key":"e_1_2_1_12_1","first-page":"6835","article-title":"Diminishing returns shape constraints for interpretability and regularization","volume":"31","author":"Gupta M. R.","year":"2018","unstructured":"M. R. Gupta , D. Bahri , A. Cotter , and K. Canini . 2018 . Diminishing returns shape constraints for interpretability and regularization . Adv. Neural Info. Process. Syst. 31 , 1 (2018), 6835 -- 6845 . M. R. Gupta, D. Bahri, A. Cotter, and K. Canini. 2018. Diminishing returns shape constraints for interpretability and regularization. Adv. Neural Info. Process. Syst. 31, 1 (2018), 6835--6845.","journal-title":"Adv. Neural Info. Process. Syst."},{"key":"e_1_2_1_13_1","first-page":"1","article-title":"Monotonic calibrated interpolated look-up tables","volume":"17","author":"Gupta M. R.","year":"2016","unstructured":"M. R. Gupta , A. Cotter , J. Pfeifer , K. Voevodski , K. Canini , A. Mangylov , W. Moczydlowski , and A. Van Esbroeck . 2016 . Monotonic calibrated interpolated look-up tables . J. Mach. Learn. Res. 17 , 109 (2016), 1 -- 47 . M. R. Gupta, A. Cotter, J. Pfeifer, K. Voevodski, K. Canini, A. Mangylov, W. Moczydlowski, and A. Van Esbroeck. 2016. Monotonic calibrated interpolated look-up tables. J. Mach. Learn. Res. 17, 109 (2016), 1--47.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of ICML","author":"Gupta M. R.","year":"2020","unstructured":"M. R. Gupta , E. Louidor , N. Morioka , T. Narayan , and S. Zhao . 2020. Multi-dimensional shape constraints . In Proceedings of ICML ( 2020 ). M. R. Gupta, E. Louidor, N. Morioka, T. Narayan, and S. Zhao. 2020. Multi-dimensional shape constraints. In Proceedings of ICML (2020)."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of CVPR.770--778","author":"He K.","year":"2016","unstructured":"K. He , X. Zhang , S. Ren , and J. Sun . 2016. Deep residual learning for image recognition . In Proceedings of CVPR.770--778 . DOI:https:\/\/doi.org\/10.1109\/CVPR. 2016 .90 10.1109\/CVPR.2016.90 K. He, X. Zhang, S. Ren, and J. Sun. 2016. Deep residual learning for image recognition. In Proceedings of CVPR.770--778. DOI:https:\/\/doi.org\/10.1109\/CVPR.2016.90"},{"key":"e_1_2_1_16_1","unstructured":"A. Howard and T. Jebara. 2007. Learning monotonic transformations for classification. In Advances in Neural Information Processing Systems. MIT Press.  A. Howard and T. Jebara. 2007. Learning monotonic transformations for classification. In Advances in Neural Information Processing Systems. MIT Press."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning (ICML\u201918)","author":"Jia Zhihao","year":"2018","unstructured":"Zhihao Jia , Sina Lin , Charles R. Qi , and Alex Aiken . 2018 . Exploring hidden dimensions in parallelizing convolutional neural networks . In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918) . 2279--2288. Retrieved from http:\/\/proceedings.mlr.press\/v80\/jia18a.html. Zhihao Jia, Sina Lin, Charles R. Qi, and Alex Aiken. 2018. Exploring hidden dimensions in parallelizing convolutional neural networks. In Proceedings of the 35th International Conference on Machine Learning (ICML\u201918). 2279--2288. Retrieved from http:\/\/proceedings.mlr.press\/v80\/jia18a.html."},{"key":"e_1_2_1_18_1","unstructured":"P. Khuong. 2012. Binary Search *Eliminates* Branch Mis-predictions. Retrieved from https:\/\/www.pvk.ca\/Blog\/2012\/07\/03\/binary-search-star-eliminates-star-branch-mispredictions\/.  P. Khuong. 2012. Binary Search *Eliminates* Branch Mis-predictions. Retrieved from https:\/\/www.pvk.ca\/Blog\/2012\/07\/03\/binary-search-star-eliminates-star-branch-mispredictions\/."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of SIGMOD\u201918","author":"Kraska T.","unstructured":"T. Kraska , A. Beutel , E. H. Chi , J. Dean , and N. Polyzotis . 2018. The case for learned index structures . In Proceedings of SIGMOD\u201918 . T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis. 2018. The case for learned index structures. In Proceedings of SIGMOD\u201918."},{"key":"e_1_2_1_20_1","volume-title":"MLIR: A Compiler Infrastructure for the End of Moore\u2019s Law.","author":"Lattner Chris","year":"2020","unstructured":"Chris Lattner , Mehdi Amini , Uday Bondhugula , Albert Cohen , Andy Davis , Jacques Pienaar , River Riddle , Tatiana Shpeisman , Nicolas Vasilache , and Oleksandr Zinenko . 2020 . MLIR: A Compiler Infrastructure for the End of Moore\u2019s Law. Retrieved from https:\/\/arxiv:cs.PL\/2002.11054. Chris Lattner, Mehdi Amini, Uday Bondhugula, Albert Cohen, Andy Davis, Jacques Pienaar, River Riddle, Tatiana Shpeisman, Nicolas Vasilache, and Oleksandr Zinenko. 2020. MLIR: A Compiler Infrastructure for the End of Moore\u2019s Law. Retrieved from https:\/\/arxiv:cs.PL\/2002.11054."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/645533.656505"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.73596"},{"key":"e_1_2_1_24_1","volume-title":"Practical Mathematics","author":"Perry J.","unstructured":"J. Perry . 1899. Practical Mathematics . Wiley and Sons . J. Perry. 1899. Practical Mathematics. Wiley and Sons."},{"key":"e_1_2_1_25_1","volume-title":"Glow: Graph lowering compiler techniques for neural networks.","author":"Rotem N.","year":"2018","unstructured":"N. Rotem , J. Fix , S. Abdulrasool , S. Deng , R. Dzhabarov , J. Hegeman , R. Levenstein , B. Maher , N. Satish , J. Olesen , J. Park , A. Rakhov , and M. Smelyanskiy . 2018 . Glow: Graph lowering compiler techniques for neural networks. Retrieved from http:\/\/arxiv.org\/abs\/1805.00907. N. Rotem, J. Fix, S. Abdulrasool, S. Deng, R. Dzhabarov, J. Hegeman, R. Levenstein, B. Maher, N. Satish, J. Olesen, J. Park, A. Rakhov, and M. Smelyanskiy. 2018. Glow: Graph lowering compiler techniques for neural networks. Retrieved from http:\/\/arxiv.org\/abs\/1805.00907."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.707591"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0370164600029837"},{"key":"e_1_2_1_28_1","unstructured":"G. Sharma and R. Bala. 2002. Digital Color Imaging Handbook. CRC Press New York.  G. Sharma and R. Bala. 2002. Digital Color Imaging Handbook. CRC Press New York."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of ICML.","author":"Sujeeth Arvind K.","unstructured":"Arvind K. Sujeeth , HyoukJoong Lee , Kevin J. Brown , Hassan Chafi , Michael Wu , Anand R. Atreya , Kunle Olukotun, Tiark Rompf, and Martin Odersky. 2011. OptiML: An implicitly parallel domain-specific language for machine learning . In Proceedings of ICML. Arvind K. Sujeeth, HyoukJoong Lee, Kevin J. Brown, Hassan Chafi, Michael Wu, Anand R. Atreya, Kunle Olukotun, Tiark Rompf, and Martin Odersky. 2011. OptiML: An implicitly parallel domain-specific language for machine learning. In Proceedings of ICML."},{"key":"e_1_2_1_30_1","unstructured":"TensorFlow Blog. 2020. TensorFlow Lattice: Flexible Controlled and Interpretable ML. Retrieved from https:\/\/blog.tensorflow.org\/2020\/02\/tensorflow-lattice-flexible-controlled-and-interpretable-ML.html.  TensorFlow Blog. 2020. TensorFlow Lattice: Flexible Controlled and Interpretable ML. Retrieved from https:\/\/blog.tensorflow.org\/2020\/02\/tensorflow-lattice-flexible-controlled-and-interpretable-ML.html."},{"key":"e_1_2_1_31_1","unstructured":"N. Vasilache O. Zinenko T. Theodoridis P. Goyal Z. DeVito W. S. Moses S. Verdoolaege A. Adams and A. Cohen. 2018. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. Retrieved from http:\/\/arxiv.org\/abs\/1802.04730.  N. Vasilache O. Zinenko T. Theodoridis P. Goyal Z. DeVito W. S. Moses S. Verdoolaege A. Adams and A. Cohen. 2018. Tensor comprehensions: Framework-agnostic high-performance machine learning abstractions. Retrieved from http:\/\/arxiv.org\/abs\/1802.04730."},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of AIStats.","author":"Wang S.","unstructured":"S. Wang and M. R. Gupta . 2020. Deontological ethics by monotonicity shape constraints . In Proceedings of AIStats. S. Wang and M. R. Gupta. 2020. Deontological ethics by monotonicity shape constraints. In Proceedings of AIStats."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1988-0917826-0"},{"key":"e_1_2_1_34_1","first-page":"2985","article-title":"Deep lattice networks and partial monotonic functions","volume":"30","author":"You S.","year":"2017","unstructured":"S. You , K. Canini , D. Ding , J. Pfeifer , and M. R. Gupta . 2017 . Deep lattice networks and partial monotonic functions . Adv. Neural Info. Process. Syst. 30 , 1 (2017), 2985 -- 2993 . S. You, K. Canini, D. Ding, J. Pfeifer, and M. R. Gupta. 2017. Deep lattice networks and partial monotonic functions. Adv. Neural Info. Process. Syst. 30, 1 (2017), 2985--2993.","journal-title":"Adv. Neural Info. Process. Syst."}],"container-title":["ACM Journal on Emerging Technologies in Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3423184","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3423184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:57Z","timestamp":1750195497000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3423184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,15]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,4,30]]}},"alternative-id":["10.1145\/3423184"],"URL":"https:\/\/doi.org\/10.1145\/3423184","relation":{},"ISSN":["1550-4832","1550-4840"],"issn-type":[{"value":"1550-4832","type":"print"},{"value":"1550-4840","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4,15]]},"assertion":[{"value":"2020-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}