With the advent of the internet of things and industry 4.0 an enormous amount of data is produced at the edge of the network. Due to a lack of computing power, this data is currently send to the cloud where centralized machine learning models are trained to derive higher level knowledge. With the recent development of specialized machine learning hardware for mobile devices, a new era of distributed learning is about to begin that raises a new research question: How can we search in distributed machine learning models? Machine learning at the edge of the network has many benefits, such as low-latency inference and increased privacy. Such distributed machine learning models can also learn personalized for a human user, a specific context, or application scenario. As training data stays on the devices, control over possibly sensitive data is preserved as it is not shared with a third party. This new form of distributed learning leads to the partitioning of knowledge between many devices which makes access difficult. In this paper we tackle the problem of finding specific knowledge by forwarding a search request (query) to a device that can answer it best. To that end, we use a entropy based quality metric that takes the context of a query and the learning quality of a device into account. We show that our forwarding strategy can achieve over 95 accuracy in a urban mobility scenario where we use data from 30 000 people commuting in the city of Trento, Italy.
This gap was filled by research centered around nearest neighbor queries for P2P systems, like pSearch @cite_37 and Semantic Small World @cite_23 . The main idea is to provide nearest neighborhood search for multidimensional queries. Most work focuses on selecting important dimensions @cite_0 @cite_28 or methods to form an overlay network that connects nodes with similar information @cite_6 . Just like in this paper, some of these approaches also form a small world topology @cite_23 that has a small network diameter, which makes each node reachable with only a few hops and enables efficient routing. There also exists work that relies on a predefined similarity metric, e.g. the euclidean distance, and retrieves the k nearest data items in a large collection of high dimensional data @cite_14 @cite_11 @cite_4 @cite_28 .
@cite_37 @cite_14 @cite_4 @cite_28 @cite_6 @cite_0 @cite_23 @cite_11
1974677553 2086179657 1566489255 2234219295 2084949326 1494374563 1563262396
We describe an efficient peer-to-peer information retrieval system, pSearch; that supports state-of-the-art content- and semantic-based full-text searches. pSearch avoids the scalability problem of existing systems that employ centralized indexing, or index query flooding. It also avoids the nondeterminism that is exhibited by heuristic-based approaches. In pSearch; documents in the network are organized around their vector representations (based on modern document ranking algorithms) such that the search space for a given query is organized around related documents, achieving both efficiency and accuracy. Abstract We propose a novel approach to solving the approximate k-nearest neighbor search problem in metric spaces. The search structure is based on a navigable small world graph with vertices corresponding to the stored elements, edges to links between them, and a variation of greedy algorithm for searching. The navigable small world is created simply by keeping old Delaunay graph approximation links produced at the start of construction. The approach is very universal, defined in terms of arbitrary metric spaces and at the same time it is very simple. The algorithm handles insertions in the same way as queries: by finding approximate neighbors for the inserted element and connecting it to them. Both search and insertion can be done in parallel requiring only local information from the structure. The structure can be made distributed. The accuracy of the probabilistic k-nearest neighbor queries can be adjusted without rebuilding the structure. The performed simulation for data in the Euclidean spaces shows that the structure built using the proposed algorithm has small world navigation properties with log 2 ( n ) insertion and search complexity at fixed accuracy, and performs well at high dimensionality. Simulation on a CoPHiR dataset revealed its high efficiency in case of large datasets (more than an order of magnitude less metric computations at fixed recall) compared to permutation indexes. Only 0.03 of the 10 million 208-dimensional vector dataset is needed to be evaluated to achieve 0.999 recall (virtually exact search). For recall 0.93 processing speed 2800 queries s can be achieved on a dual Intel X5675 Xenon server node with Java implementation. Similarity search in metric spaces represents an important paradigm for content-based retrieval in many applications. Existing centralized search structures can speed-up retrieval, but they do not scale up to large volume of data because the response time is linearly increasing with the size of the searched file. In this article, we study the problem of executing the nearest neighbor(s) queries in a distributed metric structure, which is based on the P2P communication paradigm and the generalized hyperplane partitioning. By exploiting parallelism in a dynamic network of computers, the query execution scales up very well considering both the number of distance computations and the hop count between the peers. Results are verified by experiments on real-life data sets. Peer-to-peer systems have been widely used for sharing and exchanging data and resources among numerous computer nodes. Various data objects identifiable with high dimensional feature vectors, such as text, images, genome sequences, are starting to leverage P2P technology. Most of the existing works have been focusing on queries on data objects with one or few attributes and thus are not applicable on high dimensional data objects. In this study, we investigate K nearest neighbors query (KNN) on high dimensional data objects in P2P systems. Efficient query algorithm and solutions that address various technical challenges raised by high dimensionality, such as search space resolution and incremental search space refinement, are proposed. An extensive simulation using both synthetic and real data sets demonstrates that our proposal efficiently supports KNN query on high dimensional data in P2P systems. The retrieval facilities of most peer-to-peer (P2P) systems are limited to queries based on a unique identifier or a small set of keywords. The techniques used for this purpose are hardly applicable for content based image retrieval (CBIR) in a P2P network. Furthermore, we will argue that the curse of dimensionality and the high communication overhead prevent the adaptation of multidimensional search trees or fast sequential scan techniques for P2P CBIR. In the present paper we will propose two compact data representations that can be distributed in a P2P network and used as the basis for a source selection. This allows for communicating with only a small fraction of all peers during query processing without deteriorating the result quality significantly. We will also present experimental results confirming our approach. For a peer-to-peer (P2P) system holding massive amount of data, efficient semantic based search for resources (such as data or services) is a key determinant to its scalability. This work presents the design of an overlay network, namely semantic small world (SSW), that facilitates efficient semantic based search in P2P systems. SSW is based on three innovative ideas: 1) small world network; 2) semantic clustering; 3) dimension reduction. Peers in SSW are clustered according to the semantics of their local data and self-organized as a small world overlay network. To address the maintenance issue of high dimensional overlay networks, a dynamic dimension reduction method, called adaptive space linearization, is used to construct a one-dimensional SSW that supports operations in the high dimensional semantic space. SSW achieves a very competitive trade-off between the search latencies traffic and maintenance overheads. Through extensive simulations, we show that SSW is much more scalable to very large network sizes and very large numbers of data objects compared to pSearch, the state-of-the-art semantic-based search technique for P2P systems. In addition, SSW is adaptive to distribution of data and locality of interest; is very resilient to failures; and has good load balancing property. Given a query point Q, a Reverse Nearest Neighbor (RNN) Query returns all points in the database having Q as their nearest neighbor. The problem of RNN query has received much attention in a centralized database. However, not so much work has been done on this topic in the context of Peer-to-Peer (P2P) systems. In this paper, we shall do pioneering work on supporting distributed RNN query in large distributed and dynamic P2P networks. Our proposed RNN query algorithms are based on a distributed multi-dimensional index structure, called P2PRdNN-tree, which is relying on a super-peer-based P2P overlay. The results of our performance evaluation with real spatial data sets show that our proposed algorithms are indeed practically feasible for answering distributed RNN query in P2P systems.