Article

Free access

Efficient searching with linear constraints

Authors:

Jeffry Scott VitterAuthors Info & Claims

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

Pages 169 - 178

https://doi.org/10.1145/275487.275506

Published: 01 May 1998 Publication History

PDF eReader

References

[1]

P. K, Agarwal, B, Aronov, T. Chart, and M. Shark. On levels in arrangements of lines, segments, planes, and triangles. Discrete Comput. Geom., 1998, in press.

Crossref

Google Scholar

[2]

P. K, Agarwal, M. de Berg, J. Matou~ek, and O, Schwarzkopf. Constructing levels in arrangements and higher order Voronoi diagrams. In Proc. 10th Annu. A GM Sympos. Gomput. Geom., pages 67-75, 1994.

Digital Library

Google Scholar

[3]

P, K, Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and It, Pollack, editors, Discrete and Computational Geometry: Ten Years Later, 1998, to appear.

Google Scholar

[4]

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

Digital Library

Google Scholar

[5]

L. Arge and J. S. Vitter. Optimal dynamic interval management in external memory. In Prec. IEEE Syrup. on Foundations of Comp. Sci., pages 560-569, 1996.

Digital Library

Google Scholar

[6]

it, Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Aeta informatica, 1:173- 189, 1972.

Digital Library

Google Scholar

[7]

N, Beckmann, H.-P. Kriegel, R. Schneider, and B, Seeger, The l~*-tree: An efficient and robust access method for points and rectangles. In Proc. SIG- MOD Intl. Conf. on Management of Data, pages 322- 331, 1990.

Digital Library

Google Scholar

[8]

S, Berchtold, C. Biihm, D. A. Keim, and H.-P. Kriegel. A cost model for nearest neighbor search in highdimensional data space. In Prec. A GM Sympos. Principles of Database Systems, pages 78-86, 1997.

Digital Library

Google Scholar

[9]

S, Berehtold, D, A. Keim, and H.-P. Kriegel. The X- tree: An index structure for higher dimensional data. In Proc, 2Zth international Conference on Very Larye Databases, pages 28-39, 1996.

Digital Library

Google Scholar

[10]

B. Chazelle, Filtering search: A new approach to queryanswering. SIAM J. Comput., 15:703-724, 1986.

Digital Library

Google Scholar

[11]

B. Chazelle, R. Cole, F. P. Prepaxata, and C. K. Yap. New upper bounds for neighbor searching. Inform. Oontrol, 68:I05-124, i986.

Digital Library

Google Scholar

[12]

B, Claazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality. BIT, 25:76-90, 1985.

Digital Library

Google Scholar

[13]

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

Crossref

Google Scholar

[14]

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

Digital Library

Google Scholar

[15]

D, Comer. The ubiquitous B-tree. A GM Computing Surveys, 11:121-137, 1979.

Digital Library

Google Scholar

[16]

T, Dey. Improved bounds for k-sets and k-th levels. In Proc, 38th Annu. IEEB Bympos. Found. Comput. Sei., pages, 156-161, 1997.

Digital Library

Google Scholar

[17]

F, Dumortier, M, Gyssens, and L. Vandeurzen. On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases. In Proe. A CM Syrup. Principles of Database Systems, pages 68-77, 1997,

Digital Library

Google Scholar

[18]

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

Digital Library

Google Scholar

[19]

G. Evangelidis, D. Lomet, and B. Salzberg. The hBntree: a multi-attribute index supporting concurrency, recovery and node consolidation. The VLDB Journal, 6:1-25, 1997.

Digital Library

Google Scholar

[20]

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

Google Scholar

[21]

P. G. Franciosa and M. Talamo. Orders, k-sets and fast halfplane search on paged memory. In Prec. Workshop on Orders, Algorithms and Applications, volume 831 of Lecture Notes Comput. Sci., pages 117-127. Springer- Verlag, 1994.

Digital Library

Google Scholar

[22]

J. Goldstein, R. Ramakrishnan, U. Shaft, and J.-B. Yu. Processing queries by linear constraints. In Proc. A CM Syrup. Principles of Database Systems, pages 257-267, 1997.

Digital Library

Google Scholar

[23]

M. T. Goodrich, J.-J. Tsay, D. E. Vengmff, and J. S. Vitter. External-memory computational geometry, in Prec. IEEE Syrup. on Foundations of Comp. Sci., pages 714-723, 1993.

Digital Library

Google Scholar

[24]

It. Gfiting. An introduction to spatial database systems. VLDB Journal, 4:357-399, 1994.

Digital Library

Google Scholar

[25]

