research-article

Efficient Searching with Linear Constraints

Authors:

Pankaj K Agarwal,

Paulo G Franciosa,

Jeffrey Scott VitterAuthors Info & Claims

Journal of Computer and System Sciences, Volume 61, Issue 2

Pages 194 - 216

https://doi.org/10.1006/jcss.2000.1709

Published: 01 October 2000 Publication History

Abstract

We show how to preprocess a set S of points in Rd into an external memory data structure that efficiently supports linear-constraint queries. Each query is in the form of a linear constraint xd a0+ d 1i=1aixi; the data structure must report all the points of S that satisfy the constraint. This problem is called halfspace range searching in the computational geometry literature. Our goal is to minimize the number of disk blocks required to store the data structure and the number of disk accesses (I/Os) required to answer a query. For d=2, we present the first data structure that uses linear space and answers linear-constraint queries using an optimal number of I/Os in the worst case. For d=3, we present a near-linear-size data structure that answers queries using an optimal number of I/Os on the average. We present linear-size data structures that can answer d-dimensional linear-constraint queries (and even more general d-dimensional simplex queries) efficiently in the worst case. For the d=3 case, we also show how to obtain trade-offs between space and query time.

References

[1]

P. K. Agarwal, L. Arge, J. Erickson, P. G. Franciosa, and J. S. Vitter, Efficient searching with linear constraints, in Proc. 17th Annu. ACM Sympos. Principles Database Syst., 1998, pp. 169-178.

Digital Library

[2]

P.K. Agarwal, B. Aronov, T.M. Chan, M. Sharir, On levels in arrangements of lines, segments, planes, and triangles, Discrete Comput. Geom., 19 (1998) 315-331.

[3]

P.K. Agarwal, J. Erickson, Geometric range searching and its relatives, in: Advances in Discrete and Computational Geometry, AMS Press, Providence, 1999, pp. 1-58.

[4]

P.K. Agarwal, M. van Kreveld, M. Overmars, Intersection queries in curved objects, J. Algorithms, 15 (1993) 229-266.

Digital Library

[5]

L. Arge and J. S. Vitter, Optimal dynamic interval management in external memory, in Proc. IEEE Symp. on Foundtions of Comp. Sci., 1996, pp. 560-569.

[6]

L. Arge, V. Samoladas, J.S. Vitter, On two-dimensional indexability and optimal range search indexing, 1999.

[7]

L. Arge, D. E. Vengroff, and, J. S. Vitter, External-memory algorithms for processing line segments in Geographic Information Systems, Algorithmica, to appear. An extended abstract appears in “Proc. of Third European Symposium on Algorithms, 1995.”

[8]

R. Bayer, E. McCreight, Organization and maintenance of large ordered indexes, Acta Inform., 1 (1972) 173-189.

Digital Library

[9]

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. SIGMOD Intl. Conf. on Management of Data, 1990, pp. 322-331.

Digital Library

[10]

S. Berchtold, D. A. Keim, and H.-P. Kriegel, the X-tree: An index structure for higher dimensional data, in Proc. 22th VLDB Conference, 1996, pp. 28-39.

[11]

T. M. Chan, Random sampling, halfspace range reporting, and construction of (-k)-levels in three dimensions, in Proc. 39th IEEE Symp. Foundations of Computer Science, 1998, pp. 586-595.

[12]

B. Chazelle, Filtering search: a new approach to query-answering, SIAM J. Comput., 15 (1986) 703-724.

Digital Library

[13]

B. Chazelle, R. Cole, F.P. Preparata, C.K. Yap, New upper bounds for neighbor searching, Inform. Control, 68 (1986) 105-124.

Digital Library

[14]

B. Chazelle, L.J. Guibas, D.T. Lee, The power of geometric duality, BIT, 25 (1985) 76-90.

Digital Library

[15]

B. Chazelle, F.P. Preparata, Halfspace range search: An algorithmic application of k-sets, Discrete Comput. Geom., 1 (1986) 83-93.

Digital Library

[16]

K.L. Clarkson, P.W. Shor, Applications of random sampling in computational geometry, II, Discrete Comput. Geom., 4 (1989) 387-421.

Digital Library

[17]

D. Comer, The ubiquitous B-tree, ACM Comput. Surveys, 11 (1979) 121-137.

Digital Library

[18]

A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. Ramos, Randomized external-memory algorithms for some geometric problems, in Proc. 14th Annu. ACM Sympos. Comput. Geom., 1998, pp. 269-268.

Digital Library

[19]

T.K. Dey, Improved bounds on planar k-sets and related problems, Discrete Comput. Geom., 19 (1998) 373-382.

[20]

F. Dumortier, M. Gyssens, and L. Vandeurzen, On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases, in Proc. ACM Symp. Principles of Database Systems, 1997, pp. 68-77.

