Data structures for dynamic queries: an analytical and experimental evaluation

ABSTRACT

Dynamic Queries is a querying technique for doing range search on multi-key data sets. It is a direct manipulation mechanism where the query is formulated using graphical widgets and the results are displayed graphically preferably within 100 milliseconds.This paper evaluates four data structures, the multilist, the grid file, k-d tree and the quad tree used to organize data in high speed storage for dynamic queries. The effect of factors like size, distribution and dimensionality of data on the storage overhead and the speed of search is explored. Analytical models for estimating the storage and the search overheads are presented, and verified to be correct by empirical data. Results indicate that multilists are suitable for small (few thousand points) data sets irrespective of the data distribution. For large data sets the grid files are excellent for uniformly distributed data, and trees are good for skewed data distributions. There was no significant difference in performance between the tree structures.

REFERENCES

• 1: Christopher Ahlberg , Christopher Williamson , Ben Shneiderman, Dynamic queries for information exploration: an implementation and evaluation, Proceedings of the SIGCHI conference on Human factors in computing systems, p.619-626, May 03-07, 1992, Monterey, California, United States [doi>10.1145/142750.143054]
• 2: D. A. Beckley , M. W. Evens , V. K. Raman, Multikey retrieval from K-d trees and QUAD-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.291-301, May 1985, Austin, Texas, United States
• 3: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 4: J. L. Bentley and D. F. Stauat, "Analysis of Range Searches in Quad Trees", Information Processing Letters, Vol. 3, No. 6, 1975, pp. 17&173.
• 5: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• 6: J. Bentley and H. Maurer, "Efficient Worst-Case Data Strocturn for Range Searching", Acta Informatica, Vol. 13, No. 2, 1980, pp. 158168.
• 7: Christos Faloutsos , Pravin Bhagwat, Declustering using fractals, Proceedings of the second international conference on Parallel and distributed information systems, p.18-25, January 1993, San Diego, California, United States
• 8: R. A. Fiukel and J. L. Bentley, "Quad Trees, A Data Structure for Retrievd on Compoeite Keys", Acto Iaformatico, Vol. 4, 1974, pp. l-9.
• 9: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• 10: 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
• 11: V. Jaiu and B. Sbneiderman, "Data Structures for Dynamic Queries: Au Andyticd and Experimental Evaluation", CfAR Technical Report, University of Maryland, College Park, No. CAR-TR-685, September 1993.
• 12: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 13: D. T. Lee and C. K. Wang, "Worst-Case Analysis for Region and Partial Region Searches in Multidimensional Binary Sesrch pees and Bdauced Quad 'Bees", Acta Informatica, Vol. 9, 1977, pp. 2829.
• 14: David Lomet, A review of recent work on multi-attribute access methods, ACM SIGMOD Record, v.21 n.3, p.56-63, Sept. 1992 [doi>10.1145/140979.141006]
• 15: V. Y. Lum, Multi-attribute retrieval with combined indexes, Communications of the ACM, v.13 n.11, p.660-665, Nov 1970 [doi>10.1145/362790.362794]
• 16: 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]
• 17: Mireille Regnier, Analysis of grid file algorithms, BIT, v.25 n.2, p.335-358, 1985 [doi>10.1007/BF01934379]
• 18: Phyllis Reisner, Human Factors Studies of Database Query Languages: A Survey and Assessment, ACM Computing Surveys (CSUR), v.13 n.1, p.13-31, March 1981 [doi>10.1145/356835.356837]
• 19: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 20: P. Scheuermann and M. Ouksel, "Multidimensional B-Trees for Associative Searching in Database Systema", Information Systems, Vol. 7, No. 2, 1982, pp. 128137.
• 21: B. Shneidermau, "Direct Manipulation: A Step Beyond Programming Languages", IEEE Comprter, Vol. 16, No. 8, Augut 1983, pp. 57-69.
• 22: Ben Shneiderman, Designing the user interface (2nd ed.): strategies for effective human-computer interaction, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 23: Christopher Williamson , Ben Shneiderman, The dynamic HomeFinder: evaluating dynamic queries in a real-estate information exploration system, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.338-346, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133216]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Interaction styles (e.g., commands, menus, forms, direct manipulation)

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Arrays; Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Design, Languages, Performance