In this paper, we propose an indexing approach for camera-based document image retrieval and spotting systems. The proposed approach is based on randomized hierarchical trees without storing database vector points in the memory. To construct the trees, k-means-based clustering is used for splitting the data points of every non-leaf node into 2 distinct groups. Instead of using the entire dimensions, only a small number of dimensions is chosen randomly and they are combined with the dimension with the highest variance which is computed along all dimensions and the maximum variance is selected. Experimental results demonstrate the usefulness of the proposed approach for limited memory situations, as the proposed random trees could approximately reach the accuracy of state-of-the-art methods on Tobacco dataset without storing the database descriptors in memory.