Article

Free access

Are window queries representative for arbitrary range queries?

Authors:

Bernd-Uwe Pagel,

Hans-Werner SixAuthors Info & Claims

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

Pages 150 - 160

https://doi.org/10.1145/237661.237704

Published: 03 June 1996 Publication History

PDF eReader

References

[1]

A. Belussi and C. Faloutsos. Estimating the selectivity of spatial queries using the 'correlation' fractal dimension. In Proc. 21st Intl. Conf. on VLDB, pages 299-310, Zurich, 1995.

Digital Library

Google Scholar

[2]

N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In Proc. A CM SIGMOD, pages 322-331, Atlantic City, N J, 1990.

Digital Library

Google Scholar

[3]

A. Guttman. R-trees: a dynamic index structure for spatial searching. In Proc. A CM SIGMOD, pages 47-57, Boston, 1984.

Digital Library

Google Scholar

[4]

A. Henrich and H.-W. Six. How to split buckets in spatial data structures. In G. G ambosi, M. Scholl, and H.#W. Six, editors, Geographic Database Management Systems, pages 212-244, Capri (Italy), May 1991. Esprit Basic Research Series DG XIII, Springer-Verlag.

Google Scholar

[5]

A. Henrich, H.-W. Six, and P. Widmayer. The LSD-tree: spatial access to multidimensional point- and non-point objects. In Proc. I5th VLDB, pages 45-53, Amsterdam, 1989.

Digital Library

Google Scholar

[6]

i. Kamel and C. Faloutsos. On packing R- trees. In Proc. 2nd Intl. Conf. on Information and Knowledge Management, pages 490-499, Washington D.C., 1993.

Digital Library

Google Scholar

[7]

J. Nievergelt, H. Hinterberger, and K.C. Sevcik. The grid file: an adaptable, symmetric multikey file structure. A CM Transactions on Database Systems, 9(1):38-71, 1984.

Digital Library

Google Scholar

[8]

B.-U. Pagel. Analysis and Optimization o/ Index Structures in Geometric Databases. PhD thesis, University of Hagen, Germany, August 1995. in german.

Google Scholar

[9]

B.-U. Pagel, H.-W. Six, and H. Toben. The transformation technique for spatial objects revisited. In D. Abel and B.-C. Ooi, editors, Proc. 3rd Int, Symposium on Large Spatial Databases (SSD), pages 73-88, Singapore, June 1993. LNCS No. 692, Springer.

Digital Library

Google Scholar

[10]

B.-U. Pagel, H.-W. Six, H. Toben, and P. Widmayer. Towards an analysis of range query performance in spatial data structures. In Proc. 12th A CM PODS, pages 214-221, Washington, D.C., 1993.

Digital Library

Google Scholar

[11]

B.-U. Pagei, H.-W. Six, and M. Winter. Window query-optimal clustering of spatial objects. In Proc. 14th A CM PODS, pages 86-94, San Jos#, CA, 1995.

Digital Library

Google Scholar

[12]

L.A. Santald. Integral Geometry and Geometric Probability. Addison-Wesley, 1976.

Google Scholar

[13]

B. Seeger. Performance comparison of segment access methods implemented on top of the buddy-tree. In Proc. 2cd Symposium on Large Spatial Databases (SSD), pages 277-296, Zurich, 1991.

Digital Library

Google Scholar

[14]

M. Stonebraker, J. Frew, K. Gardels, and J. Meredith. The SEQUOIA 2000 storage benchmark. In Proc. A CM SIGMOD Int. Conf. on Management of Data, pages 2-9, Washington, D.C., May 1993.

Digital Library

Google Scholar

[15]

B. Seeger and H.-P. Kriegel. The buddytree: an efficient and robust access method for spatial data base systems. In Proc. 16th VLDB, pages 590-601, Brisbane, 1990.

Digital Library

Google Scholar

[16]

T.K. Sellis, N. Roussopoulos, and C. Faloutsos. The r+-tree: a dynamic access index for multi-dimensional objects. In Proc. 13th VLDB, pages 507-518, Brighton, England, 1987.

Digital Library

Google Scholar

Cited By

View all

