More Web Proxy on the site http://driver.im/

research-article

New results on two-dimensional orthogonal range aggregation in external memory

Authors:

Yufei TaoAuthors Info & Claims

PODS '11: Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 129 - 139

https://doi.org/10.1145/1989284.1989297

Published: 13 June 2011 Publication History

Abstract

We consider the orthogonal range aggregation problem. The dataset S consists of N axis-parallel rectangles in R², each of which is associated with an integer weight. Given an axis-parallel rectangle Q and an aggregate function F, a query reports the aggregated result of the weights of the rectangles in S intersecting Q. The goal is to preprocess S into a structure such that all queries can be answered efficiently. We present indexing schemes to solve the problem in external memory when F = max (hence, min) and F = sum (hence, count and average), respectively. Our schemes have linear or near-linear space, and answer a query in O(log_BN) or O(logB²/BN) I/Os, where B is the disk block size.

References

[1]

P. Afshani, L. Arge, and K. D. Larsen. Orthogonal range reporting in three and higher dimensions. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 149--158, 2009.

Digital Library

[2]

P. Afshani, L. Arge, and K. D. Larsen. Orthogonal range reporting: query lower bounds, optimal structures in 3-d, and higher-dimensional improvements. In Symposium on Computational Geometry (SoCG), pages 240--246, 2010.

Digital Library

[3]

P. K. Agarwal, L. Arge, J. Yang, and K. Yi. I/O-efficient structures for orthogonal range-max and stabbing-max queries. In Proceedings of European Symposium on Algorithms (ESA), pages 7--18, 2003.

[4]

P. K. Agarwal, L. Arge, and K. Yi. An optimal dynamic interval stabbing-max data structure? In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 803--812, 2005.

Digital Library

[5]

A. Aggarwal and J. S. Vitter. The input/output complexity of sorting and related problems. Communications of the ACM (CACM), 31(9):1116--1127, 1988.

Digital Library

[6]

S. Alstrup, G. S. Brodal, and T. Rauhe. New data structures for orthogonal range searching. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 198--207, 2000.

Digital Library

[7]

L. Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1--24, 2003.

Digital Library

[8]

L. Arge and J. Vahrenhold. I/O-efficient dynamic planar point location. Computational Geometry, 29(2):147--162, 2004.

Digital Library

[9]

L. Arge and J. S. Vitter. Optimal dynamic interval management in external memory. In Proceedings of Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 560--569, 1996.

Digital Library

[10]

B. Chazelle. An algorithm for segment-dragging and its implementation. Algorithmica, 3:205--221, 1988.

Digital Library

[11]

B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal of Computing, 17(3):427--462, 1988.

Digital Library

[12]

H. Edelsbrunner and M. H. Overmars. On the equivalence of some rectangle problems. Information Processing Letters (IPL), 14(3):124--127, 1982.

[13]

S. Govindarajan, P. K. Agarwal, and L. Arge. CRB-tree: An efficient indexing scheme for range-aggregate queries. In Proceedings of International Conference on Database Theory (ICDT), pages 143--157, 2003.

Digital Library

[14]

H. Kaplan, E. Molad, and R. E. Tarjan. Dynamic rectangular intersection with priorities. In Proceedings of ACM Symposium on Theory of Computing (STOC), pages 639--648, 2003.

Digital Library

[15]

I. Lazaridis and S. Mehrotra. Progressive approximate aggregate queries with a multi-resolution tree structure. In Proceedings of ACM Management of Data (SIGMOD), pages 401--412, 2001.

Digital Library

[16]

D. Papadias, P. Kalnis, J. Zhang, and Y. Tao. Efficient OLAP operations in spatial data warehouses. In Proceedings of Symposium on Advances in Spatial and Temporal Databases (SSTD), pages 443--459, 2001.

Digital Library

[17]

B. Salzberg and V. J. Tsotras. Comparison of access methods for time-evolving data. ACM Computing Surveys, 31(2):158--221, 1999.

Digital Library

[18]

Y. Tao and D. Papadias. Range aggregate processing in spatial databases. IEEE Transactions on Knowledge and Data Engineering (TKDE), 16(12):1555--1570, 2004.

Digital Library

[19]

J. S. Vitter. Algorithms and data structures for external memory. Foundation and Trends in Theoretical Computer Science, 2(4):305--474, 2006.

Digital Library

[20]

D. Zhang, A. Markowetz, V. J. Tsotras, D. Gunopulos, and B. Seeger. On computing temporal aggregates with range predicates. ACM Transactions on Database Systems (TODS), 33(2), 2008.

Digital Library

[21]

D. Zhang and V. J. Tsotras. Optimizing spatial min/max aggregations. The VLDB Journal, 14(2):170--181, 2005.

Digital Library

Cited By