A. Guttman. R-trees: A dynamic index structure for spatial searching. In Proe. A CM SIGMOD Conf. on Management of Data, pages 47-57, 1985.

Digital Library

Google Scholar

[26]

D. Hausshr and E. Welzl. Epsilon-nets and simplex range queries. Discrete Comput. Geom., 2:127-151, 1987.

Digital Library

Google Scholar

[27]

A. Hen_rich. Improving the performance of multidimensional access structures based on kd-trees. In Proc. 12th IEEE Intl. Conf. on Data Engineering, pages 68-74, 1996.

Digital Library

Google Scholar

[28]

E. G. Hod and H. Samet. A qualitative comparison study of data structures for large line segment databases. In Prec. A CM SIGMOD Conf. on Management of Data, pages 205-214, 1992.

Digital Library

Google Scholar

[29]

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

Digital Library

Google Scholar

[30]

P. C. Kanellakis, S. Ramaswamy, D. E. Vengroff~ and J. S. Vitter. Indexing for data models with constraints and classes. Journal of Computer and System Sciences, 52:589-612, 1996.

Digital Library

Google Scholar

[31]

D. Lomet and B. Salzbexg. The hB-tree: A multiattribute indexing method with good guaranteed performanee. A CM Transactions on Database Systems, 15(4):625-658, 1990.

Digital Library

Google Scholar

[32]

J. Matou~ek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992.

Digital Library

Google Scholar

[33]

J. Matou~,ek. Reporting points in halfspaces. Comput. Geom. Theory AppL, 2(3):169-186, 1992.

Digital Library

Google Scholar

[34]

J. Matou~ek. Geometric range searching. A CM Corn. put. Surv., 26:421-461, 1994.

Digital Library

Google Scholar

[35]

It. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, 1995.

Crossref

Google Scholar

[36]

J. Nievezgelt, H. Hinterbexger, and K. Sevcik. The grid file: An adaptable, symmetric multikey file structure. A CM Transactions on Database Systems, 9:257-276, 1984.

Digital Library

Google Scholar

[37]

J, Nievergel~ and P. Widmayer. Spatial data structures: Concepts and design choices. In M. van Kreveld, J, Nievergelt, T, Roos, and P. Widmayer, editors, Algorithmic Foundations of GIS. Springer-Verlag, 1997. Lecture Notes in Computer Science Vol. 1340.

Digital Library

Google Scholar

[38]

M, H. Overmars and J. van Leeuwen. Maintenance of configurations in the plane, 23:166-204, 1981.

Google Scholar

[39]

S, Ramaswamy and P. Kanellakis. OOBD indexing by class division. In A.P.L U. Series, Academic Press, New York, 1995.

Google Scholar

[40]

S. Ramaswamy and S. Subramanian. Path caching: A technique for optimal external searching. In Proc. A UM Syrup. Principles of Database Systems, pages 25- 351 1994,

Digital Library

Google Scholar

[41]

J. Robinson. The K-D-B tree: A search structure for largo multidimensional dynamic indexes. In Proe. A UM SIGMOD Gonf. on Management of Data, pages 10-18, 1984,

Digital Library

Google Scholar

[42]

H. Samet. Applications of Spatial Data Structures: Gomputer Graphics, Image Processing, and GIS. Addison Wesley, MA, 1989.

Digital Library

Google Scholar

[43]

H. Samet. The Design and Analyses of Spatial Data Structures, Addison Wesley, MA, 1989.

Digital Library

Google Scholar

[44]

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.

Digital Library

Google Scholar

[45]

S, Subramanian and S. Ramaswamy. The p-range tree: A new data structure for range searching in secondary memory. In Proe. A GM-SIAM Syrup. on Discrete Algorithms, pages 378-387, 1995.

Digital Library

Google Scholar

[46]

D, E. Vengroff and J. S. Vitter. Efficient 3-d range searching in external memory. In Proe. of the Z8th An. nual A GM Symposium on Theory of Computing, pages 192-201, 1996.

Digital Library

Google Scholar

[47]

D, E, Willard. Polygon retrieval. SIAM J. Uomput., 11:149-165~ 1982.

Digital Library

Google Scholar

Cited By

View all

Künnemann MMoeller DPaturi RSchneider S(2019)Subquadratic Algorithms for Succinct Stable MatchingAlgorithmica10.1007/s00453-019-00564-x81:7(2991-3024)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00453-019-00564-x
Nodarakis NSioutas SGerolymatos PTsakalidis ATzimas G(2015)Convex Polygon Planar Range Queries on the CloudRevised Selected Papers of the First International Workshop on Algorithmic Aspects of Cloud Computing - Volume 951110.1007/978-3-319-29919-8_9(114-125)Online publication date: 14-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-29919-8_9
Khan AYanki PDimcheva BKossmann DDyreson CLi FÖzsu M(2014)Towards indexing functionsProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2610493(241-252)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2588555.2610493
Show More Cited By

