  Keyword-based search in text-rich multi-dimensional datasets facilitates many
novel applications and tools. In this paper, we consider objects that are
tagged with keywords and are embedded in a vector space. For these datasets, we
study queries that ask for the tightest groups of points satisfying a given set
of keywords. We propose a novel method called ProMiSH (Projection and Multi
Scale Hashing) that uses random projection and hash-based index structures, and
achieves high scalability and speedup. We present an exact and an approximate
version of the algorithm. Our empirical studies, both on real and synthetic
datasets, show that ProMiSH has a speedup of more than four orders over
state-of-the-art tree-based techniques. Our scalability tests on datasets of
sizes up to 10 million and dimensions up to 100 for queries having up to 9
keywords show that ProMiSH scales linearly with the dataset size, the dataset
dimension, the query size, and the result size.
