Keonwoo Kim  Younghoon Kim

spatial data processing finding k-point embedding minimum box divide and conquer time complexity analysis

There has been a recent spate in the usage of mobile device equipped GPS sensors, such as smart phones. This trend enables the posting of geo-tagged messages (i.e., multimedia messages with GPS locations) on social media such as Twitter and Facebook, and the volume of such spatial data is rapidly growing. However, the relationships between the location and content of messages are not always explicitly shown in such geo-tagged messages. Thus, the need arises to reorganize search results to find the relationship between keywords and the spatial distribution of messages. We find the smallest minimum bounding rectangle (MBR) that embedding k or more points in order to find the most dense rectangle of data, and it can be usefully used in the location search system. In this paper, we suggest efficient algorithms to discover a group of 2-Dimensional spatial data with a close distance, such as MBR. The efficiency of our proposed algorithms with synthetic and real data sets is confirmed experimentally.