DBSCAN algorithm can identify clusters of any shape, because of the way in which it works. This algorithm finds core samples of high density and expands clusters from them. It also marks points that lie alone in low-density regions as outliers, so it's useful to identify noise as well.

Ideally, the algorithm should use the same shapes of the clusters as they are in the problem field. I work in a high-dimensional semantic space and can't guess the shape of the "natural" cluster, but they definitely are not rectangular. So for me there are two options: balls or ellipsoids. Notice that the balls are more efficient in terms of computer memory. I need to store just N coordinates of the center and the radius. While for an ellipsoid I need to store N vectors of N elements each, which makes N^2. For a cluster in 1000-dimensional space I need to store 1M float values. This is not feasible.

Dear Oliver,

I feel that your expression can be a reason for cluster shapes. Still i am waiting for some resources in this connection.

Thanking you,

B. K. Tripathy