Photo de Daniel Lemire

est professeur titulaire en informatique. Il s'intéresse particulièrement aux techniques d'indexation en science des données. Par exemple, il a travaillé sur les index bitmap et la compression des listes d'entiers. Il s'intéresse aussi au design des bases de données et aux algorithmes probabilistes (par ex. le hachage universel). Il aime à poser un regard critique sur l'utilisation des technologies.

Ses travaux sur les index bitmap sont utilisés par des sociétés comme eBay, Facebook, LinkedIn et Netflix dans leurs entrepôts de données, au sein des  plate-formes de mégadonnées telles que Apache Hive, Druid, Apache Spark, Netflix Atlas, LinkedIn Pinot  et Apache Kylin. L'outil de contrôle de version Git utilise aussi ces mêmes techniques pour accélérer les requêtes. Ses techniques de compression d'index sont utilisées pour la recherche biomédicale. Certaines de ses techniques ont été adoptées par Apache Lucene, le moteur de recherche derrière des sites comme Wikipedia ou des plateformes comme Solr et Elastic. Un de ses techniques de hachage a été adoptée par Tensorflow de Google pour améliorer les performances. Son algorithme Slope One est une référence dans le domaine des systèmes de recommandation.

Il a écrit plus de 25 articles dans des revues scientifiques et un cinquantaine de publications arbitrées. Il détient des subventions de recherche depuis plus de 15 ans. Il sert régulièrement d'expert au sein des comités de programme de conférences prestigieuses (par ex., ACM CIKM, ACM WSDM, ACM SIGIR, ACM RecSys). 

Il s'investit beaucoup dans le développement de librairies logicielles open source. Il programme régulièrement en C, C++, Java, JavaScript, Python, Swift et Go. Il travaille principalement dans des environnements open source (par ex. Linux).

Il est un avide utilisateur des médias sociaux : son blogue compte plusieurs milliers de lecteurs. Il fut l'un des premiers utilisateurs de twitter: @lemire.

Quelques publications récentes

Supervision d'étudiants

Daniel Lemire supervise régulièrement des étudiants aux trois cycles universitaires. Il travaille principalement avec des étudiants qui adorent programmer et qui préfèrent les environnements open source (par ex., Linux). Plusieurs de ses étudiants aux cycles supérieurs contribuent à des projets open source sur des sites comme GitHub.

Il a récemment supervisé les thèses de doctorat des étudiants suivants : 

  • Jing Li, diplômée d'un doctorat en informatique (diplômée en 2016);
  • Samy Chambi, diplômé d'un doctorat en informatique (diplômé en 2016);
  • Hazel Webb, diplômée d'un doctorat en informatique  (diplômée en 2010).

Formation

  • Postdoctorat (Institut de génie biomédical)
  • Doctorat en mathématiques de l’ingénieur (Université de Montréal et École Polytechnique)
  • Maîtrise en mathématiques (University of Toronto)
  • Baccalauréat en mathématique (University of Toronto), avec mention «High Distinction»

Champs d'expertise

  • Science des données
  • Techniques d'indexation
  • Performance du logiciel

Enseignement

Projets de recherche

Programme de recherche

Nous cherchons à accélérer les techniques d'indexation, soit au sein des moteurs de recherche ou des bases de données relationnelles. Dans le cadre de ces travaux, on exploite les développements récents au sein des processeurs courants. En particulier, nous cherchons à bénéficier pleinement de la vectorisation de ces processeurs. Un aspect important de cette recherche est la compression des index, qu'ils s'agisse d'index inversés, d'arbre B ou d'index bitmaps. L'objectif étant de faire en sorte que les index puissent résider en mémoire le plus possible. On souhaite compresser et décompresser les données à très grande vitesse en mémoire. On souhaite aussi grandement accélérer les opérations courantes comme l'intersection ou l'union.

Subventions actuelles

  • Faster Compressed Indexes On Next ­Generation Hardware (détails à paraître)
  • Data reordering for better compression in databases (Subvention à la découverte du CRSNG, 2012-2017) : 140,000$
  • Adapting forests to global change through high-tech field monitoring, transplantation experiments and simulation models (Fond des leaders avec N. Bélanger [responsable] et E. Filotas): 800,000$

Publications et communications

Articles de revues avec comité de lecture

Muła, Wojciech; Kurz, Nathan et Lemire, Daniel (sous presse). Faster population counts using AVX2 instructions. Computer Journal. https://doi.org/10.1093/comjnl/bxx046

