Distributed Identification of Top-l Inner Product Elements and its Application in a Peer-to-Peer Network
IEEE Transactions on Knowledge and Data EngineeringPublished 29 February 2008
Kunal Das, Kanishka Bhaduri, K. Liu, H. Kargupta
Citations31
SJR quartileQ1
SJR score2.57
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
An approximate local algorithm for identifying top-l, inner products among pairs of feature vectors in a large asynchronous distributed environment such as a peer-to-peer (P2P) network is presented and a probabilistic algorithm for this purpose is developed using order statistics and the Hoeffding bound.
Abstract
The inner product measures how closely two feature vectors are related. It is an important primitive for many popular data mining tasks, for example, clustering, classification, correlation computation, and decision tree construction. If the entire data set is available at a single site, then computing the inner product matrix and identifying the top (in terms of magnitude) entries is trivial. However, in many real-world scenarios, data is distributed across many locations and transmitting the data to a central server would be quite communication intensive and not scalable. This paper presents an approximate local algorithm for identifying top-l, inner products among pairs of feature vectors in a large asynchronous distributed environment such as a peer-to-peer (P2P) network. We develop a probabilistic algorithm for this purpose using order statistics and the Hoeffding bound. We present experimental results to show the effectiveness and scalability of the algorithm. Finally, we demonstrate an application of this technique for interest-based community formation in a P2P environment.
Keywords
Computer SciencePhysics and Astronomy
The Journal of Chemical PhysicsEquation of State Calculations by Fast Computing Machines
37,074 Citations1953N. Metropolis, Arianna W. Rosenbluth +3 more
Motivation and Personality
15,228 Citations1997
Perspectives on Sexuality Sex Research - an Overview Part 1.
BiometrikaMonte Carlo sampling methods using Markov chains and their applications
15,200 Citations1970W. Keith Hastings
Springer series in statisticsProbability Inequalities for sums of Bounded Random Variables
6,947 Citations1994Wassily Hoeffding
Contemporary Sociology A Journal of ReviewsSocial Network Analysis: A Handbook.
6,046 Citations1993Franz Urban Pappi, James G. Scott
Journal of the American Statistical AssociationProbability Inequalities for Sums of Bounded Random Variables
4,750 Citations1963Wassily Hoeffding
Cambridge University Press eBooksMotivation and Personality
1,991 Citations1992Charles P. Smith, Charles P. Smith +22 more
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE<title>Measurement study of peer-to-peer file sharing systems</title>
1,922 Citations2001Stefan Saroiu, Krishna P. Gummadi +1 more
Random Walks on Graphs: A Survey
1,430 Citations2001László Lovász
Estimates on the important parameters of access time, commute time, cover time and mixing time are discussed and recent algorithmic applications of random walks are sketched, in particular to the problem of sampling.
BRITE: an approach to universal topology generation
1,233 Citations2002A. Medina, Anukool Lakhina +2 more
The goal is to produce a topology generation framework which improves the state of the art and is based on the design principles of representativeness, inclusiveness, and interoperability.
ACM SIGMOD RecordSemantic integration
1,020 Citations2004Natalya F. Noy
The goal of the paper is to provide a reader who may not be very familiar with ontology research with introduction to major themes in this research and with pointers to different research projects.
On k -anonymity and the curse of dimensionality
593 Citations2005Charų C. Aggarwal
It is shown that the curse of high dimensionality also applies to the problem of privacy preserving data mining, and when a data set contains a large number of attributes which are open to inference attacks, it becomes difficult to anonymize the data without an unacceptably high amount of information loss.
IEEE Transactions on Knowledge and Data EngineeringRandom projection-based multiplicative data perturbation for privacy preserving distributed data mining
571 Citations2006Kun Liu, H. Kargupta +1 more
This paper proposes an approximate random projection-based technique to improve the level of privacy protection while still preserving certain statistical characteristics of the data and presents extensive theoretical analysis and experimental results.
Journal of Computer and System SciencesCombining Fuzzy Information from Multiple Systems
457 Citations1999Ronald Fagin
An algorithm is given, which has been implemented in Garlic, such that if the conjuncts are independent, then with arbitrarily high probability, the total number of elements retrieved in evaluating the query is sublinear in the database size.
Distributed top-k monitoring
439 Citations2003Brian Babcock, Chris Olston
This work shows that transmitting entire data streams is unnecessary to support top-k monitoring queries and presents an alternative approach that reduces communication significantly, and empirically through extensive simulation on real-world data that this approach reduces overall communication cost by an order of magnitude.
Machine LearningAn algorithmic theory of learning: Robust concepts and random projection
334 Citations2006Rosa I. Arriaga, Santosh Vempala
This work provides a novel algorithmic analysis via a model of robust concept learning (closely related to “margin classifiers”), and shows that a relatively small number of examples are sufficient to learn rich concept classes.
PlanetP: using gossiping to build content addressable peer-to-peer information sharing communities
304 Citations2004Francisco Matias Cuenca-Acuna, Christopher Peery +2 more
Using simulation and a prototype implementation, it is shown that PlanetP achieves ranking accuracy that is comparable to a centralized solution and scales easily to several thousand peers while remaining resilient to rapid membership changes.
IEEE Internet ComputingDistributed Data Mining in Peer-to-Peer Networks
219 Citations2006Souptik Datta, Kanishka Bhaduri +3 more
An overview of DDM applications and algorithms for P2P environments is offered, focusing particularly on local algorithms that perform data analysis by using computing primitives with limited communication overhead.
AAAI Press eBooksData Mining: Next Generation Challenges and Future Directions
204 Citations2004Hillol Kargupta, Anupam Joshi +2 more
Progressive Distributed Top-k Retrieval in Peer-to-Peer Networks
188 Citations2005Wolf‐Tilo Balke, Wolfgang Nejdl +2 more
This paper discusses the benefits of best match/top-k queries in the context of distributed peer-to-peer information infrastructures and shows how to extend the limited query processing in current peer- to-peer networks by allowing the distributed processing of top- k queries, while maintaining a minimum of data traffic.
Estimating Aggregates on a Peer-to-Peer Network
174 Citations2003Mayank Bawa, Héctor García-Molina +2 more
This paper defines and study the NodeAggregation problem that is concerned with aggregating data stored at nodes in the network, and presents generic schemes that can be used to compute any of the basic aggregation functions accurately and robustly.
Improving ontology-based user profiles
172 Citations2004Joana Trajkova, Susan Gauch
This research investigates techniques that implicitly build ontology-based user profiles without user interaction, automatically monitoring the user's browsing habits and finds that ranking the concepts in the profiles by number of documents assigned to them rather than by accumulated weights provides better profile accuracy.
Power-conserving computation of order-statistics over sensor networks
171 Citations2004Michael B. Greenwald, Sanjeev Khanna
The first algorithms for computing order-statistics such that power consumption is balanced across the entire network and the worst communication cost for any single node is several times smaller than the corresponding cost in prior median algorithms are designed.
Information SciencesClustering distributed data streams in peer-to-peer environments
164 Citations2005Soma Bandyopadhyay, Chris Giannella +4 more
Experimental results show that, in contrast to the case when all the data is transmitted to a central location for application of the conventional clustering algorithm, the communication cost of the proposed approach is significantly smaller and the accuracy of the obtained centroids is high and the number of samples which are incorrectly labeled is also small.
IEEE Transactions on Knowledge and Data EngineeringApproximate Distributed K-Means Clustering over a Peer-to-Peer Network
148 Citations2008Souptik Datta, Chris Giannella +1 more
This paper offers two algorithms which produce an approximation of the result produced by the standard centralized K-means clustering algorithm which are designed to operate in a dynamic P2P network that can produce clusterings by ldquolocalrdquo synchronization only.
K-Means Clustering Over a Large, Dynamic Network
132 Citations2006Souptik Datta, Chris Giannella +1 more
IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics)Association Rule Mining in Peer-to-Peer Systems
93 Citations2004Ran Wolff, Assaf Schuster
An algorithmic theory of learning: robust concepts and random projection
88 Citations2003Rosa I. Arriaga, S. Vempala
Journal of the Operational Research SocietyOrdinal optimisation and simulation
78 Citations2000Y-C. Ho, Christos G. Cassandras +2 more
This paper introduces the idea of ordinal optimisation, and reports some recent advances in this research, and gives details of an extension of ordinals optimisation to a class of resource application problems.
Trust-Based Community Formation in Peer-to-Peer File Sharing Networks
74 Citations2004Yao Wang, Julita Vassileva
This work proposes a mechanism for forming communities in a P2P system for sharing academic papers that requires each agent to compute its trust in the agents with whom it interacts.
Information Processing LettersEstimating network size from local information
68 Citations2003Keren Horowitz, Dahlia Malkhi
Distributed Uniform Sampling in Unstructured Peer-to-Peer Networks
53 Citations2006Asad Awan, Ronaldo A. Ferreira +2 more
This paper prescribes necessary conditions for uniform sampling in such networks and presents distributed algorithms that satisfy these requirements and empirically evaluates the performance of the algorithm in comparison to known algorithms.
IEEE Transactions on Knowledge and Data EngineeringDimensionality reduction and similarity computation by inner-product approximations
48 Citations2004Ömer Eğecioǧlu, Hakan Ferhatosmanoğlu +1 more
ACM SIGKDD Explorations NewsletterClient-side web mining for community formation in peer-to-peer environments
47 Citations2006Kun Liu, Kanishka Bhaduri +3 more
At the heart of this framework is the use of an order statistics-based approach to build communities with hierarchical structure using client-side web browsing history to form interests-based Peer-to-Peer communities.
EFFICIENT DISCOVERY OF IMPLICITLY FORMED PEER-TO-PEER COMMUNITIES #
40 Citations2002Mujtaba Khambatti, K.D. Ryu +1 more
This paper investigates the behavior of randomly created communities and model the complexity of discovery algorithms, which allow for quickly changing community structures (dynamic communities, failures, mobile nodes and so on).
Local L2-Thresholding Based Data Mining in Peer-to-Peer Systems
38 Citations2006Ran Wolff, Kanishka Bhaduri +1 more
A highly efficient local algorithm which detect when the L2 norm of the average data surpasses a threshold is described and is used as a feedback loop for the monitoring of complex predicates on the data – such as the data’s k-means clustering.
IEEE/WIC/ACM International Conference on Web Intelligence (WI'04)Trust-Based Community Formation in Peer-to-Peer File Sharing Networks
38 Citations2005Yao Wang, Julita Vassileva
Uniform Data Sampling from a Peer-to-Peer Network
37 Citations2007Souptik Datta, Hillol Kargupta
This paper proposes a random walk-based sampling algorithm that can be used to sample data tuples uniformly from a large, unstructured P2P network and model the random walk as a Markov chain and derive conditions to bound the length of the randomWalk necessary to achieve uniformity.
Communication Efficient Construction of Decision Trees Over Heterogeneously Distributed Data
36 Citations2005Chris Giannella, Kun Liu +2 more
Pattern Analysis and ApplicationsRobust Combining of Disparate Classifiers through Order Statistics
33 Citations2002Kagan Tumer, Joydeep Ghosh
The trim and spread combiners are analysed, both based on linear combinations of the ordered classifier outputs, and it is shown that in the presence of uneven classifier performance, they often provide substantial gains over both linear and simple order statistics combiners.
University of Minnesota Digital Conservancy (University of Minnesota)Network Size Estimation In A Peer-to-Peer Network
28 Citations2005Sandeep Mane, Sandeep Mopuru +2 more
Archivio Istituzionale della Ricerca (Universita Degli Studi Di Milano)Semantic Self-Formation of Communities of Peers
27 Citations2005Silvana Castano, Stefano Montanelli
A novel approach to the selforganization of autonomous communities of peers is proposed based on semantic community aggregation and community-aware query propagation techniques exploiting dynamic ontology matching techniques for improving traditional P2P search and discovery capabilities.
Dimensionality reduction and similarity computation by inner product approximations
25 Citations2000Ömer Eğeci̇oğlu, Hakan Ferhatosmanoğlu
This work develops dynamic techniques for efficient and accurate approximation of similarity evaluations between high-dimensional vectors based on inner-product approximations and develops a dynamic model to compute the universal coefficients for data sets whose distribution is not known.
SEARCH, Computational Processes in Evolution, and Preliminary Development of the Gene Expression Messy Genetic Algorithm.
13 Citations1997Hillol Kargupta
arXiv (Cornell University)Efficient Algorithms for Sampling and Clustering of Large Nonuniform Networks
7 Citations2004Pekka Orponen, Satu Elisa Schaeffer
This work proposes efficient algorithms for two key tasks in the analysis of large nonuniform networks: uniform node sampling and cluster detection and clustering, based on local computations.