Splay Tree

A Self Balancing Binary Search Tree with the unusual property that recently accessed elements are easier to access.

Self Balancing Binary Search Tree

A binary search tree that balances itself automatically and attempts to keep its height small at all times.

Finger Search Trees

The goal is to leave certain auxiliary pointers in the data structure so that a search for an item helps the subsequent search.

Estimating Set Disjointness ...

... is a classical, hard problem in Communication Complexity !!

Randomized Algos In Data Streaming

The randomized algorithms used in Data Streaming applications, at least in the papers I have read are Monte Carlo algorithms. This is because they need not always produce a correct solution even allowing for approximation bounds. There is always a possibility epsilon of an error. Hence the Yao's minimax conjecture does not apply to these. Hence it is consistent, that, while deterministic algorithms produce a linear lower bound on space requirements these algorithms can indeed give a sublinear bound on space.

Permanent Matrix

Here ..

Norm of a Vector

http://mathworld.wolfram.com/VectorNorm.html

Planar Metric

A metric d is said to be planar if it is the metric induced by the weighted planar graph.