Digital Library

[21]

H. Edelsbrunner, Springer-Verlag, Heidelberg, 1987.

[22]

H. Edelsbrunner, E. Welzl, Constructing belts in two-dimensional arrangements with applications, SIAM J. Comput., 15 (1986) 271-284.

[23]

G. Evangelidis, D. Lomet, B. Salzberg, The HB¿-tree: a multi-attribute index supporting concurrency, recovery and node consolidation, VLDB J., 6 (1997) 1-25.

Digital Library

[24]

P. G. Franciosa, and, M. Talamo, Time optimal halfplane search on external memory, Unpublished manuscript, 1997.

[25]

P.G. Franciosa, M. Talamo, Orders, k-sets and fast halfplane search on paged memory, Springer-Verlag, Berlin/New York, 1994.

[26]

J. Goldstein, R. Ramakrishnan, U. shaft, and J.-B. Yu, Processing queries by linear constraints, in Proc. ACM Symp. Principles of Database Systems, 1997, pp. 257-267.

[27]

M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter, External-memory computational geometry, in Proc. IEEE Symp. on Foundations of Comp. Sci., 1993, pp. 714-723.

Digital Library

[28]

R.H. Güting, An introduction to spatial database systems, VLDB J., 4 (1994) 357-399.

[29]

A. Guttman, R-trees: A dynamic index structure for spatial searching, in Proc. SIGMOD Intl. Conf. on Management of Data, 1985, pp. 47-57.

[30]

D. Haussler, E. Welzl, Epsilon-nets and simplex range queries, Discrete Comput. Geom., 2 (1987) 127-151.

Digital Library

[31]

A. Henrich, Improving the performance of multi-dimensional access structures based on kd-trees, in Proc. 12th IEEE Intl. Conf. on Data Engineering, 1996, pp. 68-74.

[32]

E. G. Hoel and H. Samet, A qualitative comparison study of data structures for large line segment databases, in Proc. ACM SIGMOD Conf. on Management of Data, 1992, pp. 205-214.

[33]

I. Kamel and C. Faloutsos, Hilbert R-tree: An improved R-tree using fractals, in Proceedings 20th International Conference on Very Large Databases, 1994, pp. 500-509.

[34]

P.C. Kanellakis, S. Ramaswamy, D.E. Vengroff, J.S. Vitter, Indexing for data models with constraints and classes, J. Comput. System. Sci., 52 (1996) 589-612.

Digital Library

[35]

D. Lomet, B. Salzberg, The hB-tree: A multiattribute indexing method with good guaranteed performance, ACM Trans. Database Systems, 15 (1990) 625-658.

Digital Library

[36]

J. Matousek, Efficient partition trees, Discrete Comput. Geom., 8 (1992) 315-334.

Digital Library

[37]

J. Matousek, Reporting points in halfspaces, Comput. Geom. Theory Appl., 2 (1992) 169-186.

Digital Library

[38]

J. Matousek, Geometric range searching, ACM Comput. Surv., 26 (1994) 421-461.

Digital Library

[39]

K. Mehlhorn, Springer-Verlag, Heidelberg, 1984.

[40]

R. Motwani, P. Raghavan, Cambridge University Press, New York, 1995.

[41]

J. Nievergelt, H. Hinterberger, K. Sevcik, The grid file: An adaptable, symmetric multikey file structure, ACM Trans. Database Systems, 9 (1984) 257-276.

Digital Library

[42]

J. Nievergelt, P. Widmayer, Spatial data structures: Concepts and design choices, in: Lecture Notes in Computer Science, 1340, Springer-Verlag, Berlin/New York, 1997.

[43]

M.H. Overmars, J. van Leeuwen, Maintenance of configurations in the plane, J. Comput. System Sci., 23 (1981) 166-204.

[44]

S. Ramaswamy and S. Subramanian, Path caching: A technique for optimal external searching, in Proc. ACM Symp. Principles of Database Systems, 1994, pp. 25-35.

[45]

J. Robinson, The K-D-B tree: A search structure for large multidimensional dynamic indexes, in Proc. ACM SIGMOD Conf. on Management of Data, 1984, pp. 10-18.

[46]

H. Samet, Addison¿Wesley, Reading, 1989.

[47]

H. Samet, Addison¿Wesley, Reading, 1989.

[48]

T. Sellis, N. Roussopoulos, and, C. Faloutsos, The R+-tree: A dynamic index for multi-dimensional objects, in, Proc. IEEE International Conf. on Very Large Databases, 1987.

[49]

S. Subramanian and S. Ramaswamy, The P-range tree: A new data structure for range searching in secondary memory, in Proc. ACM-SIAM Symp. on Discrete Algorithms, 1995, pp. 378-387.

