Worcester Polytechnic Institute Electronic Theses and Dissertations Collection

Title page for ETD etd-050511-105238


Document Typethesis
Author NameShastri, Avani
Email Address shastriavani66 at yahoo.co.in
URNetd-050511-105238
TitleMTopS: Multi-Query Optimization for Continuous Top-K Query Workloads
DegreeMS
DepartmentComputer Science
Advisors
  • Elke A. Rundensteiner, Advisor
  • Joseph Beck, Reader
  • Keywords
  • meta query strategy
  • MTopS
  • predicted top-k results
  • MTopList
  • MTopBand
  • multi top-k query
  • Date of Presentation/Defense2011-05-05
    Availability restricted

    Abstract

    A continuous top-k query retrieves the k most preferred objects from a data stream according to a given preference function. These queries are important for a broad spectrum of applications from web-based advertising, network traffic monitoring, to financial analysis. Given the nature of such applications, a data stream may be subjected at any given time to multiple top-k queries with varying parameter settings requested simultaneously by different users.

    This workload of simultaneous top-k queries must be executed efficiently to assure real time responsiveness. However, existing methods in the literature focus on optimizing single top-k query processing, thus would handle each query independently. They are thus not suitable for handling large numbers of such simultaneous top-k queries due to their unsustainable resource demands.

    In this thesis, we present a comprehensive framework, called MTopS for Multiple Top-K Optimized Processing System. MTopS achieves resource sharing at the query level by analyzing parameter settings of all queries in the workload, including window-specific parameters and top-k parameters. We further optimize the shared processing by identifying the minimal object set from the data stream that is both necessary and sufficient for top-k monitoring of all queries in the workload. Within this framework, we design the MTopBand algorithm that maintains the up-to-date top-k result set in the size of O (k), where k is the required top-k result set, eliminating the need for any recomputation.

    To overcome the overhead caused by MTopBand to maintain replicas of the top-k result set across sliding windows, we optimize this algorithm further by integrating these views into one integrated structure, called MTopList.

    Our associated top-k maintenance algorithm, also called MTopList algorithm, is able to maintain this linear integrated structure, thus able to efficiently answer all queries in the workload. MTopList is shown to be memory optimal because it maintains only the distinct objects that are part of top-k results of at least one query. Our experimental study, using real data streams from domains of stock trades and moving object monitoring, demonstrates that both the efficiency and scalability in the query workload of our proposed technique is superior to the state-of-the-art solutions.

    Files
  • (WPI)MSThesis.pdf

    (WPI) indicates that a file or directory is accessible from the WPI campus network only.


  • 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