Index Terms

Efficient searching with linear constraints

Recommendations

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core ...
Solving sparse linear constraints
IJCAR'06: Proceedings of the Third international joint conference on Automated Reasoning

Linear arithmetic decision procedures form an important part of theorem provers for program verification. In most verification benchmarks, the linear arithmetic constraints are dominated by simple difference constraints of the form x ≤y + c. Sparse ...
Edge searching and fast searching with constraints
Abstract
In this paper, we consider the edge searching problem and the fast searching problem with constraints on some vertices. The edge searching problem was introduced by Megiddo et al. (1988) [15], in which a group of searchers want to capture an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

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

May 1998

286 pages

ISBN:0897919963

DOI:10.1145/275487

Chairmen:
Alberto Mendelson
Univ. of Toronto
,
Jan Paredaens
Univ. of Antwerp

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: 01 May 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS98

Sponsor:

SIGMOD/PODS98: Special Interest Group on Management of Data

June 1 - 4, 1998

Washington, Seattle, USA

Acceptance Rates

PODS '98 Paper Acceptance Rate 28 of 119 submissions, 24%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
447
Total Downloads

Downloads (Last 12 months)40
Downloads (Last 6 weeks)13

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Künnemann MMoeller DPaturi RSchneider S(2019)Subquadratic Algorithms for Succinct Stable MatchingAlgorithmica10.1007/s00453-019-00564-x81:7(2991-3024)Online publication date: 1-Jul-2019
https://dl.acm.org/doi/10.1007/s00453-019-00564-x
Nodarakis NSioutas SGerolymatos PTsakalidis ATzimas G(2015)Convex Polygon Planar Range Queries on the CloudRevised Selected Papers of the First International Workshop on Algorithmic Aspects of Cloud Computing - Volume 951110.1007/978-3-319-29919-8_9(114-125)Online publication date: 14-Sep-2015
https://dl.acm.org/doi/10.1007/978-3-319-29919-8_9
Khan AYanki PDimcheva BKossmann DDyreson CLi FÖzsu M(2014)Towards indexing functionsProceedings of the 2014 ACM SIGMOD International Conference on Management of Data10.1145/2588555.2610493(241-252)Online publication date: 18-Jun-2014
https://dl.acm.org/doi/10.1145/2588555.2610493
Endres MKießling W(2011)Semi-skyline optimization of constrained skyline queriesProceedings of the Twenty-Second Australasian Database Conference - Volume 11510.5555/2460396.2460400(7-16)Online publication date: 17-Jan-2011
https://dl.acm.org/doi/10.5555/2460396.2460400
Nestorov SLiu CFoster I(2007)Efficient processing of relational queries with sum constraintsProceedings of the joint 9th Asia-Pacific web and 8th international conference on web-age information management conference on Advances in data and web management10.5555/1769708.1769766(440-451)Online publication date: 16-Jun-2007
https://dl.acm.org/doi/10.5555/1769708.1769766
Nestorov SLiu CFoster I(2007)Efficient Processing of Relational Queries with Sum ConstraintsAdvances in Data and Web Management10.1007/978-3-540-72524-4_46(440-451)Online publication date: 2007
https://doi.org/10.1007/978-3-540-72524-4_46
Xin DHan JCheng HLi X(2006)Answering top-k queries with multi-dimensional selectionsProceedings of the 32nd international conference on Very large data bases10.5555/1182635.1164168(463-474)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.5555/1182635.1164168
Xin DChen CHan J(2006)Towards robust indexing for ranked queriesProceedings of the 32nd international conference on Very large data bases10.5555/1182635.1164149(235-246)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.5555/1182635.1164149
Liu CYang LFoster I(2005)Efficient Relational Joins with Arithmetic Constraints on Multiple AttributesProceedings of the 9th International Database Engineering & Application Symposium10.1109/IDEAS.2005.24(210-220)Online publication date: 25-Jul-2005
https://dl.acm.org/doi/10.1109/IDEAS.2005.24
Elbassioni KElmasry AKamel I(2005)An Indexing Method for Answering Queries on Moving ObjectsDistributed and Parallel Databases10.1007/s10619-005-6830-217:3(215-249)Online publication date: 21-Mar-2005
https://dl.acm.org/doi/10.1007/s10619-005-6830-2
Show More Cited By

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

An algorithm for linear least squares problems with equality and nonnegativity constraints

Solving sparse linear constraints

Edge searching and fast searching with constraints