OpenRaiser/Intern-Atlas huggingface dataset:
A scalable graph-cut algorithm for n-d grids
Authors: Andrew Delong, Yuri Boykov
Venue: Conference CVPR 2008
Year: 2008

Global optimisation via s-t graph cuts is widely used in computer vision and graphics. To obtain high-resolution output, graph cut methods must construct massive N-D grid-graphs containing billions of vertices. We show that when these graphs do not fit into physical memory, current max-flow/min-cut algorithms-the workhorse of graph cut methods-are totally impractical. Others have resorted to banded or hierarchical approximation methods that get trapped in local minima, which loses the main benefit of global optimisation. We enhance the push-relabel algorithm for maximum flow [14] with two practical contributions. First, true global minima can now be computed on immense grid-like graphs too large for physical memory. These graphs are ubiquitous in computer vision, medical imaging and graphics. Second, for commodity multi-core platforms our algorithm attains near-linear speedup with respect to number of processors. To achieve these goals, we generalised the standard relabeling operations associated with push-relabel.
Temporal feedback for tweet search with non-parametric density estimation
Authors: Miles Efron, Jimmy Lin, Jiyin He, Arjen P. de Vries
Venue: Conference SIGIR 2014
Year: 2014

This paper investigates the temporal cluster hypothesis: in search tasks where time plays an important role, do relevant documents tend to cluster together in time? We explore this question in the context of tweet search and temporal feedback: starting with an initial set of results from a baseline retrieval model, we estimate the temporal density of relevant documents, which is then used for result reranking. Our contributions lie in a method to characterize this temporal density function using kernel density estimation, with and without human relevance judgments, and an approach to integrating this information into a standard retrieval model. Experiments on TREC datasets confirm that our temporal feedback formulation improves search effectiveness, thus providing support for our hypothesis. Our approach out-performs both a standard baseline and previous temporal retrieval models. Temporal feedback improves over standard lexical feedback (with and without human judgments), illus- trating that temporal relevance signals exist independently of document content.
Associative tag recommendation exploiting multiple textual features
Authors: Fabiano Belém, Eder Ferreira Martins, Tatiana Pontes, Jussara M. Almeida, Marcos André Gonçalves
Venue: Conference SIGIR 2011
Year: 2011

This work addresses the task of recommending relevant tags to a target object by jointly exploiting three dimensions of the problem: (i) term co-occurrence with tags pre-assigned to the target object, (ii) terms extracted from multiple textual features, and (iii) several metrics of tag relevance. In particular, we propose several new heuristic methods, which extend state-of-the-art strategies by including new metrics that try to capture how accurately a candidate term describes the object's content. We also exploit two learning-to-rank (L2R) techniques, namely RankSVM and Genetic Programming, for the task of generating ranking functions that combine multiple metrics to accurately estimate the relevance of a tag to a given object. We evaluate all proposed methods in various scenarios for three popular Web 2.0 applications, namely, LastFM, YouTube and YahooVideo. We found that our new heuristics greatly outperform the methods on which they are based, producing gains in precision of up to 181%, as well as another state-of-the-art technique, with improvements in precision of up to 40% over the best baseline in any scenario. Further improvements can also be achieved with the new L2R strategies, which have the additional advantage of being quite flexible and extensible to exploit other aspects of the tag recommendation problem.
Gathering and ranking photos of named entities with high precision, high recall, and diversity
Authors: Bilyana Taneva, Mouna Kacimi, Gerhard Weikum
Venue: Conference WSDM 2010
Year: 2010

Knowledge-sharing communities like Wikipedia and automated extraction methods like those of DBpedia enable the construction of large machine-processible knowledge bases with relational facts about entities. These endeavors lack multimodal data like photos and videos of people and places. While photos of famous entities are abundant on the Internet, they are much harder to retrieve for less popular entities such as notable computer scientists or regionally interesting churches. Querying the entity names in image search engines yields large candidate lists, but they often have low precision and unsatisfactory recall.
Delving deep into personal photo and video search
Authors: Lu Jiang, Yannis Kalantidis, Liangliang Cao, Sachin Farfade, Jiliang Tang, Alexander G. Hauptmann
Venue: Conference WSDM 2017
Year: 2017

