Efficient execution of multiple query workloads in data analysis applications

ABSTRACT

Applications that analyze, mine, and visualize large datasets are considered an important class of applications in many areas of science, engineering, and business. Queries commonly executed in data analysis applications often involve user-defined processing of data and application-specific data structures. If data analysis is employed in a collaborative environment, the data server should execute multiple such queries simultaneously to minimize the response time to clients. In this paper we present the design of a runtime system for executing multiple query workloads on a shared-memory machine. We describe experimental results using an application for browsing digitized microscopy images.

REFERENCES

• 1: Anurag Acharya , Mustafa Uysal , Robert Bennett , Assaf Mendelson , Michael Beynon , Jeff Hollingsworth , Joel Saltz , Alan Sussman, Tuning the performance of I/O-intensive parallel applications, Proceedings of the fourth workshop on I/O in parallel and distributed systems: part of the federated computing research conference, p.15-27, May 27-27, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/236017.236027]
• 2: A. Afework, M. D. Beynon, F. Bustamante, A. Demarzo, R. Ferreira, R. Miller, M. Silberman, J. Saltz, A. Sussman, and H. Tsang. Digital dynamic telepathology --- the Virtual Microscope. In Proceedings of the 1998 AMIA Annual Fall Symposium. American Medical Informatics Association, Nov. 1998.
• 3: Michael D. Beynon , Alan Sussman , Joel Saltz, Performance impact of proxies in data intensive client-server applications, Proceedings of the 13th international conference on Supercomputing, p.383-390, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305216]
• 4: Michael D. Beynon , Alan Sussman , Tahsin Kurc , Joel Saltz, Optimizing Execution of Component-based Applications using Group Instances, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.56, May 15-18, 2001
• 5: Upen S. Chakravarthy , Jack Minker, Multiple Query Processing in Deductive Databases using Query Graphs, Proceedings of the 12th International Conference on Very Large Data Bases, p.384-391, August 25-28, 1986
• 6: C. Chang, T. Kurc, A. Sussman, U. Catalyurek, and J. Saltz. A hypergraph-based workload partitioning strategy for parallel data aggregation. In Proceedings of the Eleventh SIAM Conference on Parallel Processing for Scientific Computing. SIAM, Mar. 2001.
• 7: Optimizing Retrieval and Processing of Multi-Dimensional Scientific Datasets, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.405, May 01-05, 2000
• 8: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 9: Neil Dewhurst , Simon H. Lavington, Knowledge Discovery from Client-Server Databases, Proceedings of the Second European Symposium on Principles of Data Mining and Knowledge Discovery, p.300-308, September 23-26, 1998
• 10: Parke Godfrey , Jarek Gryz, Answering Queries by Semantic Caches, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.485-498, August 30-September 03, 1999
• 11: Joseph M. Hellerstein , Jeffrey F. Naughton, Query execution techniques for caching expensive methods, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.423-434, June 04-06, 1996, Montreal, Quebec, Canada
• 12: Anant Jhingran, A Performance Study of Query Optimization Algorithms on a Database System Supporting Procedures, Proceedings of the 14th International Conference on Very Large Data Bases, p.88-99, August 29-September 01, 1988
• 13: Myong H. Kang , Henry G. Dietz , Bharat Bhargava, Multiple-query optimization at algorithm-level, Data & Knowledge Engineering, v.14 n.1, p.57-75, Nov. 1994 [doi>10.1016/0169-023X(94)90009-4 ]
• 14: Tahsin Kurc , Chialin Chang , Renato Ferreira , Alan Sussman , Joel Saltz, Querying very large multi-dimensional datasets in ADR, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.12-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331544]
• 15: Manish Mehta , Valery Soloviev , David J. DeWitt, Batch Scheduling in Parallel Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.400-410, April 19-23, 1993
• 16: Graham Hamilton , Yousef A. Khalidi , Michael N. Nelson, A Framework for Caching in an Object-Oriented System, Sun Microsystems, Inc., Mountain View, CA, 1993
• 17: Arnon Rosenthal , Upen S. Chakravarthy, Anatomy of a Mudular Multiple Query Optimizer, Proceedings of the 14th International Conference on Very Large Data Bases, p.230-239, August 29-September 01, 1988
• 18: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 19: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 20: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 21: Kyuseok Shim , Timos Sellis , Dana Nau, Improvements on a heuristic algorithm for multiple-query optimization, Data & Knowledge Engineering, v.12 n.2, p.197-222, March 1994 [doi>10.1016/0169-023X(94)90014-0 ]
• 22: Kian-Lee Tan , Hongjun Lu, Workload scheduling for multiple query processing, Information Processing Letters, v.55 n.5, p.251-257, Sept. 15, 1995 [doi>10.1016/0020-0190(95)00088-T ]
• 23: William E Voss, Caching Derived Data in Object-Oriented Databases, and An Intelligent System Design for Selecting Their Materialization Strategies, University of Illinois at Urbana-Champaign, Champaign, IL, 1998
• 24: Jian Yang , Kamalakar Karlapalem , Qing Li, Algorithms for Materialized View Design in Data Warehousing Environment, Proceedings of the 23rd International Conference on Very Large Data Bases, p.136-145, August 25-29, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Shared memory

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms, Design, Performance