Mercury: Supporting Scalable Multi-Attribute Range Queries

@inproceedings{2004-Bharambe-sigcomm,
    author = "Bharambe, Ashwin and Agrawal, Mukesh and Seshan, Srinivasan",
    title = "Mercury: Supporting Scalable Multi-Attribute Range Queries",
    year = "2004",
    isbn = "1581138628",
    publisher = "Association for Computing Machinery",
    address = "New York, NY, USA",
    url = "https://doi.org/10.1145/1015467.1015507",
    doi = "10.1145/1015467.1015507",
    abstract = "This paper presents the design of Mercury, a scalable protocol for supporting multi-attribute range-based searches. Mercury differs from previous range-based query systems in that it supports multiple attributes as well as performs explicit load balancing. To guarantee efficient routing and load balancing, Mercury uses novel light-weight sampling mechanisms for uniformly sampling random nodes in a highly dynamic overlay network. Our evaluation shows that Mercury is able to achieve its goals of logarithmic-hop routing and near-uniform load balancing.We also show that Mercury can be used to solve a key problem for an important class of distributed applications: distributed state maintenance for distributed games. We show that the Mercury-based solution is easy to use, and that it reduces the game's messaging overheard significantly compared to a na\{\i}ve approach.",
    booktitle = "ACM SIGCOMM Conference",
    pages = "353–366",
    numpages = "14",
    keywords = "range queries, random sampling, load balancing, distributed hash tables, peer-to-peer systems",
    location = "Portland, Oregon, USA",
    month = "August",
    category = "DistApps",
    series = "SIGCOMM '04"
}