In this paper, we formulate a dual clustering problem in spatial data streams. A spatial data stream consists of data points with attributes in the optimization and geography domains. We aim at partitioning these objects into disjoint clusters such that at each time window (1) objects in the same cluster satisfy the transitively r-connected relation in the optimization and geography domains, and (2) the number of clusters is as minimal as possible. We propose a Hierarchical-Based Clustering algorithm (HBC). Specifically, objects are represented as a graph structure, called RGraph, where each node represents an object and edges indicate their similarity relationships. In light of RGraph, algorithm HBC iteratively merges clusters. Experimental results show the performance of the algorithm.