Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets Xuemin Lin, Qing Liu, Yidong Yuan, and Xiaofang Zhou   View Paper (PDF)   Return to Spatial Support (Session C3) Abstract Summarizing topological relations is fundamen- tal to many spatial applications including spatial query optimization. In this paper, we present sev- eral novel techniques to e ectively construct cell density based spatial histograms for range (win- dow) summarizations restricted to the four most important topological relations: contains, con- tained, overlap, and disjoint. We first present a novel framework to construct a multiscale his- togram composed of multiple Euler histograms with the guarantee of the exact summarization re- sults for aligned windows in constant time. Then we present an approximate algorithm, with the approximate ratio 19/12, to minimize the stor- age spaces of such multiscale Euler histograms, although the problem is generally NP-hard. To conform to a limited storage space where only k Euler histograms are allowed, an effective al- gorithm is presented to construct multiscale his- tograms to achieve high accuracy. Finally, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. Our extensive experiments against both synthetic and real world datasets demonstrated that the approximate mul- tiscale histogram techniques may improve the ac- curacy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique re- quires only a storage space linearly proportional to the number of cells for the real datasets. ©2004 Association for Computing Machinery