به نام خدا
Title: Sharding Social Networks
Authors: Quang Duong, Sharad Goel, Jake Hofman, Sergei Vassilvitskii
Abstract: Online social networking platforms regularly support hun-dreds of millions of users, who in aggregate generate sub-stantially more data than can be stored on any single phys-ical server. As such, user data are distributed, or sharded,across many machines. A key requirement in this setting israpid retrieval not only of a given user_s information, butalso of all data associated with his or her social contacts,suggesting that one should consider the topology of the so-cial network in selecting a sharding policy. In this paperwe formalize the problem of efficiently sharding large so-cial network databases, and evaluate several sharding strate-gies, both analytically and empirically. We find that randomsharding-the de facto standard-results in provably poorperformance even when frequently accessed nodes are repli-cated to many shards. By contrast, we demonstrate that onecan substantially reduce querying costs by identifying andassigning tightly knit communities to shards. In particular,our theoretical analysis motivates a novel, scalable shardingalgorithm that outperforms both random and location-basedsharding schemes.
Publish Year: 2013
Published by: ACM-WSDM
موضوع: شبکه های اجتماعی (Social Netwroks)
ایران سای – مرجع علمی فنی مهندسی
حامی دانش بومی ایرانیان
به نام خدا
Title: Efficient and dynamic key management for multiple identities in identity-based systems
Authors: Hua Guo , Chang Xu a , Zhoujun Li a , Yanqing Yao a , Yi Mu
Abstract: The traditional identity-based cryptography requires a user, who holds multiple identities, to hold multiple private keys, where each private key is associated with an identity. Man- aging multiple private/public keys is a heavy burden to a user due to key management and storage. The recent advancement of identity-based cryptography allow a single private key to map multiple public keys (identities); therefore the private key management is simpli- fied. Unfortunately, the existing schemes capturing this feature do not allow dynamic changes of identities and have a large data size proportional to the number of the associ- ated identities. To overcome these problems, in this paper, we present an efficient and dynamic identity-based key exchange protocol and prove its security under the Bilinear Diffie Hellman assumption in the random oracle model. Our protocol requires a relatively small bandwidth for a key agreement communication, in comparison with other existing schemes.
Publish Year: 2013
Published in: Information Sciences - Science Direct
موضوع: رمزنگاری
ایران سای – مرجع علمی فنی مهندسی
حامی دانش بومی ایرانیان
به نام خدا
Title: Using the idea of the sparse representation to perform coarse- to-fine face recognition
Authors: Yong Xu , Qi Zhu a , Zizhu Fan , David Zhang d , Jianxun Mi a , Zhihui Lai
Abstract: In this paper, we propose a coarse-to-fine face recognition method. This method consists of two stages and works in a similar way as the well-known sparse representation method. The first stage determines a linear combination of all the training samples that is approximately equal to the test sample. This stage exploits the determined linear combination to coarsely determine candidate class labels of the test sample. The second stage again deter- mines a weighted sum of all the training samples from the candidate classes that is approximately equal to the test sample and uses the weighted sum to perform classification. The rationale of the proposed method is as follows: the first stage identifies the classes that are far from the test sample and removes themfromthe set of the training samples. Then the method will assign the test sample into one of the remaining classes and the classification problem becomes a simpler one with fewer classes. The proposed method not only has a high accuracy but also can be clearly interpreted.
Publish Year: 2013
Published in: Information Sciences - Science Direct
موضوع: شناسایی چهره (Face Detection)
ایران سای – مرجع علمی فنی مهندسی
حامی دانش بومی ایرانیان
به نام خدا
Title: Application of the Mean Field Methods to MRF Optimization in Computer Vision
Authors: Masaki Saito Takayuki Okatani Koichiro Deguchi
Abstract: The mean field (MF) methods are an energy optimization method for Markov random fields (MRFs). These methods, which have their root in solid state physics, estimate the marginal density of each site of an MRF graph by iterative computation, similarly to loopy belief propagation (LBP).It appears that, being shadowed by LBP, the MF methods have not been seriously considered in the computer vision community. This study investigates whether these methods are useful for practical problems, particularly MPM (Maxi-mum Posterior Marginal) inference, in computer vision. To be specific, we apply the naive MF equations and the TAP (Thou less-Anderson-Palmer) equations to interactive segmentation and stereo matching. In this paper, firstly, we show implementation of these methods for computer vision problems. Next, we discuss advantages of the MF methods to LBP. Finally, we present experimental results that the MFmethods are well comparable to LBP in terms of accuracy and global convergence; furthermore, the 3rd-order TAP equation often outperforms LBP in terms of accuracy.
Publish Year: 2012
Published in: CVPR - IEEE
موضوع: بینایی ماشین (Computer Vision)
ایران سای – مرجع علمی فنی مهندسی
حامی دانش بومی ایرانیان
به نام خدا
Title: Threading Machine Generated Email
Authors: Nir Ailon, Zohar S Karnin, Edo Liberty, Yoelle Maarek
Abstract: Viewing email messages as parts of a sequence or a thread isa convenient way to quickly understand their context. Cur-rent threading techniques rely on purely syntactic methods,matching sender information, subject line, and reply/forwardpre�xes. As such, they are mostly limited to personal con-versations. In contrast, machine-generated email, whichamount, as per our experiments, to more than 60% of theoverall email traffic, requires a different kind of threadingthat should reflect how a sequence of emails is caused bya few related user actions. For example, purchasing goodsfrom an online store will result in a receipt or a con�rma-tion message, which may be followed, possibly after a fewdays, by a shipment noti�cation message from an expressshipping service. In today_s mail systems, they will not bea part of the same thread, while we believe they should.In this paper, we focus on this type of threading that wecoin “causal threading�. We demonstrate that, by analyzingrecurring patterns over hundreds of millions of mail users,we can infer a causality relation between these two indi-vidual messages. In addition, by observing multiple causalrelations over common messages, we can generate “causalthreads� over a sequence of messages. The four key stagesof our approach consist of: (1) identifying messages that areinstances of the same email type or“template� (generated bythe same machine process on the sender side) (2) building acausal graph, in which nodes correspond to email templatesand edges indicate potential causal relations (3) learning acausal relation prediction function, and (4) automatically“threading� the incoming email stream. We present detailedexperimental results obtained by analyzing the inboxes of12.5 million Yahoo! Mail users, who voluntarily opted-in forsuch research. Supervised editorial judgments show thatwe can identify more than 70% (recall rate) of all “causalthreads�at a precision level of 90%. In addition, for a searchscenario we show that we achieve a precision close to 80%at 90% recall. We believe that supporting causal threads inPermission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
Publish Year: 2013
Publisher: ACM-WSDM
موضوع: یادگیری ماشین (Machine Learning)
ایران سای – مرجع علمی فنی مهندسی
حامی دانش بومی ایرانیان
