NEST: Locality-aware approximate query service for cloud computing

Yu Hua, Bin Xiao, Xue Liu

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

22 Citations (Scopus)

Abstract

Cloud computing applications face the challenges of dealing with a huge volume of data that needs the support of fast approximate queries to enhance system scalability and improve quality of service, especially when users are not aware of exact query inputs. Locality-Sensitive Hashing (LSH) can support the approximate queries that unfortunately suffer from imbalanced load and space inefficiency among distributed data servers, which severely limits the query accuracy and incurs long query latency between users and cloud servers. In this paper, we propose a novel scheme, called NEST, which offers ease-of-use and cost-effective approximate query service for cloud computing. The novelty of NEST is to leverage cuckoo-driven locality-sensitive hashing to find similar items that are further placed closely to obtain load-balancing buckets in hash tables. NEST hence carries out flat and manageable addressing in adjacent buckets, and obtains constant-scale query complexity even in the worst case. The benefits of NEST include the increments of space utilization and fast query response. Theoretical analysis and extensive experiments in a large-scale cloud testbed demonstrate the salient properties of NEST to meet the needs of approximate query service in cloud computing environments.
Original languageEnglish
Title of host publication2013 Proceedings IEEE INFOCOM 2013
Pages1303-1311
Number of pages9
DOIs
Publication statusPublished - 2 Sep 2013
Event32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013 - Turin, Italy
Duration: 14 Apr 201319 Apr 2013

Conference

Conference32nd IEEE Conference on Computer Communications, IEEE INFOCOM 2013
Country/TerritoryItaly
CityTurin
Period14/04/1319/04/13

ASJC Scopus subject areas

  • Computer Science(all)
  • Electrical and Electronic Engineering

Cite this