The ubiquity of mobile devices and cloud services has led to an unprecedented growth of online personal photo and video collections. Due to the scarcity of personal media search log data, research to date has mainly focused on searching images and videos on the web. However, in order to manage the exploding amount of personal photos and videos, we raise a fundamental question: what are the differences and similarities when users search their own photos versus the photos on the web? To the best of our knowledge, this paper is the first to study personal media search using large-scale real-world search logs. We analyze different types of search sessions mined from Flickr search logs and discover a number of interesting characteristics of personal media search in terms of information needs and click behaviors. The insightful observations will not only be instrumental in guiding future personal media search methods, but also benefit related tasks such as personal photo browsing and recommendation. Our findings suggest there is a significant gap between personal queries and automatically detected concepts, which is responsible for the low accuracy of many personal media search queries. To bridge the gap, we propose the deep query understanding model to learn a mapping from the personal queries to the concepts in the clicked photos. Experimental results verify the efficacy of the proposed method in improving personal media search, where the proposed method consistently outperforms baseline methods.
Signal-based user recommendation on twitter
Authors: Giuliano Arru, Davide Feltoni Gurini, Fabio Gasparetti, Alessandro Micarelli, Giuseppe Sansonetti
Venue: Conference WWW 2013
Year: 2013

In recent years, social networks have become one of the best ways to access information. The ease with which users connect to each other and the opportunity provided by Twitter and other social tools in order to follow person activities are increasing the use of such platforms for gathering information. The amount of available digital data is the core of the new challenges we now face. Social recommender systems can suggest both relevant content and users with common social interests. Our approach relies on a signal-based model, which explicitly includes a time dimension in the representation of the user interests. Specifically, this model takes advantage of a signal processing technique, namely, the wavelet transform, for defining an efficient pattern-based similarity function among users. Experimental comparisons with other approaches show the benefits of the proposed approach.
Discovering top-k teams of experts with/without a leader in social networks
Authors: Mehdi Kargar, Aijun An
Venue: Conference CIKM 2011
Year: 2011

We study the problem of discovering a team of experts from a social network. Given a project whose completion requires a set of skills, our goal is to find a set of experts that together have all of the required skills and also have the minimal communication cost among them. We propose two communication cost functions designed for two types of communication structures. We show that the problem of finding the team of experts that minimizes one of the proposed cost functions is NP-hard. Thus, an approximation algorithm with an approximation ratio of two is designed. We introduce the problem of finding a team of experts with a leader. The leader is responsible for monitoring and coordinating the project, and thus a different communication cost function is used in this problem. To solve this problem, an exact polynomial algorithm is proposed. We show that the total number of teams may be exponential with respect to the number of required skills. Thus, two procedures that produce top-k teams of experts with or without a leader in polynomial delay are proposed. Extensive experiments on real datasets demonstrate the effectiveness and scalability of the proposed methods.
Composing activity groups in social networks
Authors: Cheng-Te Li, Man-Kwan Shan
Venue: Conference CIKM 2012
Year: 2012

One important function of current social networking services is allowing users to initialize different kinds of activity groups (e.g. study group, cocktail party, and group buying) and invite friends to attend in either manual or collaborative manners. However, such process of group formation is tedious, and could either include inappropriate group members or miss relevant ones. This work proposes to automatically compose the activity groups in a social network according to user-specified activity information. Given the activity host, a set of labels representing the activity's subjects, the desired group size, and a set of must-inclusive persons, we aim to find a set of individuals as the activity group, in which members are required to not only be familiar with the host but also have great communications with each other. We devise an approximation algorithm to greedily solve the group composing problem. Experiments on a real social network show the promising effectiveness of the proposed approach as well as the satisfactory human subjective study.
Information-based models for ad hoc ir
Authors: Stéphane Clinchant, Éric Gaussier
Venue: Conference SIGIR 2010
Year: 2010

