Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

REFERENCES

• 1: Accurate Estimation of the Cost of Spatial Selections, Proceedings of the 16th International Conference on Data Engineering, p.123, February 28-March 03, 2000
• 2: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Richard Beigel , Egemen Tanin, The Geometry of Browsing, Proceedings of the Third Latin American Symposium on Theoretical Informatics, p.331-340, April 20-24, 1998
• 4: Rong-chii Duh , Martin Fürer, Approximation of k-set cover by semi-local optimization, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.256-264, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258599]
• 5: M. J. Egenhofer, A formal definition of binary topological relationships, 3rd International Conference, FODO 1989 on Foundations of Data Organization and Algorithms, p.457-472, July 1989, Paris, France
• 6: Egenhofer, M. J. and Herring, J. R. 1994. Categorizing binary topological relations between regions, lines, and points in geographic databases. In The 9-Intersection: Formalism and Its Use for Natural-Language Spatial Predicates. National Center for Geographic Information and Analysis, Report 94-1, M. J. Egenhofer, D. M. Mark, and J. R. Herring, Eds.
• 7: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 8: Fleischer, R., Golin, M. J., and Zhang, Y. 2004. Online maintenance of k-medians and k-covers on a line. In Proceedings of SWAT'04 (Humlebaek, Denmark, July 8--10). 102--113.
• 9: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 10: Garofalakis, M. N. and Gehrke, J. 2002. Querying and mining data streams: You only get one look. In Proceedings of the Symposium on Very Large Data Bases (VLDB'02) (Hong Kong, Aug. 20--23).
• 11: Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. 2002. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the Symposium on Very Large Data Bases (VLDB'02). Hong Kong, August 20--23, 454--465.
• 12: Greene, S., Tanin, E., Plaisant, C., Shneiderman, B., Olsen, L., Major, G., and Johns, S. 1999. The end of zero-hit queries: Query previews for NASA's global change master directory. Int. J. Dig. Lib. 2, 2-3, 79--90.
• 13: Grigni, M., Papadias, D., and Papadimitriou, C. H. 1995. Topological inference. In Proceedings of the IJCAI (1). (Montréal, Qué. Aug. 20--25). 901--907.
• 14: Marios Hadjieleftheriou , George Kollios , Vassilis J. Tsotras, Performance evaluation of spatio-temporal selectivity estimation techniques, Proceedings of the 15th international conference on Scientific and statistical database management, p.202-211, July 09-11, 2003, Cambridge, MA [doi>10.1109/SSDM.2003.1214981]
• 15: Harary, F. 1969. Graph Theory. Addison-Wesley, Reading, MA.
• 16: Hassin, R. and Tamir, A. 1991. Improved complexity bounds for location problems on the real line. Oper. Res. Lett. 10, 395--402.
• 17: Ching-Tien Ho , Rakesh Agrawal , Nimrod Megiddo , Ramakrishnan Srikant, Range queries in OLAP data cubes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.73-88, May 11-15, 1997, Tucson, Arizona, United States
• 18: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 19: Analyzing Range Queries on Spatial Data, Proceedings of the 16th International Conference on Data Engineering, p.525, February 28-March 03, 2000
• 20: Lin, X., Liu, Q., Yuan, Y., and Zhou, X. 2003. Multiscale histograms: Summarizing topological relations in large spatial datasets. In Proceedings of the Symposium on Very Large Data Bases (VLDB'03) (Berlin, Germany, Sept. 9--12). 814--825.
• 21: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 22: Ming-Ling Lo , Chinya V. Ravishankar, Spatial hash-joins, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.247-258, June 04-06, 1996, Montreal, Quebec, Canada
• 23: Nikos Mamoulis , Dimitris Papadias, Integration of spatial join algorithms for processing multiple inputs, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.1-12, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 24: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 25: Micali, S. and Vazirani, V. V. 1980. An o(√|V||E|) algorithm for finding maximum matching in general graphs. In Proceedings of the Symposium on Foundations of Computer Science (FOCS'80) (Syracuse, NY, Oct. 17--27). IEEE Computer Society Press, Los Alamitos, CA.
• 26: Jignesh M. Patel , David J. DeWitt, Partition based spatial-merge join, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.259-270, June 04-06, 1996, Montreal, Quebec, Canada
• 27: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• 28: Exploring Spatial Datasets with Histograms, Proceedings of the 18th International Conference on Data Engineering, p.93, February 26-March 01, 2002
• 29: Chengyu Sun , Divyakant Agrawal , Amr El Abbadi, Selectivity Estimation for Spatial Joins with Geometric Selections, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.609-626, March 25-27, 2002
• 30: Alexander S. Szalay , Peter Z. Kunszt , Ani Thakar , Jim Gray , Don Slutz , Robert J. Brunner, Designing and mining multi-terabyte astronomy archives: the Sloan Digital Sky Survey, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.451-462, May 15-18, 2000, Dallas, Texas, United States
• 31: Yufei Tao , George Kollios , Jeffrey Considine , Feifei Li , Dimitris Papadias, Spatio-Temporal Aggregation Using Sketches, Proceedings of the 20th International Conference on Data Engineering, p.214, March 30-April 02, 2004
• 32: Tao, Y., Sun, J., and Papadias, D. 2003. Selectivity estimation for predictive spatio-temporal queries. In Proceedings of the International Conference on Data Engineering (ICDE'03) (Bangalore, India, Mar. 5--8). 417--428.
• 33: TIGER. 2000. Tiger/line files. Technical report, U.S. Census Bureau, Washington, DC.
• 34: Zipf, G. K. 1949. Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley, Reading, MA.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Histograms, spatial query processing and optimization