Potluri ABhattu SKumar NSubramanyam R(2022)Enhanced-Sweep: Communication Cost Efficient Top-K Best Region SearchArabian Journal for Science and Engineering10.1007/s13369-022-07084-x48:2(2121-2132)Online publication date: 12-Aug-2022
https://doi.org/10.1007/s13369-022-07084-x
Mas-ud Hussain MMostafiz MMahmud STrajcevski GEunus Ali M(2020)Conditional MaxRS Query for Evolving Spatial DataFrontiers in Big Data10.3389/fdata.2020.000203Online publication date: 19-Jun-2020
https://doi.org/10.3389/fdata.2020.00020
Liu SLiu QBao Z(2020)DARS: Diversity and Distribution-Aware Region SearchDatabase Systems for Advanced Applications10.1007/978-3-030-59419-0_13(204-220)Online publication date: 22-Sep-2020
https://doi.org/10.1007/978-3-030-59419-0_13
Show More Cited By

Index Terms

New results on two-dimensional orthogonal range aggregation in external memory
1. Information systems
  1. Information retrieval
    1. Document representation
    2. Search engine architectures and scalability
      1. Search engine indexing
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching
SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry

In this paper, we develop improved cache-oblivious data structures for two- and three-sided planar orthogonal range searching. Our main result is an optimal static structure for two-sided range searching that uses linear space and supports queries in O(...
Fast Range Searching with Delaunay Triangulations

This paper studies the idea of answering range searching queries using simple data structures. The only data structure we need is the Delaunay Triangulation of the input points. The idea is to first locate a vertex of the (arbitrary) query polygon {\cal ...
Orthogonal range searching on the RAM, revisited
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometry

We present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '11: Proceedings of the thirtieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2011

332 pages

ISBN:9781450306607

DOI:10.1145/1989284

General Chair:
Maurizio Lenzerini
Sapienza University of Rome, Italy
,
Program Chair:
Thomas Schwentick
TU Dortmund University, Germany

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '11

Sponsor:

SIGMOD

SIGMOD/PODS '11: International Conference on Management of Data

June 13 - 15, 2011

Athens, Greece

Acceptance Rates

PODS '11 Paper Acceptance Rate 25 of 113 submissions, 22%;

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
192
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Potluri ABhattu SKumar NSubramanyam R(2022)Enhanced-Sweep: Communication Cost Efficient Top-K Best Region SearchArabian Journal for Science and Engineering10.1007/s13369-022-07084-x48:2(2121-2132)Online publication date: 12-Aug-2022
https://doi.org/10.1007/s13369-022-07084-x
Mas-ud Hussain MMostafiz MMahmud STrajcevski GEunus Ali M(2020)Conditional MaxRS Query for Evolving Spatial DataFrontiers in Big Data10.3389/fdata.2020.000203Online publication date: 19-Jun-2020
https://doi.org/10.3389/fdata.2020.00020
Liu SLiu QBao Z(2020)DARS: Diversity and Distribution-Aware Region SearchDatabase Systems for Advanced Applications10.1007/978-3-030-59419-0_13(204-220)Online publication date: 22-Sep-2020
https://doi.org/10.1007/978-3-030-59419-0_13
Adu-Gyamfi DZhou FZhang FKibiwott KDela Tattrah V(2019)Real-time Monitoring of Mobile User using Trajectory Data Mining2019 IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT)10.1109/ICECCT.2019.8869336(1-8)Online publication date: Feb-2019
https://doi.org/10.1109/ICECCT.2019.8869336
Mostafiz MMahmud SHussain MAli MTrajcevski GChoudhary AWu KDong B(2017)Class-based Conditional MaxRS Query in Spatial Data StreamsProceedings of the 29th International Conference on Scientific and Statistical Database Management10.1145/3085504.3085517(1-12)Online publication date: 27-Jun-2017
https://dl.acm.org/doi/10.1145/3085504.3085517
Amagata DHara T(2017)A General Framework for MaxRS and MaxCRS Monitoring in Spatial Data StreamsACM Transactions on Spatial Algorithms and Systems10.1145/30805543:1(1-34)Online publication date: 13-May-2017
https://dl.acm.org/doi/10.1145/3080554
Xu B(2016)On stabbing queries for generalised longest repeatsInternational Journal of Data Mining and Bioinformatics10.1504/IJDMB.2016.07815215:4(350-371)Online publication date: 1-Jan-2016
https://dl.acm.org/doi/10.1504/IJDMB.2016.078152
Feng KCong GBhowmick SPeng WMiao CÖzcan FKoutrika GMadden S(2016)Towards Best Region Search for Data ExplorationProceedings of the 2016 International Conference on Management of Data10.1145/2882903.2882960(1055-1070)Online publication date: 26-Jun-2016
https://dl.acm.org/doi/10.1145/2882903.2882960
Rahul STao YMilo TCalvanese D(2015)On Top-k Range Reporting in 2D SpaceProceedings of the 34th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2745754.2745777(265-275)Online publication date: 20-May-2015
https://dl.acm.org/doi/10.1145/2745754.2745777
Xu B(2015)On stabbing queries for generalized longest repeatProceedings of the 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM)10.1109/BIBM.2015.7359738(523-530)Online publication date: 9-Nov-2015
https://dl.acm.org/doi/10.1109/BIBM.2015.7359738
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents