On the generation of 2-dimensional index workloads

Joseph M. Hellerstein, Lisa Hellerstein, George Kollios

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    A large number of database index structures have been proposed over the last two decades, and little consensus has emerged regarding their relative e_ectiveness. In order to empirically evaluate these indexes, it is helpful to have methodologies for generating random queries for performance testing. In this paper we propose a domain-independent approach to the generation of random queries: choose randomly among all logically distinct queries. We investigate this idea in the context of range queries over 2-dimensional points. We present an algorithm that chooses randomly among logically distinct 2-d range queries. It has constant-time expected performance over uniformly distributed data, and exhibited good performance in experiments over a variety of real and synthetic data sets. We observe nonuniformities in the way randomly chosen logical 2-d range queries are distributed over a variety of spatial properties. This raises questions about the quality of the workloads generated from such queries. We contrast our approach with previous work that generates workloads of random spatial ranges, and we sketch directions for future work on the robust generation of workloads for studying index performance.

    Original languageEnglish (US)
    Title of host publicationDatabase Theory - ICDT 1999 - 7th International Conference, Proceedings
    EditorsPeter Buneman, Catriel Beeri
    PublisherSpringer Verlag
    Number of pages18
    ISBN (Print)3540654526, 9783540654520
    StatePublished - 1998
    Event7th International Conference on Database Theory, ICDT 1999 - Jerusalem, Israel
    Duration: Jan 10 1999Jan 12 1999

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Other7th International Conference on Database Theory, ICDT 1999

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • General Computer Science


    Dive into the research topics of 'On the generation of 2-dimensional index workloads'. Together they form a unique fingerprint.

    Cite this