An Adaptive Nearest Keyword Search Using Multi-Scale Hashing and Projection Technique in Spatial Databases

Abstract

The Nearest keyword set (referred to as NKS) queries on text-rich multi-dimensional datasets. An NKS query is a set of user-provided keywords, and the result of the query may include k sets of data points each of which contains all the query NKS queries are useful for many applications, such as photo-sharing in social networks, graph pattern search, geo location search in GIS systems1 and so on.NKS queries are useful for graph pattern search, where labeled graphs are embedded in a high dimensional for scalability. In this case, a search for a sub graph with a set of specified labels can be answered by an NKS query in the embedded space.  NKS queries can also reveal geographic patterns. GIS can characterize a region by a high-dimensional set of attributes, such as pressure, humidity, and soil types. Meanwhile, these regions can also be tagged with information such as diseases. An epidemiologist can formulate NKS queries to discover patterns by finding a set of similar regions with all the diseases of her interest. we develop an exact ProMiSH (referred to as ProMiSH-E) that always retrieves the optimal top-k results, and an approximate ProMiSH (referred to as ProMiSH-A) that is more efficient in terms of time and space, and is able to obtain near-optimal results in practice.. Based on this index, ProMiSH-A which searches near-optimal results with better efficiency. ProMiSH is faster than state-of-the-art tree-based techniques, with multiple orders of magnitude performance improvement.