DARS: Diversity and Distribution-Aware Region Search

Recent years have seen the rapid development of Location Based Services (LBSs). Many users of these services are making use of them to, for example, plan trips, find houses or explore their surroundings. In this paper we introduce a novel problem called the diversity and distribution-aware region search (DARS) problem. In particular, DARS aims to find regions of size \(a \times b\) where the number of different categories is maximized such that objects of different categories are not too scattered from each other and objects of the same category are within reasonable distance (which is a tunable parameter to cater for different users’ needs). We propose several methods to tackle the problem. We first design a sweepline based method, and then design various techniques to further improve the efficiency. We have conducted extensive experiments over real datasets and demonstrate both the usefulness and the efficiency of our methods.