Lemire, Daniel et Rupp, Christoph (2017). Upscaledb: Efficient Integer-Key Compression in a Key-Value Store using SIMD Instructions. Information Systems, 66, 13–23. https://doi.org/10.1016/j.is.2017.01.002

Badia, Antonio et Lemire, Daniel (sous presse). On Desirable Semantics of Functional Dependencies over Databases with Incomplete Information. Fundamenta Informaticae.

Lemire, Daniel; Ssi-Yan-Kai, Gregory et Kaser, Owen (2016). Consistently faster and smaller compressed bitmaps with Roaring. Software: Practice and Experience, 46 (11), 1547-1569. https://doi.org/10.1002/spe.2402

Lemire, Daniel et Kaser, Owen (2016). Faster 64-bit universal hashing using carry-less multiplications. Journal of Cryptographic Engineering, 6 (3), 171-185. https://doi.org/10.1007/s13389-015-0110-5

Li, Jing; Yan, Yuhong et Lemire, Daniel (sous presse). Full Solution Indexing for top-K Web Service Composition. IEEE Transactions on Services Computing.

Chambi, Samy; Lemire, Daniel; Kaser, Owen et Godin, Robert (2016). Better bitmap performance with Roaring bitmaps. Software: Practice and Experience, 45 (5), 709–719. https://doi.org/10.1002/spe.2325

Chambi, Samy; Lemire, Daniel et Godin, Robert (2016). Vers de meilleures performances avec des Roaring bitmaps. Technique et Science Informatiques, 35 (3), 335-355.

Kaser, Owen et Lemire, Daniel (2016). Compressed bitmap indexes: beyond unions and intersections. Software: Practice and Experience, 46 (2). https://doi.org/10.1002/spe.2289

Ivanchykhin, Dmytro; Ignatchenko, Sergey et Lemire, Daniel (sous presse). Regular and almost universal hashing: an efficient implementation. Software: Practice and Experience.

Badia, Antonio et Lemire, Daniel (2015). Functional dependencies with null markers. Computer Journal, 58 (5), 1160-1168. https://doi.org/10.1093/comjnl/bxu039

Zhao, Wayne Xin; Zhang, Xudong; Lemire, Daniel; Shan, Dongdong; Nie, Jian-Yun; Yan, Hongfei et Wen, Ji-Rong (2015). A General SIMD-based Approach to Accelerating Compression Algorithms. ACM Transactions on Information Systems, 33 (3). https://doi.org/10.1145/2735629

Zhu, Xiaodan; Turney, Peter; Lemire, Daniel et Vellino, Andre (2015). Measuring academic influence: Not all citations are equal. Journal of the Association for Information Science and Technology, 66 (2), 408-427. https://doi.org/10.1002/asi.23179

Lemire, Daniel et Boytsov, Leonid (2015). Decoding billions of integers per second through vectorization. Software: Practice & Experience, 45 (1), 1-29. https://doi.org/10.1002/spe.2203

Crainiceanu, Adina et Lemire, Daniel (2015). Bloofi : Multidimensional Bloom Filters. Information Systems, 54. https://doi.org/10.1016/j.is.2015.01.002

Lemire, Daniel et Kaser, Owen (2014). Strongly universal string hashing is fast. Computer Journal, 57 (11), 1624-1638. https://doi.org/10.1093/comjnl/bxt070

Webb, Hazel; Lemire, Daniel et Kaser, Owen (2013). Diamond dicing. Data & Knowledge Engineering, 86. https://doi.org/10.1016/j.datak.2013.01.001

Prekopcsák, Zoltán et Lemire, Daniel (2012). Time Series Classification by Class-Specific Mahalanobis Distance Measures. Advances in Data Analysis and Classification, 6 (3). https://doi.org/10.1007/s11634-012-0110-6

Lemire, Daniel; Kaser, Owen et Gutarra, Eduardo (2012). Reordering rows for better compression: Beyond the lexicographic order. ACM Transactions on Database Systems, 37 (3). https://doi.org/10.1145/2338626.2338627

Neylon, Cameron; Aerts, Jan; Brown, C. Titus; Coles, Simon J.; Hatton, Les; Lemire, Daniel; Millman, K. Jarrod; Murray-Rust, Peter; Perez, Fernando; Saunders, Neil; Shah, Nigam; Smith, Arfon; Varoquaux, Gaël et Willighagen, Egon (2012). Changing computational research. The challenges ahead. Source Code for Biology and Medicine, 7 (2). https://doi.org/10.1186/1751-0473-7-2

