On a model of indexability and its bounds for range queries

ABSTRACT

We develop a theoretical framework to characterize the hardness of indexing data sets on block-access memory devices like hard disks. We define an indexing workload by a data set and a set of potential queries. For a workload, we can construct an indexing scheme, which is a collection of fixed-sized subsets of the data. We identify two measures of efficiency for an indexing scheme on a workload: storage redundancy, r (how many times each item in the data set is stored), and access overhead, A (how many times more blocks than necessary does a query retrieve).For many interesting families of workloads, there exists a trade-off between storage redundancy and access overhead. Given a desired access overhead A, there is a minimum redundancy that any indexing scheme must exhibit. We prove a lower-bound theorem for deriving the minimum redundancy. By applying this theorem, we show interesting upper and lower bounds and trade-offs between A and r in the case of multidimensional range queries and set queries.

REFERENCES

• 1: Paul M. Aoki, Generalizing "Search'' in Generalized Search Trees (Extended Abstract), Proceedings of the Fourteenth International Conference on Data Engineering, p.380-389, February 23-27, 1998
• 2: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 3: L. Arge , J. S. Vitter, Optimal dynamic interval management in external memory, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.560, October 14-16, 1996
• 4: Omer Barkol , Yuval Rabani, Tighter bounds for nearest neighbor search and related problems in the cell probe model, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.388-396, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335350]
• 5: BAYER, R., AND MCCREIGHT, E. 1972. Organization and maintenance of large ordered indexes. Acta Inf. 1, 173-189.
• 6: 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
• 7: Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov, A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.305-311, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301325]
• 8: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 9: Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
• 10: Bernard Chazelle, Lower bounds for off-line range searching, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.733-740, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225291]
• 11: 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]
• 12: FIAT, A., AND SHAMIR, A. 1989. How to find a battleship. Networks 19, 361-371.
• 13: FREDMAN, M. L. 1980. The inherent complexity of dynamic data structures which accomodate range queries. In Proceedings of the IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., pp. 191-199.
• 14: FREDMAN, M. L. 1981. Lower bounds on the complexity of some optimal data structures. SIAM J. Comput. 10, 1-10.
• 15: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 16: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 17: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 18: JOHNSON, S. M. 1962. A new upper bound for error-correcting codes. IEEE Trans. Inf. Theory 8, 203- 207.
• 19: Paris Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey Scott Vitter, Indexing for data models with constraints and classes, Journal of Computer and System Sciences, v.52 n.3, p.589-612, June 1996 [doi>10.1006/jcss.1996.0043]
• 20: Paris C. Kanellakis , Sridhar Ramaswamy , Darren E. Vengroff , Jeffrey S. Vitter, Indexing for data models with constraints and classes (extended abstract), Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.233-243, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153884]
• 21: K. V. Ravi Kanth , Siva Ravada , Jayant Sharma , Jay Banerjee, Indexing medium-dimensionality data in Oracle, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.521-522, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 22: Marcel Kornacker, High-Performance Extensible Indexing, Proceedings of the 25th International Conference on Very Large Data Bases, p.699-708, September 07-10, 1999
• 23: Marcel Kornacker , C. Mohan , Joseph M. Hellerstein, Concurrency and recovery in generalized search trees, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.62-72, May 11-15, 1997, Tucson, Arizona, United States
• 24: Elias Koutsoupias , D. S. Taylor, Tight bounds for 2-dimensional indexing schemes, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-58, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275494]
• 25: Elias Koutsoupias , David Taylor, Indexing schemes for random points, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.596-602, January 17-19, 1999, Baltimore, Maryland, United States
• 26: MATOUSEK, J. 1999. Geometric Discrepancy. Springer-Verlag, New York.
• 27: Kurt Mehlhorn, Data structures and algorithms 3: multi-dimensional searching and computational geometry, Springer-Verlag New York, Inc., New York, NY, 1984
• 28: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.103-111, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225093]
• 29: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 30: Mark H. Nodine , Michael T. Goodrich , Jeffrey Scott Vitter, Blocking for external graph searching, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.222-232, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153880]
• 31: 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]
• 32: Sridhar Ramaswamy , Paris C. Kanellakis, OODB indexing by class-division, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.139-150, May 22-25, 1995, San Jose, California, United States
• 33: Sridhar Ramaswamy , Sairam Subramanian, Path caching (extended abstract): a technique for optimal external searching, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.25-35, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182595]
• 34: Betty Salzberg , Vassilis J. Tsotras, Comparison of access methods for time-evolving data, ACM Computing Surveys (CSUR), v.31 n.2, p.158-221, June 1999 [doi>10.1145/319806.319816]
• 35: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 36: Mehul A. Shah , Marcel Kornacker , Joseph M. Hellerstein, Amdb: A Visual Access Method Development Tool, Proceedings of the 1999 User Interfaces to Data Intensive Systems, p.130, September 05-06, 1999
• 37: Michiel H. M. Smid , Mark H. Overmars, Maintaining range trees in secondary memory. Part II: lower bounds, Acta Informatica, v.27 n.5, p.453-480, 1990 [doi>10.1007/BF00289019]
• 38: Sairam Subramanian , Sridhar Ramaswamy, The P-range tree: a new data structure for range searching in secondary memory, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.378-387, January 22-24, 1995, San Francisco, California, United States
• 39: TURAN, P. 1941. An extrenal problem in graph theory (in Hungarian). Mat. Fiz. Lapok. 48, 435-452.
• 40: Pravin M. Vaidya, Space-time trade-offs for orthogonal range queries, SIAM Journal on Computing, v.18 n.4, p.748-758, Aug. 1989 [doi>10.1137/0218051]
• 41: VAN LINT, J. H., AND WILSON, R. M. 1992. A Course in Combinatorics. Cambridge University Press, Cambridge, Mass.
• 42: Darren Erik Vengroff , Jeffrey Scott Vitter, Efficient 3-D range searching in external memory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.192-201, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237864]
• 43: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 44: Andrew Chi-Chih Yao, Should Tables Be Sorted?, Journal of the ACM (JACM), v.28 n.3, p.615-628, July 1981 [doi>10.1145/322261.322274]
• 45: Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802185]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Theory

Keywords:
Database, index, indexability, lower bounds, multidimensional, query, redundancy