On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications.

@inproceedings{DBLP:conf/icdt/MuthukrishnanPS99,
  author    = {S. Muthukrishnan and
               Viswanath Poosala and
               Torsten Suel},
  editor    = {Catriel Beeri and
               Peter Buneman},
  title     = {On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity,
               and Applications},
  booktitle = {Database Theory - ICDT '99, 7th International Conference, Jerusalem,
               Israel, January 10-12, 1999, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1540},
  year      = {1999},
  isbn      = {3-540-65452-6},
  pages     = {236-256},
  ee        = {db/conf/icdt/MuthukrishnanPS99.html, http://link.springer.de/link/service/series/0558/bibs/1540/15400236.htm},
  crossref  = {DBLP:conf/icdt/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Online Edition: Springer LINK

References

[1]

...

[2]

Sanjeev Arora: Polynomial Time Approximation Schemes for Euclidean TSP and Other Geometric Problems. FOCS 1996: 2-11 BibTeX

[3]

Shahid H. Bokhari: Partitioning Problems in Parallel, Pipelined, and Distributed Computing. IEEE Trans. Computers 37(1): 48-57(1988) BibTeX

[4]

Hervé Brönnimann, Michael T. Goodrich: Almost Optimal Set Covers in Finite VC-Dimension (Preliminary Version). Symposium on Computational Geometry 1994: 293-302 BibTeX

[5]

Bruno Carpentieri, James A. Storer: A Split-Merge Parallel Block-Matching Algorithm for Video Displacement Estimation. Data Compression Conference 1992: 239-248 BibTeX

[6]

...

[7]

Kenneth L. Clarkson: A Las Vegas Algorithm for Linear Programming When the Dimension Is Small. FOCS 1988: 452-456 BibTeX

[8]

Fabrizio d'Amore, Paolo Giulio Franciosa: On the Optimal Binary Plane Partition for Sets of Isothetic Rectangles. Inf. Process. Lett. 44(5): 255-259(1992) BibTeX

[9]

Robert J. Fowler, Mike Paterson, Steven L. Tanimoto: Optimal Packing and Covering in the Plane are NP-Complete. Inf. Process. Lett. 12(3): 133-137(1981) BibTeX

[10]

...

[11]

Michelangelo Grigni, Fredrik Manne: On the Complexity of the Generalized Block Distribution. IRREGULAR 1996: 319-326 BibTeX

[12]

David Haussler, Emo Welzl: Epsilon-Nets and Simplex Range Queries. Symposium on Computational Geometry 1986: 61-71 BibTeX

[13]

Yannis E. Ioannidis: Universality of Serial Histograms. VLDB 1993: 256-267 BibTeX

[14]

Yannis E. Ioannidis, Viswanath Poosala: Balancing Histogram Optimality and Practicality for Query Result Size Estimation. SIGMOD Conference 1995: 233-244 BibTeX

[15]

H. V. Jagadish, Nick Koudas, S. Muthukrishnan, Viswanath Poosala, Kenneth C. Sevcik, Torsten Suel: Optimal Histograms with Quality Guarantees. VLDB 1998: 275-286 BibTeX

[16]

...

[17]

Maher Kaddoura, Sanjay Ranka, Albert Wang: Array Decompositions for Nonuniform Computational Environments. J. Parallel Distrib. Comput. 36(2): 91-105(1996) BibTeX

[18]

Sanjeev Khanna, S. Muthukrishnan, Mike Paterson: On Approximating Rectangle Tiling and Packing. SODA 1998: 384-393 BibTeX

[19]

Sanjeev Khanna, S. Muthukrishnan, Steven Skiena: Efficient Array Partitioning. ICALP 1997: 616-626 BibTeX

[20]

Robert Kooi: The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980
BibTeX

[21]

David Lichtenstein: Planar Formulae and Their Uses. SIAM J. Comput. 11(2): 329-343(1982) BibTeX

[22]

Nick Littlestone: Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm (Extended Abstract). FOCS 1987: 68-77 BibTeX

[23]

...

[24]

...

[25]

...

[26]

Joseph S. B. Mitchell: Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple New Method for the Geometric k-MST Problem. SODA 1996: 402-408 BibTeX

[27]

M. Muralikrishna, David J. DeWitt: Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988: 28-36 BibTeX

[28]

Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX

[29]

...

[30]

Viswanath Poosala, Yannis E. Ioannidis, Peter J. Haas, Eugene J. Shekita: Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conference 1996: 294-305 BibTeX

[31]

Viswanath Poosala: Histogram-Based Estimation Techniques in Database Systems. Ph.D. thesis, Univ. of Wisconsin-Madison 1997
BibTeX

[32]

Viswanath Poosala, Yannis E. Ioannidis: Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997: 486-495 BibTeX

[33]

Gregory Piatetsky-Shapiro, Charles Connell: Accurate Estimation of the Number of Tuples Satisfying a Condition. SIGMOD Conference 1984: 256-276 BibTeX

[34]

Emo Welzl: Partition Trees for Triangle Counting and Other Range Searching Problems. Symposium on Computational Geometry 1988: 23-33 BibTeX

Referenced by

1. Viswanath Poosala, Venkatesh Ganti, Yannis E. Ioannidis: Approximate Query Answering using Histograms. IEEE Data Eng. Bull. 22(4): 5-14(1999)
2. Viswanath Poosala, Venkatesh Ganti: Fast Approximate Answers to Aggregate Queries on a Data Cube. SSDBM 1999: 24-33
3. Swarup Acharya, Viswanath Poosala, Sridhar Ramaswamy: Selectivity Estimation in Spatial Databases. SIGMOD Conference 1999: 13-24