We introduce in this paper the family of information-based models for ad hoc information retrieval. These models draw their inspiration from a long-standing hypothesis in IR, namely the fact that the difference in the behaviors of a word at the document and collection levels brings information on the significance of the word for the document. This hypothesis has been exploited in the 2-Poisson mixture models, in the notion of eliteness in BM25, and more recently in DFR models. We show here that, combined with notions related to burstiness, it can lead to simpler and better models.
Image matching via saliency region correspondences
Authors: Alexander Toshev, Jianbo Shi, Kostas Daniilidis
Venue: Conference CVPR 2007
Year: 2007

We introduce the notion of co-saliency for image matching. Our matching algorithm combines the discriminative power of feature correspondences with the descriptive power of matching segments. Co-saliency matching score favors correspondences that are consistent with 'soft' image segmentation as well as with local point feature matching. We express the matching model via a joint image graph (JIG) whose edge weights represent intra-as well as inter-image relations. The dominant spectral components of this graph lead to simultaneous pixel-wise alignment of the images and saliency-based synchronization of 'soft' image segmentation. The co-saliency score function, which characterizes these spectral components, can be directly used as a similarity metric as well as a positive feedback for updating and establishing new point correspondences. We present experiments showing the extraction of matching regions and pointwise correspondences, and the utility of the global image similarity in the context of place recognition.
Bayesian face recognition using support vector machine and face clustering
Authors: Zhifeng Li 0001, Xiaoou Tang
Venue: Conference CVPR 2004
Year: 2004

In this paper, we first develop a direct Bayesian based support vector machine by combining the Bayesian analysis with the SVM. Unlike traditional SVM-based face recognition method that needs to train a large number of SVMs, the direct Bayesian SVM needs only one SVM trained to classify the face difference between intra-personal variation and extra-personal variation. However, the added simplicity means that the method has to separate two complex subspaces by one hyper-plane thus affects the recognition accuracy. In order to improve the recognition performance we develop three more Bayesian based SVMs, including the one-versus-all method, the hierarchical agglomerative clustering based method, and the adaptive clustering method. We show the improvement of the new algorithms over traditional subspace methods through experiments on two face databases, the FERET database and the XM2VTS database.
Simultaneous super-resolution and feature extraction for recognition of low-resolution faces
Authors: Pablo H. Hennings-Yeomans, Simon Baker, B. V. K. Vijaya Kumar
Venue: Conference CVPR 2008
Year: 2008

Face recognition degrades when faces are of very low resolution since many details about the difference between one person and another can only be captured in images of sufficient resolution. In this work, we propose a new procedure for recognition of low-resolution faces, when there is a high-resolution training set available. Most previous super-resolution approaches are aimed at reconstruction, with recognition only as an after-thought. In contrast, in the proposed method, face features, as they would be extracted for a face recognition algorithm (e.g., eigenfaces, Fisher-faces, etc.), are included in a super-resolution method as prior information. This approach simultaneously provides measures of fit of the super-resolution result, from both reconstruction and recognition perspectives. This is different from the conventional paradigms of matching in a low-resolution domain, or, alternatively, applying a super-resolution algorithm to a low-resolution face and then classifying the super-resolution result. We show, for example, that recognition of faces of as low as 6 times 6 pixel size is considerably improved compared to matching using a super-resolution reconstruction followed by classification, and to matching with a low-resolution training set.
Prep: Path-based relevance from a probabilistic perspective in heterogeneous information networks
Authors: Yu Shi, Po-Wei Chan, Honglei Zhuang, Huan Gui, Jiawei Han
Venue: Conference KDD 2017
Year: 2017

