Pairwise Expansion: A New Topdown Search for mCK Queries Problem over Spatial Web

摘要

This paper focuses on the problem of m-Closest Keywords (mCK) queries over spatial web objects. An mCK query is to find the optimal set of objects (object-set) in the sense that they are the spatially-closest records and satisfy m user-given keywords. We propose a new approach called Pairwise Expansion to find an exact solution of mCK queries based on topdown search of an on-the-fly quad-tree. This approach first enumerates object-pairs in a topdown way, then picks up each 'closer' object-pair and expands it into candidate object-sets. Experimental results show that this approach is more efficient than existing topdown search strategies and applicable for real spatial web data.