Lemire, Daniel (2012). The universality of iterated hashing over variable-length strings. Discrete Applied Mathematic, 160 (4-5), 604–617. https://doi.org/10.1016/j.dam.2011.11.009

Lemire, Daniel et Kaser, Owen (2011). Reordering Columns for Smaller Indexes. Information Sciences, 181 (12), 2550–2570. https://doi.org/10.1016/j.ins.2011.02.002

Badia, Antonio et Lemire, Daniel (2011). A call to arms: Revisiting database design. SIGMOD Record, 40 (3), 61-69. https://doi.org/10.1145/2070736.2070750

Lemire, Daniel et Kaser, Owen (2010). Recursive n-gram hashing is pairwise independent, at best. Computer Speech & Language, 24 (4), 698-710. https://doi.org/10.1016/j.csl.2009.12.001

Lemire, Daniel; Kaser, Owen et Aouiche, Kamel (2010). Sorting improves word-aligned bitmap indexes. Data & Knowledge Engineering, 69 (1), 3-28. https://doi.org/10.1016/j.datak.2009.08.006

Lemire, Daniel (2009). Faster retrieval with a two-pass dynamic-time-warping lower bound. Pattern Recognition, 42 (9). https://doi.org/10.1016/j.patcog.2008.11.030

Lemire, Daniel; Brooks, Martin et Yan, Yuhong (2009). An optimal linear time algorithm for quasi-monotonic segmentation. International Journal of Computer Mathematics, 86 (7). https://doi.org/10.1080/00207160701694153

Lemire, Daniel et Kaser, Owen (2008). Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays. ACM Transactions on Algorithms, 4 (1), 1-31. https://doi.org/10.1145/1328911.1328925

Kaser, Owen et Lemire, Daniel (2006). Attribute value reordering for efficient hybrid OLAP. Information Systems, 176 (16), 2304-2336. https://doi.org/10.1016/j.ins.2005.09.005

Lemire, Daniel (2006). Streaming maximum-minimum filter using no more than three comparisons per element. Nordic Journal of Computing, 13 (4), 328-339.

Lemire, Daniel (2005). Scale and translation invariant collaborative filtering systems. Information Retrieval, 8 (1), 129-150. https://doi.org/10.1023/B:INRT.0000048492.50961.a6

Lemire, Daniel; Boley, Harold; McGrath, Sean et Ball, Marc (2005). Collaborative filtering and inference rules for context-aware learning object recommendation. Interactive Technology and Smart Education, 2 (3). https://doi.org/10.1108/17415650580000043

Dubuc, Serge; Lemire, Daniel et Merrien, Jean-Louis (2001). Fourier analysis of 2-point Hermite interpolatory subdivision schemes. Journal of Fourier Analysis and Applications, 7 (5), 532-552. https://doi.org/10.1007/BF02511225

Chapitres de livres

Noël, Sylvie et Lemire, Daniel (2010). On the Challenges of Collaborative Data Processing. Dans Foster, Jonathan (dir.), Collaborative Information Behaviour. User Engagement and Communication Sharing (p. 55-71). IGI Global : IGI Global.

Aouiche, Kamel; Lemire, Daniel et Godin, Robert (2009). Web 2.0 OLAP: From data cubes to tag clouds. Dans Web Information Systems and Technologies. 4th International Conference, WEBIST 2008, Funchal, Madeira, Portugal, May 4-7, 2008, Revised Selected Papers. Springer, coll. « Lecture Notes in Business Information Processing », vol. 18.

Communications dans des actes avec comité de lecture

Chambi, Samy; Lemire, Daniel et Godin, Robert (2016). Nouveaux modèles d’index bitmap compressés à 64 bits. Dans Actes des 12es journées francophones sur les Entrepôts de Données et l'Analyse en Ligne.

Chambi, Samy; Lemire, Daniel; Godin, Robert; Boukhalfa, Kamel; Allen, Charles et Yang, Fangjin (2016). Optimizing Druid with Roaring bitmaps. Dans Proceedings of the 20th International Database Engineering & Applications Symposium. ACM. ISBN 978-1-4503-4118-9 https://doi.org/10.1145/2938503.2938515

Li, Jing; Yan, Yuhong et Lemire, Daniel (sous presse). Scaling up Web Service Composition with the Skyline Operator. Dans IEEE International Conference on Web Services 2016.

Ruer, Perrine; Gouin-Vallerand, Charles; Zhang, Le; Lemire, Daniel et Vallières, Évelyne F. (2015). An analysis tool for the contextual information from field experiments on driving fatigue. Dans Proceeding of the Ninth International and Interdisciplinary Conference on Modeling and Using Context (Context 2015). Springer, coll. « LNAI ».

Li, Jing; Yan, Yuhong et Lemire, Daniel (2015). A web service composition method based on compact K2-trees. Dans IEEE International Conference on Services Computing (p. 403 - 410). IEEE. ISBN 978-1-4673-7280-0 https://doi.org/10.1109/SCC.2015.62

Plaisance, Jeff; Kurz, Nathan et Lemire, Daniel (2015). Vectorized VByte Decoding. Dans First International Symposium on Web Algorithms.

Chambi, Samy; Lemire, Daniel et Godin, Robert (2014). Roaring bitmap : nouveau modèle de compression bitmap. Dans Actes des 10e journées francophones sur les Entrepôts de Données et l'Analyse en Ligne.

Li, Jing; Yan, Yuhong et Lemire, Daniel (2014). Full Solution Indexing Using Database for QoS-aware Web Service Composition. Dans IEEE International Conference on Services Computing (p. 99 - 106). IEEE. ISBN 978-1-4799-5065-2 https://doi.org/10.1109/SCC.2014.22

Lemire, Daniel et Vellino, Andre (2011). Extracting, Transforming and Archiving Scientific Data. Dans Proceedings of the Fourth Workshop on Very Large Digital Libraries. DELOS Association for Digital Libraries.

Kaser, Owen; Lemire, Daniel et Aouiche, Kamel (2008). Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes. Dans Proceedings of the 11th ACM International Workshop on Data Warehousing and OLAP. ACM.

Webb, Hazel; Kaser, Owen et Lemire, Daniel (2008). Pruning Attributes From Data Cubes with Diamond Dicing. Dans IDEAS '08 Proceedings of the 2008 international symposium on Database engineering & applications. ACM International Conference Proceeding Series.

Aouiche, Kamel; Lemire, Daniel et Godin, Robert (2008). Collaborative OLAP with Tag Clouds: Web 2.0 OLAP Formalism and Experimental Evaluation. Dans Proceedings of WEBIST 2008. Portugal : Institute for Systems and Technologies of Information, Control and Communication.

Aouiche, Kamel et Lemire, Daniel (2007). A Comparison of Five Probabilistic View-Size Estimation Techniques in OLAP. Dans Proceedings of the 10th International Workshop on Data Warehousing and OLAP. ACM.

Aouiche, Kamel et Lemire, Daniel (2007). Unasssuming View-Size Estimation Techniques in OLAP. Dans Proceedings of the 9th International Conference on Enterprise Information Systems. Portugal : INSTICC.

Kaser, Owen et Lemire, Daniel (2007). Removing Manually-Generated Boilerplate from Electronic Texts: Experiments with Project Gutenberg e-Books. Dans Spencer, Bruce; Story, Margaret-Ann et Stewart, Darlene (dir.), Proceedings of the 2007 Conference of the Center for Advanced Studies on Collaborative Research (CASCON '07). Riverton, NJ, É.-U. : IBM.

Kaser, Owen et Lemire, Daniel (2007). Tag-Cloud Drawing: Algorithms for Cloud Visualization. Dans Proceedings of the Tagging and Metadata for Social Information Organization Workshop, 16th International World Wide Web Conference (WWW 2007). Banff, Canada : IW3C2.

Kucerovsky, Dan et Lemire, Daniel (2007). Monotonicity Analysis over Chains and Curves. Dans Curve and surface fitting: Avignon 2006 (p. 180-190). Brentwood, TN, É.-U. : Nashboro Press.

Kaser, Owen; Lemire, Daniel et Keith, Steven (2006). The LitOLAP Project: Data Warehousing with Literature. Dans Proceedings of the 2006 CaSTA Conference. University of New Brunswick.

Brooks, Martin; Yan, Yuhong et Lemire, Daniel (2005). Scale-Based Monotonicity Analysis in Qualitative Modelling with Flat Segments. Dans Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Edinburgh, UK : IJICAI.

Lemire, Daniel (2005). A Better Alternative to Piecewise Linear Time Series Segmentation. Dans Apte, Chid; Skillicorn, David; Liu, Bing et Parthasara, Srinivasan (dir.), Proceedings of the 2007 SIAM International Conference on Data Mining (SDM'07) (p. 545-550). Minneapolis, Minnesota : SIAM. https://doi.org/10.1137/1.9781611972771.59

Lemire, Daniel; Brooks, Martin et Yan, Yuhong (2005). An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation. Dans Han, Jiawei; Wah, Benjamin W.; Vijay, Raghavan; Wu, Xindong et Rastogi, Rajeev (dir.), Proceedings of the Fifth IEEE International Conference on Data Mining (ICDM-05) (p. 709-712). Piscataway, NJ : IEEE. https://doi.org/10.1109/ICDM.2005.25

Lemire, Daniel et Maclachlan, Anna (2005). Slope One Predictors for Online Rating-Based Collaborative Filtering. Dans Kargupta, Hillol; Srivastava, Jaideep; Kamath, Chandrika et Goodman, Arnold (dir.), Proceedings of the 2005 SIAM International Conference on Data Mining (SDM'05) (p. 471-475). Newport Beach, CA : SIAM.

Anderson, Michelle; Ball, Marcel; Boley, Harold; Greene, Stephen; Howse, Nancy; Lemire, Daniel et McGrath, Sean (2003). RACOFI: A Rule-Applying Collaborative Filtering System. Dans IEEE/WIC COLA 2003.

Kaser, Owen et Lemire, Daniel (2003). Attribute Value Reordering for Efficient Hybrid OLAP. Dans Rizzi, Stefano et Song, Il-Yeol (dir.), Proceedings of the ACM Sixth International Workshop on Data Warehousing and OLAP (p. 1-8). New Orleans, LA : ACM.

Lemire, Daniel (2003). A Family of 4-Point Dyadic Multistep Subdivision Schemes. Dans Cohen, Albert; Merrien, Jean-Louis et Scumaker, Larry L. (dir.), Curves and Surface Fitting: Saint-Malo 2002 (p. 259-268). Brentwood, TN, USA : Nashboro Press.

Lemire, Daniel (2002). Wavelet-Based Relative Prefix Sum Methods for Range Sum Queries in Data Cubes. Dans Stewart, Darlene A. et Johnson, J. Howard (dir.), Proceedings of the 2002 Conference of the Center for Advanced Studies on Collaborative Research (CASCON '02) (p. 6). Riverton, NJ, USA : IBM.

Communications avec comité de lecture

Aouiche, Kamel; Lemire, Daniel et Kaser, Owen (juin 2008). Tri de la table de faits et compression des index bitmaps avec alignement sur les mots. Communication présentée aux 24ièmes journées 'Bases de Données Avancées'.

Prix et distinctions

Prix industriel

  • Google Open Source Peer Bonus Program (2012)

Communications primées

  • Best student paper award (IEEE SCC 2014)
  • Best paper award (CASCON 2002)

Service à la collectivité

conférences publiques

COMITÉ DE PROGRAMME DE CONFÉRENCES INTERNATIONALES

  • ACM Conference on Information and Knowledge Management (ACM CIKM)
  • ACM Conference on Web Search and Data Mining (ACM WSDM)
  • ACM Conference on Information Retrieval (ACM SIGIR)
  • ACM Conference on Recommender Systems (ACM RecSys)
  • ACM/IEEE Joint Conference on Digital Libraries (JCDL)

ORGANISMES SUBVENTIONNAIRES

  • FQRNT: comité d'évaluation 03F (informatique théorique) depuis 2007.
  • FQRNT: comité d'évaluation 309 (subvention d'équipe en informatique) depuis 2006.
  • CRSNG: comité d'évaluation du programme de subventions d’outils et d’instruments de recherche dans les sciences informatiques

ÉVALUATEUR EXTERNE (DOCTORAT)

  • Khaled Dehdouh de Lyon 2 (2015) - dirigé par Omar Boussaid.
  • Martin Leginus de l'Université Aalborg (2015) - dirigé par Peter Dolog.
  • Ahmad Taleb de l'Université Concordia (2011) - dirigé par Todd Eavis.

ÉVALUATEUR EXTERNE (PROMOTION)

  • Sabine Loudcher Rabaseda de l'Université Lyon2 - dossier d'habilitation.
  • Jason Sawin de l'Université of St. Thomas.
  • Amer Nizar AbuAli de la Philadelphia University.
  • Jinan Fiaidhi de Lakehead University.