Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores

Xiangjun Peng; Qingfeng Wang; Xu Sun; Chunye Gong; Yaohua Wang

doi:10.1109/PDCAT46702.2019.00083

Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores

Xiangjun Peng
, Qingfeng Wang
, Xu Sun
, Chunye Gong
, Yaohua Wang

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

206 Downloads (Pure)

Abstract

User-Item (U-I) matrix has been used as the dominant data infrastructure of Collaborative Filtering (CF). To reduce space consumption in runtime and storage, caused by data sparsity and growing need to accommodate side information in CF design, one needs to go beyond the U-I Matrix. In this paper, we took a case study of Succinct Representations in Collaborative Filtering, rather than using a U-I Matrix. Our key insight is to introduce Succinct Data Structures as a new infrastructure of CF. Towards this, we implemented a User-based K-Nearest-Neighbor CF prototype via Wavelet Tree, by first designing a Accessible Compressed Documents (ACD) to compress U-I data in Wavelet Tree, which is efficient in both storage and runtime. Then, we showed that ACD can be applied to develop an efficient intersection algorithm without decompression, by taking advantage of ACD's characteristics. We evaluated our design on 1,000 cores of Tianhe-II supercomputer, with one of the largest public data set ml-20m. The results showed that our prototype could achieve 3.7 minutes on average to deliver the results.

Original language	English
Title of host publication	Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019
Editors	Hui Tian, Hong Shen, Wee Lum Tan
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	427-432
Number of pages	6
ISBN (Electronic)	9781728126166
DOIs	https://doi.org/10.1109/PDCAT46702.2019.00083
Publication status	Published - Dec 2019
Event	20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019 - Gold Coast, Australia Duration: 5 Dec 2019 → 7 Dec 2019

Publication series

Name	Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019

Conference

Conference	20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019
Country/Territory	Australia
City	Gold Coast
Period	5/12/19 → 7/12/19

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 15 Life on Land

Free Keywords

Collaborative filtering
Succinct data structures
Supercomputing

ASJC Scopus subject areas

Computer Networks and Communications
Computer Science Applications
Hardware and Architecture

Access to Document

10.1109/PDCAT46702.2019.00083

256 Succinct representations in collaborative filtering A case study using wavelet tree on 1,000 coresAccepted author manuscript, 1.14 MBLicence: CC BY

Cite this

