Alejandro López-Ortiz

Professor

Professor Alejandro (Alex) López-Ortiz passed away on Sunday, March 12, 2017, at age 49. Please see the in memoriam for our tribute to him and details about his personal and academic life.

His faculty profile has been preserved for historical interest. Please also see his personal research website.


photo of Professor Alejandro López-Ortiz
Professor López-Ortiz’s research focused on practical applications of advanced algorithms. He made contributions in information retrieval, Internet routing, paging, and multicore computing.

In information retrieval Professor López-Ortiz defined novel algorithms for computing the primitives that drive search engines. He was also interested in compression schemes that support search operations. Data compression schemes economize storage needs while at the same time reduce access times to secondary storage.

On the topic of Internet protocols and applications Alex’s research focused on three problems: (1) routing, (2) caching and (3) stream statistics and measuring the network. To illustrate, a key problem for large service providers is to maintain reliable traffic statistics at the core of the network. These massive data sets require ingenious and extremely efficient algorithms given the speeds at which packets are exchanged. In this research he developed efficient deterministic and statistical sampling methods, with applications that extend also to large data streams in databases (iceberg queries).

In a more recent series of contributions he made breakthroughs in the theoretical understanding of the superiority of paging techniques such as Least-Recently-Used (LRU) by introducing better techniques for modelling and study of online algorithms. He also explored the design and analysis of algorithms for multicore architectures.

Major Awards

Cheriton Faculty Fellow (2010–13)

Industrial and Sabbatical Experience

After receiving his PhD in 1996, Professor López-Ortiz spent two years at OpenText, first as a research scientist and then as a dual research scientist and leader of the search engine development team. In 1998 he took a position at the University of New Brunswick, where he was the director of the Internet Computing Laboratory and an assistant professor in the Faculty of Computer Science.

In 2000 he moved to Seattle to become Director of Core Research of Internap Network Services, the eighth largest ISP in North America. There he led a team of researchers in successfully developing and implementing an automated quality-of-service–based routing system.

He has been a faculty member at Waterloo since 2001.

As a consultant, Professor López-Ortiz has experience in managing the software process from discovery to product delivery, implementing best practices and helping avoid pitfalls. He also has experience in taking time critical applications and improving performance by factors between 10 and 1000 using general algorithm techniques.

Representative Publications

Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono and A. López-Ortiz. The Cost of Cache-Oblivious Searching, Algorithmica, 2011.

Spyros Angelopoulos, A. López-Ortiz. Interruptible algorithms for Multi-Problem Solving. Proceedings of 21st International Joint Conference on Artificial Intelligence (IJCAI), pp. 380--386, 2009.

Spyros Angelopoulos, Reza Dorrigiv, and A. López-Ortiz. On the Separation and Equivalence of Paging Strategies. In Proceedings of 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 229-237, 2007.

A. López-Ortiz, S. Angelopoulos, and A. Hamel. Optimal Scheduling of Contract Algorithms for Any-time Problems. Proceedings of 21st National Conference on Artificial Intelligence (AAAI), 2006.

A. López-Ortiz, C-G Quimper, J. Tromp, and P. van Beek. A Fast and Simple Algorithm for Bounds Consistence of the Alldifferent Constraint. Proceedings of 18th International Joint Conference on Artificial Intelligence (IJCAI), pp. 245-250, 2003.

E.D. Demaine, A. López-Ortiz, and J.I. Munro. Frequency Estimation of Internet Packet Streams with Limited Space. Proceedings of European Symposium on Algorithms, LNCS 2461, pp. 248-260, 2002.

E.D. Demaine, A. López-Ortiz, and J.I. Munro. A Linear Lower Bound on Index Size for Text Retrieval. In Journal of Algorithms, 48(1):2-15, 2003. Special issue of selected papers from the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001).

E.D. Demaine, A. López-Ortiz, and J.I. Munro. Adaptive Set Intersections, Unions and Differences. Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 743-752, 2000.