Digital Library

[50]

G. Tóth, Point sets with many k-sets, in preparation.

[51]

D. E. Vengroff and J. S. Vitter, Efficient 3-d range searching in external memory, in Proc. ACM Symp. on Theory of Computation, 1996, pp. 192-201.

Digital Library

[52]

J. S. Vitter, Online data structures in external memory, in, Proc. Annual International Colloquim on Automata, Languages, and Programming, 1999.

[53]

D.E. Willard, Polygon retrieval, SIAM J. Comput., 11 (1982) 149-165.

Cited By

Mouratidis KLi KTang B(2024)Quantifying the competitiveness of a dataset in relation to general preferencesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00804-133:1(231-250)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00778-023-00804-1
Rahul STao Y(2022)Generic Techniques for Building Top-k StructuresACM Transactions on Algorithms10.1145/354607418:4(1-23)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3546074
Asudeh AJagadish HMiklau GStoyanovich J(2018)On obtaining stable rankingsProceedings of the VLDB Endowment10.14778/3291264.329126912:3(237-250)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.14778/3291264.3291269
Show More Cited By

Index Terms

Efficient Searching with Linear Constraints

Recommendations

Efficient Relational Joins with Arithmetic Constraints on Multiple Attributes
IDEAS '05: Proceedings of the 9th International Database Engineering & Application Symposium

We introduce and study a new class of queries that we refer to as ACMA (arithmetic constraints on multiple attributes) queries. Such combinatorial queries require the simultaneous satisfaction of arithmetic constraints on three or more attributes from ...
Exploiting Constraints in Query Processing: Query transformation using interity constraints and views
Orthogonal range searching in linear and almost-linear space
WADS'07: Proceedings of the 10th international conference on Algorithms and Data Structures

In this paper we describe space-efficient data structures for two-dimensional range searching problem. We present a dynamic linear space data structure that supports orthogonal range reporting queries in O(log n + k log^ε n) time, where k is the size of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 61, Issue 2

Special issue on the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on principles of database systems

Oct. 2000

189 pages

ISSN:0022-0000

Editor:
E. K. Blum
Univ. of Southern California, Los Angeles

Issue’s Table of Contents

Copyright © Academic Press.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 October 2000

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 23 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mouratidis KLi KTang B(2024)Quantifying the competitiveness of a dataset in relation to general preferencesThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-023-00804-133:1(231-250)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00778-023-00804-1
Rahul STao Y(2022)Generic Techniques for Building Top-k StructuresACM Transactions on Algorithms10.1145/354607418:4(1-23)Online publication date: 10-Oct-2022
https://dl.acm.org/doi/10.1145/3546074
Asudeh AJagadish HMiklau GStoyanovich J(2018)On obtaining stable rankingsProceedings of the VLDB Endowment10.14778/3291264.329126912:3(237-250)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.14778/3291264.3291269
Rahul STao YMilo TTan W(2016)Efficient Top-k Indexing via General ReductionsProceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems10.1145/2902251.2902290(277-288)Online publication date: 15-Jun-2016
https://dl.acm.org/doi/10.1145/2902251.2902290
Gerolymatos PSioutas SNodarakis NPanaretos ATsakalidis K(2015)SMaRTJournal of Systems and Software10.1016/j.jss.2015.03.068105:C(79-90)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1016/j.jss.2015.03.068
Chan T(2012)Optimal Partition TreesDiscrete & Computational Geometry10.5555/3116278.311656847:4(661-690)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.5555/3116278.3116568
Afshani PDey TWhitesides S(2012)Improved pointer machine and I/O lower bounds for simplex range reporting and related problemsProceedings of the twenty-eighth annual symposium on Computational geometry10.1145/2261250.2261301(339-346)Online publication date: 17-Jun-2012
https://dl.acm.org/doi/10.1145/2261250.2261301
Yu AAgarwal PYang JCandan KChen YSnodgrass RGravano LFuxman A(2012)Processing a large number of continuous preference top-k queriesProceedings of the 2012 ACM SIGMOD International Conference on Management of Data10.1145/2213836.2213882(397-408)Online publication date: 20-May-2012
https://dl.acm.org/doi/10.1145/2213836.2213882
Streppel MYi K(2011)Approximate Range Searching in External MemoryAlgorithmica10.5555/3118734.311882559:2(115-128)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.5555/3118734.3118825
Afshani PHamilton CZeh N(2011)Cache-Oblivious Range Reporting with Optimal Queries Requires Superlinear SpaceDiscrete & Computational Geometry10.5555/3116262.311641845:4(824-850)Online publication date: 1-Jun-2011
https://dl.acm.org/doi/10.5555/3116262.3116418
Show More Cited By

View Options

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

Media

Figures

Other

Tables

View Issue’s Table of Contents