Uniform Generation in Spatial Constraint Databases and Applications David Gross and Michel de Rougemont   View Paper (PDF)   Return to Sampling 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 Note: References link to DBLP on the Web. [1] ... [2] Imre Bárány , Zoltán Füredi : Computing the Volume Is Difficult. STOC 1986 : 442-447 [3] Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong : Relational Expressive Power of Constraint Query Languages. PODS 1996 : 5-16 [4] Michael Benedikt , Leonid Libkin : Languages for Relational Databases over Interpreted Structures. PODS 1997 : 87-98 [5] Michael Benedikt , Leonid Libkin : Safe Constraint Queries. PODS 1998 : 99-108 [6] Michael Benedikt , Leonid Libkin : Exact and Approximate Aggregation in Constraint Query. PODS 1999 : 102-113 [7] William G. Cochran: Sampling Techniques, 3rd Edition. John Wiley 1977, ISBN 0-471-16240-X [8] Martin Dyer , Alan M. Frieze , Ravi Kannan : A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. JACM 38(1) : 1-17(1991) [9] ... [10] ... [11] ... [12] Stéphane Grumbach , Philippe Rigaux , Luc Segoufin : On the Orthographic Dimension of Constraint Databases. ICDT 1999 : 199-216 [13] Stéphane Grumbach , Jianwen Su : Finitely Representable Databases. JCSS 55(2) : 273-298(1997) [14] Stéphane Grumbach , Jianwen Su : Queries with Arithmetical Constraints. TCS 173(1) : 151-181(1997) [15] Stéphane Grumbach , Jianwen Su , Christophe Tollu : Linear Constraint Query Languages: Expressive Power and Complexity. LCC 1994 : 426-446 [16] Marc Gyssens , Jan Van den Bussche , Dirk Van Gucht : Complete Geometric Query Languages. JCSS 58(3) : 483-511(1999) [17] Wen-Chi Hou , Gultekin Özsoyoglu , Baldeo K. Taneja : Statistical Estimators for Relational Algebra Expressions. PODS 1988 : 276-287 [18] Mark Jerrum , Leslie G. Valiant , Vijay V. Vazirani : Random Generation of Combinatorial Structures from a Uniform Distribution. TCS 43 : 169-188(1986) [19] Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz : Constraint Query Languages. JCSS 51(1) : 26-52(1995) [20] Richard M. Karp , Michael Luby : Monte-Carlo Algorithms for Enumeration and Reliability Problems. FOCS 1983 : 56-64 [21] Marek Karpinski , Angus Macintyre : Approximating the Volume of General Pfaffian Bodies. Structures in Logic and Computer Science 1997 : 162-173 [22] Pascal Koiran : Approximating the Volume of Definable Sets. FOCS 1995 : 134-141 [23] Richard J. Lipton , Jeffrey F. Naughton : Query Size Estimation by Adaptive Sampling. JCSS 51(1) : 18-25(1995) [24] Kurt Mehlhorn , Stefan Näher : LEAD: A Platform for Combinatorial and Geometric Computing. Cambridge University Press 1999, ISBN 0-521-56329-1 Contents [25] Frank Olken , Doron Rotem : Random Sampling from Database Files: A Survey. SSDBM 1990 : 92-111 [26] Frank Olken , Doron Rotem : Sampling from Spatial Databases. ICDE 1993 : 199-208 [27] Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht : Towards a Theory of Spatial Database Queries. PODS 1994 : 279-288 [28] ... [29] Jan van Leeuwen (Ed.): Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. Elsevier and MIT Press 1990, ISBN 0-444-88071-2 and 0-262-22038-5 Contents [30] Luc Vandeurzen , Marc Gyssens , Dirk Van Gucht : An Expressive Language for Linear Spatial Database Queries. PODS 1998 : 109-118 BIBTEX @inproceedings{DBLP:conf/pods/GrossR00,   author    = {David Gross and                 Michel de Rougemont},    title     = {Uniform Generation in Spatial Constraint Databases and Applications},    booktitle = {Proceedings of the Nineteenth ACM SIGMOD-SIGACT-SIGART Symposium                 on Principles of Database Systems, May 15-17, 2000, Dallas, Texas,                 USA},    publisher = {ACM},    year      = {2000},    isbn      = {1-58113-214-X},    pages     = {254-259},    crossref  = {DBLP:conf/pods/00},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.