As a powerful representation paradigm for networked and multi-typed data, the heterogeneous information network (HIN) is ubiquitous. Meanwhile, defining proper relevance measures has always been a fundamental problem and of great pragmatic importance for network mining tasks. Inspired by our probabilistic interpretation of existing path-based relevance measures, we propose to study HIN relevance from a probabilistic perspective. We also identify, from real-world data, and propose to model cross-meta-path synergy, which is a characteristic important for defining path-based HIN relevance and has not been modeled by existing methods. A generative model is established to derive a novel path-based relevance measure, which is data-driven and tailored for each HIN. We develop an inference algorithm to find the maximum a posteriori (MAP) estimate of the model parameters, which entails non-trivial tricks. Experiments on two real-world datasets demonstrate the effectiveness of the proposed model and relevance measure.
Image segmentation with minimum mean cut
Authors: Song Wang 0002, Jeffrey Mark Siskind
Venue: Conference ICCV 2001
Year: 2001

We introduce a new graph-theoretic approach to image segmentation based on minimizing a novel class of 'mean cut' cost functions. Minimizing these cost functions corresponds to finding a cut with minimum mean edge weight in a connected planar graph. This approach has several advantages over prior approaches to image segmentation. First, it allows cuts with both open and closed boundaries. Second, it guarantees that the partitions are connected. Third, the cost function does not introduce an explicit bias, such as a preference for large-area foregrounds, smooth or short boundaries, or similar-weight partitions. This lack of bias allows it to produce segmentations that are better aligned with image edges, even in the presence of long thin regions. Finally, the global minimum of this cost function is largely insensitive to the precise choice of edge-weight function. In particular, we show that the global minimum is invariant under a linear transformation of the edge weights and thus insensitive to image contrast. Building on algorithms by Ahuja et al. (1993), we present a polynomial-time algorithm for finding a global minimum of the mean-cut cost function and illustrate the results of applying that algorithm to several synthetic and real images.
Improving weak ad-hoc queries using Wikipedia as external corpus
Authors: Yinghao Li, Robert Wing Pong Luk, Edward Kei Shiu Ho, Korris Fu-Lai Chung
Venue: Conference SIGIR 2007
Year: 2007

In an ad-hoc retrieval task, the query is usually short and the user expects to find the relevant documents in the first several result pages. We explored the possibilities of using Wikipedia's articles as an external corpus to expand ad-hoc queries. Results show promising improvements over measures that emphasize on weak queries.
Supervised query modeling using Wikipedia
Authors: Edgar Meij, Maarten de Rijke
Venue: Conference SIGIR 2010
Year: 2010

We use Wikipedia articles to semantically inform the generation of query models. To this end, we apply supervised machine learning to automatically link queries to Wikipedia articles and sample terms from the linked articles to re-estimate the query model. On a recent large web corpus, we observe substantial gains in terms of both traditional metrics and diversity measures.
PTE: enumerating trillion triangles on distributed systems
Authors: Ha-Myung Park, Sung-Hyon Myaeng, U Kang
Venue: Conference KDD 2016
Year: 2016

How can we enumerate triangles from an enormous graph with billions of vertices and edges? Triangle enumeration is an important task for graph data analysis with many applications including identifying suspicious users in social networks, detecting web spams, finding communities, etc. However, recent networks are so large that most of the previous algorithms fail to process them. Recently, several MapReduce algorithms have been proposed to address such large networks; however, they suffer from the massive shuffled data resulting in a very long processing time. In this paper, we propose PTE (Pre-partitioned Triangle Enumeration), a new distributed algorithm for enumerating triangles in enormous graphs by resolving the structural inefficiency of the previous MapReduce algorithms. PTE enumerates trillions of triangles in a billion scale graph by decreasing three factors: the amount of shuffled data, total work, and network read.
Selective value coupling learning for detecting outliers in high-dimensional categorical data
Authors: Guansong Pang, Hongzuo Xu, Longbing Cao, Wentao Zhao
Venue: Conference CIKM 2017
Year: 2017

