Stebalien
commented
4 years ago I'm having trouble finding:
- What you're actually proposing other than "semantic DHT".
- A strong motivation for your proposal. I.e., use-cases.
- A concrete description of what you intend to do.
As far as I can tell, this proposal boils down to:
- KV DHTs are limited.
- We should have a semantic DHT.
- We could implement this DHT by mapping documents into a vector space and mapping this vector space onto a set of nodes on the network.
But that took quite a bit of digging.
If you want to generate a discussion, I'd recommend:
- Removing all the background on DHTs. It's not relevant outside of an academic paper where you need to prove that you've made something new.
- Start with a proposal: One or two sentences stating what you want to build.
- Next, motivate your proposal. Provide examples of systems you could build with it, etc. Please use ample punctuation and bullet points.
- Finally, describe how you'd build it.
tarzaa1
aschmahmann
Hi there,
I have this idea for a peer-to-peer network construction technique and a lookup function that would enhance content-addressing by mapping data to high-dimensional vectors instead of purely logical keys or hashes.
I read the contributing document and under Protocol Design it says:
When considering protocol design proposals, we are looking for:
Please note that protocol design is hard, and meticulous work. You may need to review existing literature and think through generalized use cases.
So here we go:
A description of the problem this design proposal solves: DHTs offer an efficient distributed data structure accompanied by multiple proposed methods to dynamically partition and traverse the underlying logical keyspace. Just like hash tables, DHTs are used to store and retrieve key-value pairs. Yet, the partitioning of the keyspace allows for reaching any node in the network in a logarithmic number of steps as a function of the network size. Research solutions such as Chord [1], Pastry [2], CAN [3], and Kademlia [4], all offer a Key-based routing primitive (KBR) that routes a message m with key x to the node responsible for key x. This requires that each node maintains enough information about nodes responsible for key-space partitions allowing deterministic routing. The routing primitive works by hashing the identifier of a data item and mapping it to a location in the keyspace. By choosing a large enough size of the keyspace along with an appropriate hash function, solutions can guarantee the uniqueness of each generated key, hence, this guarantees an exact-match every time a participant attempts to store or retrieve a data item. we identify that having a purely logical keyspace that has no physical properties, accompanied by an exact-match KBR primitive, results in a limitation when attempting to approximately match two semantically related terms. Assuming that the rendezvous node maintains the key for the term "couch", if a user attempts to fetch relevant data by routing towards the key for "sofa". The KBR primitive will probably route the message to a distant node in the network.
Review of Existing Solutions: Chord [1] is a distributed lookup protocol and algorithm for constructing, maintaining, and operating a DHT. Chord provides a distributed computation of a hash function mapping m-bit keys to nodes using Consistent Hashing. Keys are ordered along an identifier circle modulo 2^m. Key k is assigned to the first node whose identifier is equal to or follows k in the identifiers space. To enable scalable key location, each node maintains a finger table. The ith entry in the table at node n contains the identity of the first node that succeeds n by at least 2^(i-1) on the identifier circle. Hence, by forwarding a key to the closest node every time Chord guarantees that the number of forwardings necessary will be O(logN).
Pastry [2] assigns each node a 128-bit identifier within [0, 2^128 - 1]. NodeIds and keys are thought of as sequences of digits with base 2b. It organizes nodes in a ring structure so that a message can be routed from any node to any key in a logarithmic number of steps with respect to the total number of nodes. It implements a prefix-based routing protocol whereby a key is forwarded to the node whose identifier has the longest common prefix with the key's identifier. Each record in row i of the routing table of node n is a node identifier that shares i prefix bits with the identifier of n. Similar to Chord, the partitioning of the keyspace in pastry along with each node's state guarantees reaching any key in O(LogN) steps.
Kademlia [4] assigns each node a 160-bit opaque ID. It treats nodes as leafs to a binary tree, with each node's position determined by the shortest unique prefix of its ID. The protocol guarantees that each node knows at least one node in each of the subtrees. Kademlia uses the xor distance measure to identify how close two nodes are in the key space. To route messages in a logarithmic number of steps, for each 0 < i < 160, each node maintains a list (i.e. k-bucket) of identifiers for nodes of distance 2^i and 2^(i+1) from itself.
CAN [3] maps keys as coordinates in a d-dimensional Cartesian space. The space is dynamically partitioned among nodes such that every node is assigned a distinct zone. Each node maintains routing information to reach its immediate neighbors. Two nodes are considered neighbors if their coordinate zones overlap along d-1 dimensions and abut along one dimension. A node routes a message in a greedy manner by forwarding towards the neighbors with a zone closest to the destination based on Euclidian distance. The average routing path the CAN guarantees is (d/4)(n power 1/d) hops.
What all these solutions or protocols have in common is a purely logical key space that doesn’t map to any physical coordinate space or key space. They all partition the space in a certain way and maintain enough state at each node during the dynamic construction of the network to be able to traverse the space in a few number of steps. But the inherent limitation they all have lies in what also make them work. The exact match key or hash that is used to address data or for content-addressing means nothing. It is just a logical pointer. And the whole design is targeted towards content-addressing as opposed to location-based addressing like in HTTP, the what instead of where. Routing the two terms “couch” and “sofa” even though they might be very related semantically would lead in mapping each of the terms to distant nodes in the network. Natural Language Processing NLP has changed how search works over the internet in the past few years. At the moment there is no way to employ such features such as semantic search atop Kademlia or even IPFS.
Discussion of the proposed Solution Just like CAN [3] used a d-dimensional cartesian space to construct the network and route and fetch keyed data. Why not use a high dimensional vector space instead. Distributional approaches to word meaning acquisition originally leveraged statistical properties of linguistic entities as the building blocks of semantics. This has led to the conception of the vector space model in information retrieval [5]. The representation of a set of documents as vectors in a common vector space is known as the vector space model and is fundamental to a host of information retrieval operations ranging from scoring documents on a query, document classification and document clustering. Since its conception, the vector space model has also been used to identify semantically associated words by measuring the similarity of their corresponding vectors. In particular, Cosine Similarity is a widely used measure of how similar two documents are irrespective of their size. Mathematically, it measures the cosine of the angle between two vectors projected in a multi-dimensional space. The cosine similarity is beneficial because even if the two similar documents are far apart by the Euclidean distance, chances are they may still be oriented closer together. The smaller the angle, the higher the cosine similarity.
The availability of larger corpora and faster computers have recently resulted in the conception of highly accurate machine learning models based on neural networks such as Google's Word2Vec [6] and BERT [7]. Stanford's Glove [8], and Facebook's Fast text [9]. Such models are used to produce word embeddings (i.e. vectors) by reconstructing linguistic contexts of words. The resulting vectors are typically comprised of several hundreds of dimensions. I tried using the produced vector spaces as a keyspace to construct semantically aware DHTs. The challenge tackled is twofold. Mainly, the partitioning of the vector space is supposed to create compact semantic groupings of vectors as keyspace partitions. In addition, each node in the network has to maintain enough state to be able to route a message m containing the vector v to the node responsible for vector v in a few numbers of hops as a function of the network size.
I have a working solution with initial results that I aim to discuss with you guys if anyone is interested.
Discussion of the tradeoffs involved: I didn’t dig deep into that yet, but so far my results are showing very good routing performance (I can argue it is O(LogN)) The construction (Node Join) is also the same, I might have one particular method I'm using creating a bit of overhead and is very fixable (I just created a word there). Other trade-offs might relate to the semantic accuracy of the lookup but that depends on the accuracy of state-of-the-art models that are being used in centralized search today.
Links to relevant literature (RFCs, papers, etc): [1] Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review 31, 4 (2001), 149–160. [2] Rowstron, A., and Druschel, P. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In IFIP/ACM International Conference on Distributed Systems Platforms and Open Distributed Processing (2001), Springer, pp. 329–350. [3] Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Shenker, S. A scalable content-addressable network. In Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications (2001), pp. 161–172. [4] Maymounkov, P., and Mazieres, D. Kademlia: A peer-to-peer information system based on the xor metric. In International Workshop on Peer-to-Peer Systems (2002), Springer, pp. 53–65. [5] Salton, G., Wong, A., and Yang, C.-S. A vector space model for automatic indexing. Communications of the ACM 18, 11 (1975), 613–620. [6] Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., and Dean, J. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems (2013), pp. 3111–3119. [7] Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018). [8] Pennington, J., Socher, R., and Manning, C. D. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP) (2014), pp. 1532–1543. [9] Bojanowski, P., Grave, E., Joulin, A., and Mikolov, T. Enriching word vectors with subword information. Transactions of the Association for Computational Linguistics 5 (2017), 135–146.