The multidimensional k-NN (k nearest neighbors) query problem arises in a large variety of database applications, including information retrieval, natural language processing, and data mining. To solve it efficiently, database needs an indexing structure supporting this kind of search. However, exact solution is hardly feasible in multidimensional space. In this paper we describe and analyze an indexing technique for approximate solution of k-NN problem. Construction of the indexing tree is based on clustering. Construction of hash indexing is based on s-stable distributions. Indices are implemented on top of high-performance industrial DBMS.