Uniform generation in spatial constraint databases and applications (Extended abstract)
Pages 254 - 259
Abstract
We study the efficient approximation of queries in linear constraint databases using sampling techniques. We define the notion of an almost uniform generator for a generalized relation and extend the classical generator of Dyer, Frieze and Kannan for convex sets to the union and the projection of relations. For the intersection and the difference, we give sufficient conditions for the existence of such generators. We show how such generators give relative estimations of the volume and approximations of generalized relations as the composition of convex hulls obtained from the samples.
References
[1]
F. Affentranger and J. A. Wieacker. On the convex hull of uniform random points in a simple d-polytope. Discrete Cornput. Geom., 6:291-305, 1991.
[2]
I. B~r~ny and Z. Fiiredi. Computing the volume is difficult. In Proceedings of the Eighteenth Annual A CM Symposium on Theory of Computing, pages 442-447, 1986.
[3]
M. Benedikt, G. Dong, L. Libkin, and L. Wong. Relational expressive power of constraint query languages. In Proceedings of the Fifteenth Symposium on Principles of Database Systems, pages 5-16, 1996.
[4]
M. Benedikt and L. Libkin. Languages for relational databases over interpreted structures. In Proceedings of the Sixteenth Symposium on Principles of Database Systems, pages 87-98, 1997.
[5]
M. Benedikt and L. Libkin. Safe constraint queries. In Proceedings of the Seventeenth Symposium on Principles of Database Systems, pages 99-108, 1998.
[6]
M. Benedikt and L. Libkin. Exact and approximate aggregation in constraint query languages. In Symposium on Principles of Databases Systems, pages 102-113, 1999.
[7]
W. Cochran. Sampling Techniques. Wiley, 1977.
[8]
M. Dyer, A. Frieze, and R. Kannan. A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the ACM, 38:1-17, 1991.
[9]
G. Elekes. A geometric inequality and the complexity of computing volume. Discr. Comput. Geom, 1, 1986.
[10]
D. M. Flewelling. Comparing Subsets from Digital Spatial Archives: Point Set Similarity. PhD thesis, University of Maine, 1997.
[11]
M. GrStschel, L. Lovgsz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988.
[12]
S. Grumbach, P. Rigaux, and L. Segoufin. On the orthographic dimension of constraint databases. In ICD T, volume 1540 of Lecture Notes in Computer Science, pages 199-216, 1999.
[13]
S. Grumbach and J. Su. Finitely representable databases. Journal of Computer and System Sciences, 55(2):273-298, 1997.
[14]
S. Grumbach and J. Su. Queries with arithmetical constraints. Theoretical Computer Science, 173(1):151-181, 1997.
[15]
S. Grumbach, J. Su, and C. Tollu. Linear constraint query languages : Expressive power and complexity. In D. Leivant, editor, Logic and Computational Complexity, volume 960 of LNCS. Springer Verlag, 1994.
[16]
M. Gyssens, J. V. den Bussche, and D. V. Gucht. Complete geometric query languages. Journal of Computer and System Sciences, 58(3):483-511, 1999.
[17]
W.-C. Hou, G. Ozsoyoglu, and B. K. Taneja. Statistical estimators for relational algebra expressions. In Symposium on Principles of Databases Systems, pages 276-287, 1988.
[18]
M. Jerrum, L. Valiant, and V. Vazirani. Random generation of combinatorial structures from a uniform generation. Theoretical Computer Science, 43:169-188, 1986.
[19]
P. C. Kanellakis, G. M. Kuper, and P. Z. Revesz. Constraint query languages. Journal of Computer and System Sciences, 51(1):26-52, Aug. 1995.
[20]
R. M. Karp and M. Luby. Monte-carlo algorithms for enumeration and reliability problems. Proceedings of the 2gth Symposium on Foundations of Computer Science, pages 56- 64, 1983.
[21]
M. Karpinski and A. Macintyre. Approximating the volume of general Pfaffian bodies. In Structures in Logic and Computer Science, volume 1261 of Lecture Notes in Computer Science, pages 162-173, 1997.
[22]
P. Koiran. Approximating the volume of definable sets. In 36th Symposium on Foundations of Computer Science, pages 134-141, 1995.
[23]
R. J. Lipton and J. F. Naughton. Query size estimation by adaptive sampling. Journal of Computer and System Sciences, 51(1):18-25, 1995.
[24]
K. Mehlhorn and S. Ngher. The LEDA Platform of Combinatorial and Geometric Computing. Cambridge University Press, 1999.
[25]
F. Olken and D. Rotem. Random sampling form database files: A survey. In Z. Michalewicz, editor, Fifth International Conference on Statistical and Scientific Database Management, 1990.
[26]
F. Olken and D. Rotem. Sampling from spatial databases. In International Conference on Data Engineering, pages 199- 208, 1993.
[27]
J. Paredaens, J. V. den Bussche, and D. V. Gucht. Towards a theory of spatial database queries. In Symposium on PrincipIes of Databases Systems, pages 279-288, 1994.
[28]
A. Schrijver. Theory of linear and integer programming. Wiley, 1986.
[29]
Van Leuwen, editor. Handbook of Theoretical Computer Science, voI A. Elsevier, 1990.
[30]
L. Vandeurzen, M. Gyssens, and D. V. Gucht. An expressive language for linear spatial database queries. In Symposium on Principles of Databases Systems, 1998.
Index Terms
- Uniform generation in spatial constraint databases and applications (Extended abstract)
Recommendations
Uniform generation in spatial constraint databases and applications
We study the efficient approximation of queries in linear constraint databases using sampling techniques. We define the notion of an almost uniform generator for a generalized relation and extend the classical generator of Dyer, Frieze and Kannan for ...
Non-uniform random number generation
A frequently used technique for generating non-uniform random numbers is to combine uniform random numbers. For example, the sum of two uniform random numbers yields a triangular distribution. The difference yields another which will be statistically ...
An Extended Algebra for Constraint Databases
Constraint relational databases use constraints to both model and query data. A constraint relation contains a finite set of generalized tuples. Each generalized tuple is represented by a conjunction of constraints on a given logical theory and, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2000 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 May 2000
Check for updates
Qualifiers
- Article
Conference
SIGMOD/PODS00
Sponsor:
SIGMOD/PODS00: ACM International Conference on Management of Data and Symposium on Principles of Database Systems
May 15 - 18, 2000
Texas, Dallas, USA
Acceptance Rates
PODS '00 Paper Acceptance Rate 26 of 119 submissions, 22%;
Overall Acceptance Rate 642 of 2,707 submissions, 24%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 274Total Downloads
- Downloads (Last 12 months)37
- Downloads (Last 6 weeks)6
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in