Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/43610
Title: The design and implementations of locality-aware approximate queries in hybrid storage systems
Authors: Hua, Y
Xiao, B 
Liu, X
Feng, D
Keywords: Approximate queries
Hybrid storage systems
Locality
Issue Date: 2015
Publisher: Institute of Electrical and Electronics Engineers
Source: IEEE transactions on parallel and distributed systems, 2015, v. 26, no. 11, 6948249, p. 3194-3207 How to cite?
Journal: IEEE transactions on parallel and distributed systems 
Abstract: Cloud computing applications face the challenges of dealing with a huge volume of data that needs the support of accurate and fast approximate queries to enhance system scalability and improve quality of service. 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 easy-to-use and cost-effective approximate queries for cloud computing. The novelty of NEST is to leverage cuckoo-driven locality-sensitive hashing to find similar items that are further placed closely through cuckoo-driven method 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. Moreover, due to the salient property of flat addressing in NEST, we implement NEST design in a real hybrid storage system, which consists of DRAM, SSD, and hard disk. The flat addressing allows efficient operations in SSD to improve system performance. We argue that a proper ' division of labor' among DRAM, SSD, and hard disk in the hybrid and heterogeneous storage hierarchy is desperately needed to strike an optimal balance to remove the indexing bottleneck. Theoretical analysis and extensive experiments (on LANL and Microsoft metadata) in a large-scale cloud testbed demonstrate the salient properties of NEST to meet the needs of approximate query service in cloud computing environments. We have offered open-source codes of NEST for public use.
URI: http://hdl.handle.net/10397/43610
ISSN: 1045-9219 (print)
1558-2183 (online)
DOI: 10.1109/TPDS.2014.2367497
Appears in Collections:Journal/Magazine Article

Access
View full-text via PolyU eLinks SFX Query
Show full item record

SCOPUSTM   
Citations

2
Last Week
1
Last month
Citations as of Apr 15, 2017

WEB OF SCIENCETM
Citations

2
Last Week
0
Last month
Citations as of Apr 20, 2017

Page view(s)

6
Last Week
0
Last month
Checked on Apr 23, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.