Peng, X., Wang, Q., Sun, X., Gong, C., & Wang, Y. (2019). Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores. In H. Tian, H. Shen, & W. L. Tan (Eds.), Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019 (pp. 427-432). Article 9029130 (Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/PDCAT46702.2019.00083

Peng, Xiangjun ; Wang, Qingfeng ; Sun, Xu et al. / Succinct representations in collaborative filtering : A case study using wavelet tree on 1,000 cores. Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019. editor / Hui Tian ; Hong Shen ; Wee Lum Tan. Institute of Electrical and Electronics Engineers Inc., 2019. pp. 427-432 (Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019).

@inproceedings{f827796561884ce7a37678b7ccc584a8,

title = "Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores",

abstract = "User-Item (U-I) matrix has been used as the dominant data infrastructure of Collaborative Filtering (CF). To reduce space consumption in runtime and storage, caused by data sparsity and growing need to accommodate side information in CF design, one needs to go beyond the U-I Matrix. In this paper, we took a case study of Succinct Representations in Collaborative Filtering, rather than using a U-I Matrix. Our key insight is to introduce Succinct Data Structures as a new infrastructure of CF. Towards this, we implemented a User-based K-Nearest-Neighbor CF prototype via Wavelet Tree, by first designing a Accessible Compressed Documents (ACD) to compress U-I data in Wavelet Tree, which is efficient in both storage and runtime. Then, we showed that ACD can be applied to develop an efficient intersection algorithm without decompression, by taking advantage of ACD's characteristics. We evaluated our design on 1,000 cores of Tianhe-II supercomputer, with one of the largest public data set ml-20m. The results showed that our prototype could achieve 3.7 minutes on average to deliver the results.",

keywords = "Collaborative filtering, Succinct data structures, Supercomputing",

author = "Xiangjun Peng and Qingfeng Wang and Xu Sun and Chunye Gong and Yaohua Wang",

note = "Publisher Copyright: {\textcopyright} 2019 IEEE.; 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019 ; Conference date: 05-12-2019 Through 07-12-2019",

year = "2019",

month = dec,

doi = "10.1109/PDCAT46702.2019.00083",

language = "English",

series = "Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "427--432",

editor = "Hui Tian and Hong Shen and Tan, \{Wee Lum\}",

booktitle = "Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019",

address = "United States",

}

Peng, X, Wang, Q , Sun, X, Gong, C & Wang, Y 2019, Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores. in H Tian, H Shen & WL Tan (eds), Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019., 9029130, Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019, Institute of Electrical and Electronics Engineers Inc., pp. 427-432, 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019, Gold Coast, Australia, 5/12/19. https://doi.org/10.1109/PDCAT46702.2019.00083

Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores. / Peng, Xiangjun; Wang, Qingfeng ; Sun, Xu et al.
Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019. ed. / Hui Tian; Hong Shen; Wee Lum Tan. Institute of Electrical and Electronics Engineers Inc., 2019. p. 427-432 9029130 (Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Succinct representations in collaborative filtering

T2 - 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019

AU - Peng, Xiangjun

AU - Wang, Qingfeng

AU - Sun, Xu

AU - Gong, Chunye

AU - Wang, Yaohua

PY - 2019/12

Y1 - 2019/12

N2 - User-Item (U-I) matrix has been used as the dominant data infrastructure of Collaborative Filtering (CF). To reduce space consumption in runtime and storage, caused by data sparsity and growing need to accommodate side information in CF design, one needs to go beyond the U-I Matrix. In this paper, we took a case study of Succinct Representations in Collaborative Filtering, rather than using a U-I Matrix. Our key insight is to introduce Succinct Data Structures as a new infrastructure of CF. Towards this, we implemented a User-based K-Nearest-Neighbor CF prototype via Wavelet Tree, by first designing a Accessible Compressed Documents (ACD) to compress U-I data in Wavelet Tree, which is efficient in both storage and runtime. Then, we showed that ACD can be applied to develop an efficient intersection algorithm without decompression, by taking advantage of ACD's characteristics. We evaluated our design on 1,000 cores of Tianhe-II supercomputer, with one of the largest public data set ml-20m. The results showed that our prototype could achieve 3.7 minutes on average to deliver the results.

AB - User-Item (U-I) matrix has been used as the dominant data infrastructure of Collaborative Filtering (CF). To reduce space consumption in runtime and storage, caused by data sparsity and growing need to accommodate side information in CF design, one needs to go beyond the U-I Matrix. In this paper, we took a case study of Succinct Representations in Collaborative Filtering, rather than using a U-I Matrix. Our key insight is to introduce Succinct Data Structures as a new infrastructure of CF. Towards this, we implemented a User-based K-Nearest-Neighbor CF prototype via Wavelet Tree, by first designing a Accessible Compressed Documents (ACD) to compress U-I data in Wavelet Tree, which is efficient in both storage and runtime. Then, we showed that ACD can be applied to develop an efficient intersection algorithm without decompression, by taking advantage of ACD's characteristics. We evaluated our design on 1,000 cores of Tianhe-II supercomputer, with one of the largest public data set ml-20m. The results showed that our prototype could achieve 3.7 minutes on average to deliver the results.

KW - Collaborative filtering

KW - Succinct data structures

KW - Supercomputing

UR - https://www.scopus.com/pages/publications/85083157730

U2 - 10.1109/PDCAT46702.2019.00083

DO - 10.1109/PDCAT46702.2019.00083

M3 - Conference contribution

AN - SCOPUS:85083157730

T3 - Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019

SP - 427

EP - 432

BT - Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019

A2 - Tian, Hui

A2 - Shen, Hong

A2 - Tan, Wee Lum

PB - Institute of Electrical and Electronics Engineers Inc.

Y2 - 5 December 2019 through 7 December 2019

ER -

Peng X, Wang Q , Sun X, Gong C, Wang Y. Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores. In Tian H, Shen H, Tan WL, editors, Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019. Institute of Electrical and Electronics Engineers Inc. 2019. p. 427-432. 9029130. (Proceedings - 2019 20th International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2019). doi: 10.1109/PDCAT46702.2019.00083

Succinct representations in collaborative filtering: A case study using wavelet tree on 1,000 cores

Abstract

Publication series

Conference

UN SDGs

Free Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this