Nearest Keyword Set Search in Multi-dimensional Datasets
This addresses the need for scalable keyword-based search in text-rich multi-dimensional datasets, which is incremental as it builds on existing methods but offers substantial performance improvements.
The paper tackles the problem of efficiently finding the tightest groups of points that satisfy a given set of keywords in multi-dimensional datasets, proposing ProMiSH, which achieves a speedup of over four orders of magnitude compared to state-of-the-art tree-based techniques and scales linearly with dataset size, dimension, query size, and result size.
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.