An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table

Yuichi Sei; Kazutaka Matsuzaki; Shinichi Honiden

doi:10.1007/978-0-387-34735-6_13

An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table

Yuichi Sei^*, Kazutaka Matsuzaki, Shinichi Honiden

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Chapter

3 Citations (Scopus)

Abstract

In distributed hash tables, much communication traffic comes from multi-word searches. The aim of this work is to reduce the amount of traffic by using a bloom filter, which is a space-efficient probabilistic data structure used to test whether or not an element is a member of a set. However, bloom filters have a limited role if several sets have different numbers of elements. In the proposed method, extra data storage is generated when contents' keys are registered in a distributed hash table system. Accordingly, we propose a "divided bloom filter" to solve the problem of a normal bloom filter. Using the divided bloom filter, we aim to reduce both the amount of communication traffic and the amount of data storage.

Original language	English
Title of host publication	Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006
Subtitle of host publication	IFIP 19th Worm Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago Chile
Editors	Gonzalo Navarro, Leopolo Bertossi, Yoshiharu Kohayakawa
Pages	115-129
Number of pages	15
DOIs	https://doi.org/10.1007/978-0-387-34735-6_13
Publication status	Published - 2006
Externally published	Yes

Publication series

Name	IFIP International Federation for Information Processing
Volume	209
ISSN (Print)	1571-5736

ASJC Scopus subject areas

Information Systems and Management

Access to Document

10.1007/978-0-387-34735-6_13

Cite this

Sei, Y., Matsuzaki, K., & Honiden, S. (2006). An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table. In G. Navarro, L. Bertossi, & Y. Kohayakawa (Eds.), Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006: IFIP 19th Worm Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago Chile (pp. 115-129). (IFIP International Federation for Information Processing; Vol. 209). https://doi.org/10.1007/978-0-387-34735-6_13

An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table. / Sei, Yuichi; Matsuzaki, Kazutaka; Honiden, Shinichi.
Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006: IFIP 19th Worm Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago Chile. ed. / Gonzalo Navarro; Leopolo Bertossi; Yoshiharu Kohayakawa. 2006. p. 115-129 (IFIP International Federation for Information Processing; Vol. 209).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Sei, Y, Matsuzaki, K & Honiden, S 2006, An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table. in G Navarro, L Bertossi & Y Kohayakawa (eds), Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006: IFIP 19th Worm Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago Chile. IFIP International Federation for Information Processing, vol. 209, pp. 115-129. https://doi.org/10.1007/978-0-387-34735-6_13

Sei Y, Matsuzaki K, Honiden S. An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table. In Navarro G, Bertossi L, Kohayakawa Y, editors, Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006: IFIP 19th Worm Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago Chile. 2006. p. 115-129. (IFIP International Federation for Information Processing). doi: 10.1007/978-0-387-34735-6_13

Sei, Yuichi ; Matsuzaki, Kazutaka ; Honiden, Shinichi. / An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table. Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006: IFIP 19th Worm Computer Congress, TC-1, Foundations of Computer Science, August 23-24, 2006, Santiago Chile. editor / Gonzalo Navarro ; Leopolo Bertossi ; Yoshiharu Kohayakawa. 2006. pp. 115-129 (IFIP International Federation for Information Processing).

@inbook{c9e51ce4e463479a962d3b6e5f8d2859,

title = "An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table",

abstract = "In distributed hash tables, much communication traffic comes from multi-word searches. The aim of this work is to reduce the amount of traffic by using a bloom filter, which is a space-efficient probabilistic data structure used to test whether or not an element is a member of a set. However, bloom filters have a limited role if several sets have different numbers of elements. In the proposed method, extra data storage is generated when contents' keys are registered in a distributed hash table system. Accordingly, we propose a {"}divided bloom filter{"} to solve the problem of a normal bloom filter. Using the divided bloom filter, we aim to reduce both the amount of communication traffic and the amount of data storage.",

author = "Yuichi Sei and Kazutaka Matsuzaki and Shinichi Honiden",

year = "2006",

doi = "10.1007/978-0-387-34735-6_13",

language = "English",

isbn = "0387346333",

series = "IFIP International Federation for Information Processing",

pages = "115--129",

editor = "Gonzalo Navarro and Leopolo Bertossi and Yoshiharu Kohayakawa",

booktitle = "Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006",

}

TY - CHAP

T1 - An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table

AU - Sei, Yuichi

AU - Matsuzaki, Kazutaka

AU - Honiden, Shinichi

PY - 2006

Y1 - 2006

N2 - In distributed hash tables, much communication traffic comes from multi-word searches. The aim of this work is to reduce the amount of traffic by using a bloom filter, which is a space-efficient probabilistic data structure used to test whether or not an element is a member of a set. However, bloom filters have a limited role if several sets have different numbers of elements. In the proposed method, extra data storage is generated when contents' keys are registered in a distributed hash table system. Accordingly, we propose a "divided bloom filter" to solve the problem of a normal bloom filter. Using the divided bloom filter, we aim to reduce both the amount of communication traffic and the amount of data storage.

AB - In distributed hash tables, much communication traffic comes from multi-word searches. The aim of this work is to reduce the amount of traffic by using a bloom filter, which is a space-efficient probabilistic data structure used to test whether or not an element is a member of a set. However, bloom filters have a limited role if several sets have different numbers of elements. In the proposed method, extra data storage is generated when contents' keys are registered in a distributed hash table system. Accordingly, we propose a "divided bloom filter" to solve the problem of a normal bloom filter. Using the divided bloom filter, we aim to reduce both the amount of communication traffic and the amount of data storage.

UR - http://www.scopus.com/inward/record.url?scp=33845643139&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33845643139&partnerID=8YFLogxK

U2 - 10.1007/978-0-387-34735-6_13

DO - 10.1007/978-0-387-34735-6_13

M3 - Chapter

AN - SCOPUS:33845643139

SN - 0387346333

SN - 9780387346335

T3 - IFIP International Federation for Information Processing

SP - 115

EP - 129

BT - Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006

A2 - Navarro, Gonzalo

A2 - Bertossi, Leopolo

A2 - Kohayakawa, Yoshiharu

ER -

An algorithm to reduce the communication traffic for multi-word searches in a distributed hash table

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this