This paper introduces a novel framework, namely SelectVC and its instance POP, for learning selective value couplings (i.e., interactions between the full value set and a set of outlying values) to identify outliers in high-dimensional categorical data. Existing outlier detection methods work on a full data space or feature subspaces that are identified independently from subsequent outlier scoring. As a result, they are significantly challenged by overwhelming irrelevant features in high-dimensional data due to the noise brought by the irrelevant features and its huge search space. In contrast, SelectVC works on a clean and condensed data space spanned by selective value couplings by jointly optimizing outlying value selection and value outlierness scoring. Its instance POP defines a value outlierness scoring function by modeling a partial outlierness propagation process to capture the selective value couplings. POP further defines a top-k outlying value selection method to ensure its scalability to the huge search space. We show that POP (i) significantly outperforms five state-of-the-art full space- or subspace-based outlier detectors and their combinations with three feature selection methods on 12 real-world high-dimensional data sets with different levels of irrelevant features; and (ii) obtains good scalability, stable performance w.r.t. k, and fast convergence rate.
A way to boost semi-nmf for document clustering
Authors: Aghiles Salah, Melissa Ailem, Mohamed Nadif
Venue: Conference CIKM 2017
Year: 2017

Semi-Non Negative Matrix Factorization (Semi-NMF) is one of the most popular extensions of NMF, it extends the applicable range of NMF models, to data having mixed signs, as well as strengthens their relation to clustering. However, Semi-NMF has been found to perform somewhat less than NMF, in terms of clustering, when applied to positive data such as text, which we focus on. Inspired by the recent success of neural word embedding models, e.g., word2vec, in learning high quality real valued vector representations of words, we propose to integrate a word embedding model into Semi-NMF. This allows Semi-NMF to capture more semantic relationships among words and, thereby, to infer document factors that are even better for clustering. The combination of Semi-NMF and word embedding noticeably improves the performance of NMF models, in terms of both clustering and embedding, as illustrated in our experiments.
Alip: the automatic linguistic indexing of pictures system
Authors: Jia Li 0001, James Ze Wang
Venue: Conference CVPR 2005
Year: 2005

We present the Automatic Linguistic Indexing of Pictures (ALIP) system. The system annotates images with linguistic terms, chosen among hundreds of such terms. The system uses a wavelet-based approach for feature extraction, a statistical modeling process for training, and a statistical significance processor to annotate images. We implemented and tested our ALIP system on a photographic image database of 600 different concepts, each with about 40 training images. The ALIP system has been used to annotate about 60,000 photographic images. In this demonstration, we illustrate the algorithms in the system and show the annotation results. With distributed computation, the annotation of an image can be provided in real-time.
Information retrieval using impression of documents as a clue
Authors: Fusako Hirabayashi, Hiroshi Matoba, Yutaka Kasahara
Venue: Conference SIGIR 1988
Year: 1988

Proposed here is an internal representation and mapping method for multimedia information in which retrieval is based on the impression documents are desired to make. A user interface design for a system using this method is also proposed.
Detecting non-gaussian geographical topics in tagged photo collections
Authors: Christoph Carl Kling, Jérôme Kunegis, Sergej Sizov, Steffen Staab
Venue: Conference WSDM 2014
Year: 2014

Nowadays, large collections of photos are tagged with GPS coordinates. The modelling of such large geo-tagged corpora is an important problem in data mining and information retrieval, and involves the use of geographical information to detect topics with a spatial component. In this paper, we propose a novel geographical topic model which captures dependencies between geographical regions to support the detection of topics with complex, non-Gaussian distributed spatial structures. The model is based on a multi-Dirichlet process (MDP), a novel generalisation of the hierarchical Dirichlet process extended to support multiple base distributions. Our method thus is called the MDP-based geographical topic model (MGTM). We show how to use a MDP to dynamically smooth topic distributions between groups of spatially adjacent documents. In systematic quantitative and qualitative evaluations using independent datasets from prior related work, we show that such a model can exploit the adjacency of regions and leads to a significant improvement in the quality of topics compared to the state of the art in geographical topic modelling.