{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:42:28Z","timestamp":1750308148881,"version":"3.41.0"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2006,6,1]],"date-time":"2006-06-01T00:00:00Z","timestamp":1149120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,6]]},"abstract":"<jats:p>\n            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\n            <jats:italic>k<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.1145\/1138394.1138398","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"584-630","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Summarizing level-two topological relations in large spatial datasets"],"prefix":"10.1145","volume":"31","author":[{"given":"Xuemin","family":"Lin","sequence":"first","affiliation":[{"name":"NICTA &amp; University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qing","family":"Liu","sequence":"additional","affiliation":[{"name":"NICTA &amp; University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yidong","family":"Yuan","sequence":"additional","affiliation":[{"name":"NICTA &amp; University of New South Wales, Sydney, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaofang","family":"Zhou","sequence":"additional","affiliation":[{"name":"University of Queensland, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hongjun","family":"Lu","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,6]]},"reference":[{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'00)","author":"Aboulnaga A.","key":"e_1_2_2_1_1","unstructured":"Aboulnaga , A. and Naughton , J. F . 2000. Accurate estimation of the cost of spatial selections . In Proceedings of the International Conference on Data Engineering (ICDE'00) (Washington, DC, Feb. 28 --Mar. 3). 123--134. Aboulnaga, A. and Naughton, J. F. 2000. Accurate estimation of the cost of spatial selections. In Proceedings of the International Conference on Data Engineering (ICDE'00) (Washington, DC, Feb. 28--Mar. 3). 123--134."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304184"},{"volume-title":"Proceedings of LATIN'98 (Brazil, Apr. 20--24)","author":"Beigel R.","key":"e_1_2_2_3_1","unstructured":"Beigel , R. and Tanin , E . 1998. The geometry of browsing . In Proceedings of LATIN'98 (Brazil, Apr. 20--24) . 331--340. Beigel, R. and Tanin, E. 1998. The geometry of browsing. In Proceedings of LATIN'98 (Brazil, Apr. 20--24). 331--340."},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258599"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/68413.68447"},{"key":"e_1_2_2_6_1","volume-title":"Report 94-1, M. J","author":"Egenhofer M. J.","year":"1994","unstructured":"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. 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."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"volume-title":"Proceedings of SWAT'04","author":"Fleischer R.","key":"e_1_2_2_8_1","unstructured":"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. 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."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"volume-title":"Proceedings of the Symposium on Very Large Data Bases (VLDB'02)","author":"Garofalakis M. N.","key":"e_1_2_2_10_1","unstructured":"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). 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)."},{"volume-title":"Proceedings of the Symposium on Very Large Data Bases (VLDB'02)","author":"Gilbert A. C.","key":"e_1_2_2_11_1","unstructured":"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. 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."},{"key":"e_1_2_2_12_1","first-page":"2","article-title":"The end of zero-hit queries: Query previews for NASA's global change master directory","volume":"2","author":"Greene S.","year":"1999","unstructured":"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. 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.","journal-title":"Int. J. Dig. Lib."},{"volume-title":"Proceedings of the IJCAI (1). (Montr\u00e9al, Qu\u00e9. Aug. 20--25)","author":"Grigni M.","key":"e_1_2_2_13_1","unstructured":"Grigni , M. , Papadias , D. , and Papadimitriou , C. H . 1995. Topological inference . In Proceedings of the IJCAI (1). (Montr\u00e9al, Qu\u00e9. Aug. 20--25) . 901--907. Grigni, M., Papadias, D., and Papadimitriou, C. H. 1995. Topological inference. In Proceedings of the IJCAI (1). (Montr\u00e9al, Qu\u00e9. Aug. 20--25). 901--907."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SSDM.2003.1214981"},{"volume-title":"Graph Theory","author":"Harary F.","key":"e_1_2_2_15_1","unstructured":"Harary , F. 1969. Graph Theory . Addison-Wesley , Reading, MA . Harary, F. 1969. Graph Theory. Addison-Wesley, Reading, MA."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90041-M"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253274"},{"volume-title":"Proceedings of the Symposium on Very Large Data Bases (VLDB'98)","author":"Jagadish H. V.","key":"e_1_2_2_18_1","unstructured":"Jagadish , H. V. , Koudas , N. , Muthukrishnan , S. , Poosala , V. , Sevcik , K. C. , and Suel , T . 1998. Optimal histograms with quality guarantees . In Proceedings of the Symposium on Very Large Data Bases (VLDB'98) . (New York City, New York, August 24--27). 275--286. Jagadish, H. V., Koudas, N., Muthukrishnan, S., Poosala, V., Sevcik, K. C., and Suel, T. 1998. Optimal histograms with quality guarantees. In Proceedings of the Symposium on Very Large Data Bases (VLDB'98). (New York City, New York, August 24--27). 275--286."},{"volume-title":"Proceedings of the 2000 International Conference on Data Engineering (ICDE'00)","author":"Jin J.","key":"e_1_2_2_19_1","unstructured":"Jin , J. , An , N. , and Sivasubramaniam , A . 2000. Analyzing range queries on spatial data . In Proceedings of the 2000 International Conference on Data Engineering (ICDE'00) (Washington, DC, Feb. 28 --Mar. 3). 525--534. Jin, J., An, N., and Sivasubramaniam, A. 2000. Analyzing range queries on spatial data. In Proceedings of the 2000 International Conference on Data Engineering (ICDE'00) (Washington, DC, Feb. 28--Mar. 3). 525--534."},{"volume-title":"Proceedings of the Symposium on Very Large Data Bases (VLDB'03)","author":"Lin X.","key":"e_1_2_2_20_1","unstructured":"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. 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."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.93611"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233337"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304183"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276344"},{"volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS'80)","author":"Micali S.","key":"e_1_2_2_25_1","unstructured":"Micali , S. and Vazirani , V. V . 1980. An o(&radic;&verbar;V&verbar;&verbar;E&verbar;) 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. Micali, S. and Vazirani, V. V. 1980. An o(&radic;&verbar;V&verbar;&verbar;E&verbar;) 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."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233338"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.878999"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/645340.650239"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335439"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'04)","author":"Tao Y.","key":"e_1_2_2_31_1","unstructured":"Tao , Y. , Kollios , G. , Considine , J. , Li , F. , and Papadias , D . 2004. Spatio-temporal aggregation using sketches . In Proceedings of the International Conference on Data Engineering (ICDE'04) (Boston, MA, Mar. 30 --Apr. 2). 214--226. Tao, Y., Kollios, G., Considine, J., Li, F., and Papadias, D. 2004. Spatio-temporal aggregation using sketches. In Proceedings of the International Conference on Data Engineering (ICDE'04) (Boston, MA, Mar. 30--Apr. 2). 214--226."},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'03)","author":"Tao Y.","key":"e_1_2_2_32_1","unstructured":"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. 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."},{"volume-title":"Technical report","author":"Tiger","key":"e_1_2_2_33_1","unstructured":"TIGER. 2000. Tiger \/line files. Technical report , U.S. Census Bureau , Washington, DC . TIGER. 2000. Tiger\/line files. Technical report, U.S. Census Bureau, Washington, DC."},{"volume-title":"Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology","author":"Zipf G. K.","key":"e_1_2_2_34_1","unstructured":"Zipf , G. K. 1949. Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology . Addison-Wesley , Reading, MA . Zipf, G. K. 1949. Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley, Reading, MA."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138394.1138398","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1138394.1138398","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:41Z","timestamp":1750263521000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1138394.1138398"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,6]]},"references-count":33,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,6]]}},"alternative-id":["10.1145\/1138394.1138398"],"URL":"https:\/\/doi.org\/10.1145\/1138394.1138398","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2006,6]]},"assertion":[{"value":"2006-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}