Canonical bases first appeared as Kazhdan-Lusztig bases in the study of Hecke
algebras which can be thought of as "q-deformations" of symmetric groups (or,
more generally, Coxeter groups). These are distinguished bases of an algebra
with prescribed invariance properties when q is replaced by its inverse. They
are also triangular with respect to some natural initial basis. Such bases
play an important role in algebra since Lusztig constructed them in quantum
groups in early 90-ies using geometric methods.