The power-method: a comprehensive estimation technique for multi-dimensional queries

ABSTRACT

Existing estimation approaches for multi-dimensional databases often rely on the assumption that data distribution in a small region is uniform, which seldom holds in practice. Moreover, their applicability is limited to specific estimation tasks under certain distance metric. This paper develops the Power-method, a comprehensive technique applicable to a wide range of query optimization problems under various metrics. The Power-method eliminates the local uniformity assumption and is accurate even in scenarios where existing approaches completely fail. Furthermore, it performs estimation by evaluating only one simple formula with minimal computational overhead. Extensive experiments confirm that the Power-method outperforms previous techniques in terms of accuracy and applicability to various optimization scenarios.

REFERENCES

• 1: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Aref, W., Samet, H. A Cost Model for Query Optimization Using R-Trees. ACM GIS, 1994.
• 3: Ning An , Zhen-Yu Yang , Anand Sivasubramaniam, Selectivity Estimation for Spatial Joins, Proceedings of the 17th International Conference on Data Engineering, p.368-375, April 02-06, 2001
• 4: Christian Böhm, A cost model for query processing in high dimensional data spaces, ACM Transactions on Database Systems (TODS), v.25 n.2, p.129-178, June 2000 [doi>10.1145/357775.357776]
• 5: Berchtold, S., Bohm, C., Keim, D.A., Kriegel, H. A Cost Model for Nearest Neighbor Search in High-Dimensional Data Space. PODS, 1997.
• 6: Brian Babcock , Surajit Chaudhuri , Gautam Das, Dynamic sample selection for approximate query processing, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872822]
• 7: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• 8: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 9: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 10: Björn Blohsfeld , Dieter Korus , Bernhard Seeger, A comparison of selectivity estimators for range queries on metric attributes, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.239-250, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 11: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 12: Surajit Chaudhuri , Gautam Das , Mayur Datar , Rajeev Motwani , Vivek R. Narasayya, Overcoming Limitations of Sampling for Aggregation Queries, Proceedings of the 17th International Conference on Data Engineering, p.534-542, April 02-06, 2001
• 13: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.295-306, May 21-24, 2001, Santa Barbara, California, United States
• 14: Amol Deshpande , Minos Garofalakis , Rajeev Rastogi, Independence is good: dependency-based histogram synopses for high-dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.199-210, May 21-24, 2001, Santa Barbara, California, United States
• 15: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 16: Christos Faloutsos , Bernhard Seeger , Agma Traina , Caetano Traina, Jr., Spatial join selectivity using power laws, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.177-188, May 15-18, 2000, Dallas, Texas, United States
• 17: Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.463-474, May 15-18, 2000, Dallas, Texas, United States
• 18: Jermaine, C. Making Sampling Robust with APA. VLDB, 2003.
• 19: Jin, J., An, N., Sivasubramaniam, A. Analyzing Range Queries on Spatial Data. ICDE, 2000.
• 20: Ju-Hong Lee , Deok-Hwan Kim , Chin-Wan Chung, Multi-dimensional selectivity estimation using compressed histogram information, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 21: Lin, X., Liu, Q., Yuan, Y., Zhou, X. Multiscale histograms: Summarizing topological relations in large spatial datasets. VLDB, 2003.
• 22: Muralikrishna, M., DeWitt, D. Equi-Depth Histograms for Estimating Selectivity Factors for Multi-Dimensional Queries. SIGMOD, 1988.
• 23: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000
• 24: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 25: Frank Olken , Doron Rotem, Random Sampling from Database Files: A Survey, Proceedings of the 5th International Conference SSDBM on Statistical and Scientific Database Management, p.92-111, April 03-05, 1990
• 26: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• 27: Christopher R. Palmer , Christos Faloutsos, Density biased sampling: an improved method for data mining and clustering, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.82-92, May 15-18, 2000, Dallas, Texas, United States
• 28: Pagel, B., Korn, F., Faloutsos, C. Deflating the Dimensionality Curse using Multiple Fractal Dimensions. ICDE, 2000.
• 29: Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153878]
• 30: Sun, C., Agrawal, D., El Abbadi, A. Exploring Spatial Datasets with Histograms. ICDE, 2002.
• 31: Http://www.census.gov/geo/www/tiger/
• 32: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 33: Yannis Theodoridis , Emmanuel Stefanakis , Timos Sellis, Efficient Cost Models for Spatial Queries Using R-Trees, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.19-32, January 2000 [doi>10.1109/69.842247]
• 34: Yi-Leh Wu , Divyakant Agrawal , Amr El Abbadi, Applying the golden rule of sampling for query estimation, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.449-460, May 21-24, 2001, Santa Barbara, California, United States
• 35: Min Wang , Jeffrey Scott Vitter , Lipyeow Lim , Sriram Padmanabhan, Wavelet-Based Cost Estimation for Spatial Queries, Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, p.175-196, July 12-15, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Theory