An exact and an approximate version of the algorithm.

Abstract

Keyword-based search in rich, multidimensional datasets helps with many new applications and tools. In this search, we consider objects marked with keywords to be included in the vector space. For these data sets, we look at queries that require small groups of points to satisfy a certain set of keywords. We propose a new method called ProMiSH (Multi-Purpose Projection and Diagnosis) that uses random index structures and random fragmentation, and achieves high scalability and acceleration. We provide an accurate and approximate version of the algorithm. Our experimental results show on real and synthetic data sets that ProMiSH has up to 60 times the acceleration on modern tree-based techniques.