Yufei Tao Dimitris Papadias (2004)Performance analysis of R*-trees with arbitrary node extentsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2004.1316:6(653-668)Online publication date: Jun-2004
https://doi.org/10.1109/TKDE.2004.13
Tao YPapadias DZhang J(2002)Cost models for overlapping and multiversion structuresACM Transactions on Database Systems10.1145/581751.58175427:3(299-342)Online publication date: 1-Sep-2002
https://dl.acm.org/doi/10.1145/581751.581754
Song JWhang KLee YLee MHan WPark B(2002)The clustering property of corner transformation for spatial database applicationsInformation and Software Technology10.1016/S0950-5849(02)00026-544:7(419-429)Online publication date: May-2002
https://doi.org/10.1016/S0950-5849(02)00026-5
Show More Cited By

Index Terms

Are window queries representative for arbitrary range queries?
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Range queries on uncertain data

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...
Decidable containment of recursive queries
Database theory

One of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...
Sliding-window top-k queries on uncertain streams

Recently, due to the imprecise nature of the data generated from a variety of streaming applications, such as sensor networks, query processing on uncertain data streams has become an important problem. However, all the existing works on uncertain data ...

Comments

Information & Contributors

Information

Published In

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

June 1996

249 pages

ISBN:0897917812

DOI:10.1145/237661

Chairman:
Richard Hull
Univ. of Colorado

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 June 1996

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS96

Sponsor:

SIGMOD/PODS96: Joint ACM SIGMOD International Conference on Management of Data and ACM Symposium on Principles of Database Systems

June 4 - 6, 1996

Quebec, Montreal, Canada

Acceptance Rates

PODS '96 Paper Acceptance Rate 22 of 84 submissions, 26%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
302
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yufei Tao Dimitris Papadias (2004)Performance analysis of R*-trees with arbitrary node extentsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2004.1316:6(653-668)Online publication date: Jun-2004
https://doi.org/10.1109/TKDE.2004.13
Tao YPapadias DZhang J(2002)Cost models for overlapping and multiversion structuresACM Transactions on Database Systems10.1145/581751.58175427:3(299-342)Online publication date: 1-Sep-2002
https://dl.acm.org/doi/10.1145/581751.581754
Song JWhang KLee YLee MHan WPark B(2002)The clustering property of corner transformation for spatial database applicationsInformation and Software Technology10.1016/S0950-5849(02)00026-544:7(419-429)Online publication date: May-2002
https://doi.org/10.1016/S0950-5849(02)00026-5
Korn FPagel BFaloutsos C(2001)On the 'Dimensionality Curse' and the 'Self-Similarity Blessing'IEEE Transactions on Knowledge and Data Engineering10.1109/69.90898313:1(96-111)Online publication date: 1-Jan-2001
https://dl.acm.org/doi/10.1109/69.908983
Mamoulis NPapadias D(2001)Selectivity Estimation of Complex Spatial QueriesAdvances in Spatial and Temporal Databases10.1007/3-540-47724-1_9(155-174)Online publication date: 4-Jul-2001
https://doi.org/10.1007/3-540-47724-1_9
Theodoridis YStefanakis ESellis T(2000)Efficient Cost Models for Spatial Queries Using R-TreesIEEE Transactions on Knowledge and Data Engineering10.1109/69.84224712:1(19-32)Online publication date: 1-Jan-2000
https://dl.acm.org/doi/10.1109/69.842247
Papadias DMamoulis NTheodoridis YVianu VPapadimitriou C(1999)Processing and optimization of multiway spatial joins using R-treesProceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/303976.303981(44-55)Online publication date: 1-May-1999
https://dl.acm.org/doi/10.1145/303976.303981
Hellerstein JHellerstein LKollios G(1999)On the Generation of 2-Dimensional Index WorkloadsDatabase Theory — ICDT’9910.1007/3-540-49257-7_9(113-130)Online publication date: 15-Jan-1999
https://doi.org/10.1007/3-540-49257-7_9

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Range queries on uncertain data

Decidable containment of recursive queries

Sliding-window top-k queries on uncertain streams

Comments

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF

eReader

Login options

Full Access

References

Cited By

Index Terms

Recommendations

Range queries on uncertain data

Decidable containment of recursive queries

Sliding-window top-k queries on uncertain streams

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations