Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-040311-153502


Document Typethesis
Author NameSrivastava, Shweta
Email Address shweta.sriv at gmail.com
URNetd-040311-153502
TitleLook Before You Leap: An Adaptive Processing Strategy For Multi-Criteria Decision Support Queries
DegreeMS
DepartmentComputer Science
Advisors
  • Elke A. Rundensteiner, Advisor
  • George T. Heineman, Reader
  • Keywords
  • Skyline
  • adaptive
  • partition
  • Date of Presentation/Defense2011-04-04
    Availability unrestricted

    Abstract

    In recent years, we have witnessed a massive acquisition of data and increasing need to support multi-criteria decision support (MCDS) queries efficiently. Pareto-optimal also known as skyline queries is a popular class of MCDS queries and has received a lot of attention resulting in a flurry of efficient skyline algorithms. The vast majority of such algorithms focus entirely on the input being a single data set. In this work, we provide an adaptive query evaluation technique --- AdaptiveSky that is able to reason at different levels of abstraction thereby effectively minimizing the two primary costs, namely the cost of generating join results and the cost of dominance comparisons to compute the final skyline of the join results.

    Our approach hinges on two key principles. First, in the input space -- we determine the abstraction levels dynamically at run time instead of assigning a static one at compile time that may or may not work for different data distributions. This is achieved by adaptively partitioning the input data as intermediate results are being generated thereby eliminating the need to access vast majority of the input tuples. Second, we incrementally build the output space, containing the final skyline, without generating a single join result.

    Our approach is able to reason about the final result space and selectively drill into regions in the output space that show promise in generating result tuples to avoid generation of results that do not contribute to the query result. In this effort, we propose two alternate strategies for reasoning, namely the Euclidean Distance method and the cost-benefit driven Dominance Potential method for reasoning. Our experimental evaluation demonstrates that AdaptiveSky shows superior performance over state-of-the-art techniques over benchmark data sets.

    Files
  • adaptive.pdf

  • Browse by Author | Browse by Department | Search all available ETDs

    [WPI] [Library] [Home] [Top]

    Questions? Email etd-questions@wpi.edu
    Maintained by webmaster@wpi.edu