Search

The rich knowledge contains on the web plays an important role in the researches and practical applications including web search, multi-question answering, and knowledge base construction. How to correctly detect the semantic types of all the data columns is critical to understand the web table. The traditional methods have the following limitations: (1) Most of them rely on dictionary lookup and regular expression matching, and are generally not robust to dirty data; (2) They only consider character data besides numeric data which accounts for a large proportion; (3) Some models take the characteristics of a single column and do not consider the special organizational structure of the table. In this paper, a column type detection method combining deep learning and probability graph model is proposed, taking the semantic features of a single column and the interaction between multiple columns into account to improve the prediction accuracy. Experimental results show that our method has higher accuracy compared with the state-of-the-art approaches.

The problem of link prediction in dynamic heterogeneous information networks has been widely studied in recent years. The technique of network embedding has been proved extremely useful for link prediction. However, the existing methods lack the close combination between deep-level features and temporal features of networks, which affects the accuracy of prediction and makes it difficult to adapt to the dynamic networks. In this paper, a Smooth Evolution model for Network Embedding (called SENE) is proposed, which considers both deep-level features and temporal features to obtain the embedded representations of the network structure, and uses the transformer mechanism to effectively obtain the smooth evolution of network embedding. Also an SENE-based link prediction algorithm is proposed, which can effectively guarantee the accuracy of link prediction. The feasibility and effectiveness of the proposed key technologies are verified by experiments.

Set similarity join (SSJoin) is an important operation for searching similarity set pairs from the given database and play a core role in data integration, data cleaning, and data mining. In contrast to the traditional SSJoin methods, progressive SSJoin aims to resolve large datasets so that the efficiency of finding similarity pairs in the limited running time is improved. Progressive SSJoin can provide possible partial matching pairs of the dataset as early as possible in the processing. Moreover, recent research has shown that GPUs (Graphics Processing Units) can accelerate the similarity operation. This paper focuses on exploring progressive SSJoin algorithms and accelerating them with GPUs. We proposes two progressive SSJoin methods, PSSJM and PBM. PSSJM uses inverted index and PBM achieves its required functions by utilizing counting Bloom filter and prefix filtering techniques. In addition, we proposed a GPUs-based algorithm based on our proposed progressive method to accelerate the computation. Comprehensive experiments with real-world datasets show that our methods can generate better quality results than the traditional method under limited time and the method implementing on GPUs has high speedups over CPU-base method.

A lot of scholars have focused on developing effective techniques for package queries, and a lot of excellent approaches have been proposed. Unfortunately, most of the existing methods focus on a small volume of data. The rapid increase in data volume means that traditional methods of package queries find it difficult to meet the increasing requirements. To solve this problem, a novel optimization method of package queries (HPPQ) is proposed in this paper. First, the data is preprocessed into regions. Data preprocessing segments the dataset into multiple subsets and the centroid of the subsets is used for package queries, this effectively reduces the volume of candidate results. Furthermore, an efficient heuristic algorithm is proposed (namely IPOL-HS) based on the preprocessing results. This improves the quality of the candidate results in the iterative stage and improves the convergence rate of the heuristic algorithm. Finally, a strategy called HPR is proposed, which relies on a greedy algorithm and parallel processing to accelerate the rate of query. The experimental results show that our method can significantly reduce time consumption compared with existing methods.

Nowadays, people usually participate in multiple social networks simultaneously, e.g., Facebook and Twitter. Formally, the correspondences of the accounts that belong to the same user are defined as anchor links, and the networks aligned by anchor links can be denoted as aligned networks. In this paper, we study the problem of anchor link prediction (ALP) across a pair of aligned networks based on social network structure. First, three similarity metrics (CPS, CCS, and CPS+) are proposed. Different from the previous works, we focus on the theoretical guarantees of our metrics. We prove mathematically that the node pair with the maximum CPS or CPS+ should be an anchor link with high probability and a correctly predicted anchor link must have a high value of CCS. Second, using the CPS+ and CCS, we present a two-stage iterative algorithm CPCC to solve the problem of the ALP. More specifically, we present an early termination strategy to make a tradeoff between precision and recall. At last, a series of experiments are conducted on both synthetic and real-world social networks to demonstrate the effectiveness of the CPCC.

Set similarity join (SSJoin) is known as an important operation for searching similarity set pairs from the given database and plays a core role in data integration, data cleaning, and data mining. Different from the traditional SSJoin methods, progressive SSJoin aims to resolve large datasets so that the efficiency of finding similarity pairs in the limited running time can be improved. Progressive SSJoin can provide possible partial matching pairs of the dataset as early as possible in the processing. Moreover, many recent researches have shown that GPUs (Graphics Processing Units) can accelerate and improve the efficiency of similarity join operation. This paper focuses on exploring progressive SSJoin algorithms and accelerating them with the CPU-GPU architecture. We propose two progressive SSJoin methods, PSSJM and PBM. PSSJM utilizes inverted indexing and PBM achieves its required functions by utilizing the counting Bloom filter and prefix filtering techniques. In addition, we proposed a GPUs-based algorithm based on our progressive SSJoin method to accelerate the processing. Comprehensive experiments with real-world datasets show that our methods can generate better quality results than the traditional method under limited time and the method implementing on CPU-GPU architecture has high speedups over the CPU-base method.

The process of matching and integrating records that relate to the same entity from one or more datasets is known as record linkage, and it has become an increasingly important subject in many application areas, including business, government and health system. The data from these areas often contain sensitive information. To prevent privacy breaches, ideally records should be linked in a private way such that no information other than the matching result is leaked in the process, and this technique is called privacy-preserving record linkage (PPRL). With the increasing data, scalability becomes the main challenge of PPRL, and many private blocking techniques have been developed for PPRL. They are aimed at reducing the number of record pairs to be compared in the matching process by removing obvious non-matching pairs without compromising privacy. However, most of them are designed for two databases and they vary widely in their ability to balance competing goals of accuracy, efficiency and security. In this paper, we propose a novel private blocking approach for PPRL based on dynamic k-anonymous blocking and Paillier cryptosystem which can be applied on two or multiple databases. In dynamic k-anonymous blocking, our approach dynamically generates blocks satisfying k-anonymity and more accurate values to represent the blocks with varying k. We also propose a novel similarity measure method which performs on the numerical attributes and combines with Paillier cryptosystem to measure the similarity of two or more blocks in security, which provides strong privacy guarantees that none information reveals even collusion. Experiments conducted on a public dataset of voter registration records validate that our approach is scalable to large databases and keeps a high quality of blocking. We compare our method with other techniques and demonstrate the increases in security and accuracy.

Conditional functional dependencies(CFDs) are important techniques for data consistency. However, CFDs are limited to 1) provide the reasonable values for consistency repairing and 2) detect potential errors. This paper presents context-aware conditional functional dependencies(CCFDs) which contribute to provide reasonable values and detect potential errors. Especially, we focus on automatically discovering minimal CCFDs. In this paper, we present context relativity to measure the relationship of CFDs. The overlap of the related CFDs can provide reasonable values which result in more accuracy consistency repairing, and some related CFDs are combined into CCFDs.Moreover,we prove that discovering minimal CCFDs is NP-complete and we design the precise method and the heuristic method. We also present the dominating value to facilitate the process in both the precise method and the heuristic method. Additionally, the context relativity of the CFDs affects the cleaning results. We will give an approximate threshold of context relativity according to data distribution for suggestion. The repairing results are approvedmore accuracy, even evidenced by our empirical evaluation.

Link prediction on temporal networks has a wide range of applications, such as facilitating individual relationship mining, user recommendation, and user behavior analysis. The traditional link prediction methods on temporal network only considered the structure of single-relational networks, which ignored the diversity of network link types and the influence between different link types. This paper proposes a temporal multi-relational network link prediction method combining personalized time interval and node embedding. Firstly, the node embedding is generated according to the structure of target network and auxiliary network which overcomes the defect of single network information sparseness; then, considering the diversity of link types, we construct the relationship formation sequence based on personalized time interval and the influence between different relationships for each link; next, the relationship formation sequence is modeled based on the Hawkes process, which takes product of the node embedding as the initial value to calculate the possibility of link formation. The method captures the dynamic characteristics and multi-relational property of the network, which is helpful to improve the accuracy of link prediction. Experimental results find that the proposed method has better performance and can be applied to large-scale networks.

Cross-network user identification is a technique to infer the potential links among the shared user entities across multiple networks. However, existing methods mainly rely on a small set of seed users which might not get enough evidence for identification. In this paper, we propose a cross-network user identification model based on two-phase expansion. On one hand, in order to effectively solve the cold start problem, we propose a global seed expansion method to expand the seed set. On the other hand, we propose a local search range expansion method with the aim to ensure higher accuracy at a lower time cost. Experiments demonstrate the effectiveness of our proposed model.

As considerable amounts of point-of-interest (POI) check-in data have been accumulated, POI recommendation has received much attention recently. It is well recognized that spatial–temporal information plays an important role in the user’s decision-making for visiting a POI. However, in time-aware POI recommendation, exploring temporal patterns on user preferences and incorporating multi-view factors for choosing preferred POIs are challenging issues to be resolved. To this end, we propose a novel Attentional Memory Network with Correlation-based Embedding (AMN-CE) for time-aware POI recommendation. Specifically, we first propose a correlation-based POI embedding method to capture geographical influence and interactive correlation between POIs. Sequentially, we design an attentional memory network, which is able to capture the micro-level relationship between time slot pairs. Furthermore, we propose a temporal-level attention mechanism to distinguish and dynamically adjust the influence strength of different time slots on user preferences at the target time slot. The experimental results on four real-life datasets demonstrate significant improvements of our proposed method compared with state-of-the-art models.

This work proposes an unsupervised topological features based entity disambiguation solution. Most existing studies leverage semantic information to resolve ambiguous references. However, the semantic information is not always accessible because of privacy or is too expensive to access. We consider the problem in a setting that only relationships between references are available. A structure similarity algorithm via random walk with restarts is proposed to measure the similarity of references. The disambiguation is regarded as a clustering problem and a family of graph walk based clustering algorithms are brought to group ambiguous references. We evaluate our solution extensively on two real datasets and show its advantage over two state-of-the-art approaches in accuracy.

Conditional functional dependencies (CFDs) are a critical technique for detecting inconsistencies while they may ignore some potential inconsistencies without considering the content relationship of data. Content-related conditional functional dependencies (CCFDs) are a type of special CFDs, which combine content-related CFDs and detect potential inconsistencies by putting content-related data together. In the process of cleaning inconsistencies, detection and repairing are interactive: 1) detection catches inconsistencies, 2) repairing corrects caught inconsistencies while may bring new inconsistencies. Besides, data are often fragmented and distributed into multiple sites. It consequently costs expensive shipment for inconsistencies cleaning. In this paper, our aim is to repair inconsistencies in distributed content-related data. We propose a framework consisting of an inconsistencies detection method and an inconsistencies repairing method, which work iteratively. The detection method marks the violated CCFDs for computing the inconsistencies which should be repaired preferentially. Based on the repairing-cost model presented in this paper, we prove that the minimum-cost repairing using CCFDs is NP-complete. Therefore, the repairing method heuristically repairs the inconsistencies with minimum cost. To improve the efficiency and accuracy of repairing, we propose distinct values and rules sequences. Distinct values make less data shipments than real data for communication. Rules sequences determine appropriate repairing sequences to avoid some incorrect repairs. Our solution is proved to be more effective than CFDs by empirical evaluation on two real-life datasets.

In most real life networks such as social networks and biology networks, a node often involves in multiple overlapping communities. Thus, overlapping community discovery has drawn a great deal of attention and there is a lot of research on it. However, most work has focused on community detection, which takes the whole network as input and derives all communities at one time. Community detection can only be used in offline analysis of networks and it is quite costly, not flexible and can not support dynamically evolving networks. Online community search which only finds overlapping communities containing a given node is a flexible and light-weight solution, and also supports dynamic graphs very well. However, in some scenarios, it requires overlapping community search for group query, which means that the input is a set of nodes instead of one single node. To solve this problem, we propose an overlapping community search framework for group query, including both exact and heuristic solutions. The heuristic solution has four strategies, some of which are adjustable and self-adaptive. We propose two parameters node degree and discovery power to trade off the efficiency and quality of the heuristic strategies, in order to make them satisfy different application requirements. Comprehensive experiments are conducted and demonstrate the efficiency and quality of both exact and heuristic solutions.

The top-k query on uncertain data set has been a very hot topic these years, and there have been many studies on uncertain top-k queries. Unfortunately, most of the existing algorithms only consider centralized processing environments, and they are not suitable for the large-scale data. In this paper, it is the first attempt to process probabilistic threshold top-k queries (an important uncertain top-k query, PT-k for short) in a distributed environment. We propose 3 efficient algorithms. The serial distributed approach adopts a new method, which only requires a few amount of calculations, to serially process PT-k queries in distributed environments. The global sorting first algorithm for PT-k query processing (GSP) is designed for improving the computation speed. In GSP, a distributed sorting operation is performed, and then we compute the candidates for PT-k queries in parallel. The query results can be computed by using a novel incremental method which can reduce the number of calculations. The local filtering first algorithm for PT-k query processing is designed for reducing the network overhead. Specifically, several filtering strategies are proposed to filter out redundant data locally, and then the incremental method in GSP is used to process the PT-k queries. Finally, the effectiveness of our proposed algorithms is verified through a series of experiments.

The distance-based outlier is a widely used definition of outlier. A point is distinguished as an outlier on the basis of the distances to its nearest neighbors. In this paper, to solve the problem of outlier computing in distributed environments, DBOZ, a distributed algorithm for distance-based outlier detection using Z-curve hierarchical tree (ZH-tree) is proposed. First, we propose a new index, ZH-tree, to effectively manage the data in a distributed environment. ZH-tree has two desirable advantages, including clustering property to help search the neighbors of a point, and hierarchical structure to support space pruning. We also design a bottom-up approach to build ZH-tree in parallel, whose time complexity is linear to the number of dimensions and the size of dataset. Second, DBOZ is proposed to compute outliers in distributed environments. It consists of two stages. 1) To avoid calculating the exact nearest neighbors of all the points, we design a greedy method and a new ZH-tree based k-nearest neighbor searching algorithm (ZHkNN for short) to obtain a threshold LW. 2) We propose a filter-and-refine approach, which first filters out the unpromising points using LW, and then outputs the final outliers through refining the remaining points. At last, the efficiency and the effectiveness of ZH-tree and DBOZ are testified through a series of experiments.

The problem of imbalanced data classification often exists in medical diagnosis. Traditional classification algorithms usually assume that the number of samples in each class is similar and their misclassification cost during training is equal. However, the misclassification cost of patient samples is higher than that of healthy person samples. Therefore, how to increase the identification of patients without affecting the classification of healthy individuals is an urgent problem. In order to solve the problem of imbalanced data classification in medical diagnosis, we propose a hybrid sampling algorithm called RFMSE, which combines the Misclassification-oriented Synthetic minority over-sampling technique (M-SMOTE) and Edited nearset neighbor (ENN) based on Random forest (RF). The algorithm is mainly composed of three parts. First, M-SMOTE is used to increase the number of samples in the minority class, while the over-sampling rate of M-SMOTE is the misclassification rate of RF. Then, ENN is used to remove the noise ones from the majority samples. Finally, RF is used to perform classification prediction for the samples after hybrid sampling, and the stopping criterion for iterations is determined according to the changes of the classification index (i.e. Matthews Correlation Coefficient (MCC)). When the value of MCC continuously drops, the process of iterations will be stopped. Extensive experiments conducted on ten UCI datasets demonstrate that RFMSE can effectively solve the problem of imbalanced data classification. Compared with traditional algorithms, our method can improve F-value and MCC more effectively.

Erratum: Ming-Dong Zhu, De-Rong Shen, Yue Kou, Tie-Zheng Nie, Ge Yu. A Framework for Supporting Tree-Like Indexes on the Chord Overlay. Journal of Computer Science and Technology 2013, 28(6): 962-972. DOI: 10.1007/s11390-013-1391-8.

The sequence data is one of the most common types the objects are described with and is also an important research subject that has caused a lot of attention to researchers. Mining hidden information from the sequence data is an important issue. Recently, the rapid developing deep learning technology achieves great success in biomedical information mining. In this paper, we propose a Deep Neural Block Cascade Networks(DeepNBCN) which is a general framework for sequence translating. Then we take protein secondary structure prediction as an important test target. DeepNBCN has a full-free adjustment mechanism of deep neural networks, in which every layer is structured as a block composed of one or more Feature Extractor named as module, and delivers features to the upper layer. DeepNBCN can model not only internal relations between amino acid sequence and Protein Secondary Structure(PSS), but also complex sequence relationship and dependency. We evaluate our model with two protein datasets. With a well designed architecture for PSS, the experimental results show that our model can achieve a better performance compared with the state of the art algorithms.

With the volume of data grows rapidly, the cost of detecting duplication entities has increased significantly in data cleaning. However, some real-time applications only need to identify as many duplicate entities as possible in a limited time, rather than all of them. The existing works adopt the sorting method to divide similar records into blocks, and arrange the processing order of blocks to detect duplicate entity progressively. However, this method only works well when the attributes of records are suitable for sorting. Therefore, this paper proposes a novel progressive de-duplicate method for records that can't be sorted by their attributes. The method distributes records into different blocks based on their features and generates a modified bloom filter index for each block. Then it uses the bloom filter to predict the probability of duplicate entities in this block, which determines the processing order of blocks to detect the duplicate entities more quickly. The comprehensive experiment shows that the number of duplicate detection by this algorithm in the finite time is far more efficient than other algorithms involved in the related works.

Nowadays, people prefer to take part in multiple social networks to enjoy different kinds of services. Consequently, a significant task is to identify users across networks. Most state-of-the-art works on this issue exploit user local structure features (e.g., friend, follow and followed). In this paper, we first proposes the notion of user global view features, which represent the location of users in the network. Then, we present an iterative two-stage algorithm (GAUI) using Global view features with user Attribute features to solve User Identification. In GAUI, we iteratively update pairwise similarity and predict new matching users. Certainly, we present a community based core anchor link filter strategy to reduce the computation cost, and present a stable matching based mapping strategy to improve the accuracy. At last, the experiments conducted on two real-world aligned networks demonstrate that our method has better performance on precision and recall.

MapReduce is a popular parallel data-processing system, and task scheduling is one of the kernel techniques in MapReduce. In many applications, users have requirements that their MapReduce jobs should be completed before specific deadlines. Hence, in this paper, a novel scheduling algorithm based on the most effective sequence (SAMES) is proposed for deadline-constraint jobs in MapReduce. First, according to the characteristics of MapReduce, we propose a novel sequence-based execution strategy for MapReduce jobs and a new concept, the effective sequence (ES). Then, we design some efficient approaches for finding ESes and choose the most effective sequence (MES) for job execution. We also propose methods for MES-updates and exception handling. Finally, we verify the effectiveness of SAMES through experiments. The experimental results show that SAMES is an efficient scheduling algorithm for deadline-constraint jobs in MapReduce.

Data consistency is one of the central issues of data quality management. Content-related conditional functional dependencies (CCFDs) are practical techniques for data consistency. CCFDs catch inconsistencies by putting content-related data together. Specially, repairing sequence plays a key role in consistency repairing. Some repairing sequences may bring unexpected results (e.g., incorrect repairs and results with extra repairing-cost). Hence, reasonable repairing sequences are advocated and readily supported by commercial system for better performance. To meet this need, this paper present a method of determining repairing sequence of inconsistencies in content-related data. (1) We present repairing sequence graph about CCFDs to select the inconsistencies which should be repaired preferentially. (2) We analyze the repairing mutex and discuss the interaction between repairing sequence and repairing mutex. (3) We proof that the problem of determining repairing sequence with minimum repairing-cost is NP-complete so that our method heuristically finds the appropriate repairing sequence. Our solution performs to be effective by empirical evaluation on three datasets.

Outlier detection is an important data mining task, whose target is to find the abnormal or atypical objects from a given dataset. The techniques for detecting outliers have a lot of applications, such as credit card fraud detection and environment monitoring. Our previous work proposed the Cluster-Based (CB) outlier and gave a centralized method using unsupervised extreme learning machines to compute CB outliers. In this paper, we propose a new distributed algorithm for the CB outlier detection (DACB). On the master node, we collect a small number of points from the slave nodes to obtain a threshold. On each slave node, we design a new filtering method that can use the threshold to efficiently speed up the computation. Furthermore, we also propose a ranking method to optimize the order of cluster scanning. At last, the effectiveness and efficiency of the proposed approaches are verified through a plenty of simulation experiments.

With the explosive growth of data, to support efficient data management including queries and updates, the database system is expected to provide tree-like indexes, such as R-tree, M-tree, B+-tree, according to different types of data. In the distributed environment, the indexes have to be scattered across the compute nodes to improve reliability and scalability. Indexes can speed up queries, but they incur maintenance cost when updates occur. In the distributed environment, each compute node maintains a subset of an index tree, so keeping the communication cost small is more crucial, or else it occupies lots of network bandwidth and the scalability and availability of the database system are affected. Further, to achieve the reliability and scalability for queries, several replicas of the index are needed, but keeping the replicas consistent is not straightforward. In this paper, we propose a framework supporting tree-like indexes, based on Chord overlay, which is a popular P2P structure. The framework dynamically tunes the number of replicas of index to balance the query cost and the update cost. Several techniques are designed to improve the efficiency of updates without the cost of performance of the queries. We implement M-tree and R-tree in our framework, and extensive experiments on real- life and synthetic datasets verify the efficiency and scalability of our framework.

Keyword query has attracted much research attention due to its simplicity and wide applications. The inherent ambiguity of keyword query is prone to unsatisfied query results. Moreover some existing techniques on Web query keyword query in relational databases and XML databases cannot be completely applied to keyword query in dataspaces. So we propose KeymanticES a novel keyword-based semantic entity search mechanism in dataspaces which combines both keyword query and semantic query features. And we focus on query intent disambiguation problem and propose a novel three-step approach to resolve it. Extensive experimental results show the effectiveness and correctness of our proposed approach.

With the growing amount of information available online, context-aware recommender systems have emerged to improve the precision of recommendation. Matrix factorization models are the state-of-the-art in these systems, especially for multi-context recommendation. However, existing models ignored either context influence or entity sensitivity. That is, they assume that one entity (user or item) shares the same factors across different contexts, or one context shares the same influence across different entities. In fact, for one context (or entity), its influence (or sensitivity) may be different with the changes of entities (or contexts). In this paper, we present a matrix factorization model for multi-context recommendation (namely ISMF). Unlike traditional models, ISMF considers both context influence and entity sensitivity. Instead of enforcing the same factors for each entity, we detail the factors as entity-intrinsic factors and entity-specific factors to represent entity-itself and context influence respectively. Meanwhile, we use some parameters acting on these factors to represent entity sensitivity. Also a matrix factorization algorithm for ISMF is proposed. We iteratively determine the factors and relevant parameters to maintain the precision for recommendation. The experiments demonstrate the feasibility and effectiveness of our method.

Outlier detection is an important data mining task, whose target is to find the abnormal or atypical objects from a given data set. The techniques for detecting outliers have a lot of applications, such as credit card fraud detection, environment monitoring, etc. In this paper, we proposed a new definition of outlier, called cluster-based outlier. Comparing with the existing definitions, the cluster-based outlier is more suitable for the complicated data sets that consist of many clusters with different densities. To detect cluster-based outliers, we first split the given data set into a number of clusters using unsupervised extreme learning machines. Then, we further design a pruning method technique to efficiently compute outliers in each cluster. at last, the effectiveness and efficiency of the proposed approaches are verified through plenty of simulation experiments.

Record linkage is the process of matching records from multiple databases that refer to the same entities and it has become an increasingly important subject in many application areas, including business, government, and health. When we collect data which is about people from these areas, integrating such data across organizations can raise privacy concerns. To prevent privacy breaches, ideally records should be linked in a private way such that no information other than the matching result is leaked in the process, this technique is called privacy-preserving record linkage (PPRL). Scalability is one of the main challenges in PPRL, therefore, many private blocking techniques have been developed for PPRL. They are aimed at reducing the number of record pairs to be compared in the matching process by removing obvious non-matching pairs without compromising privacy. However, they vary widely in their ability to balance competing goals of accuracy, efficiency and security. In this paper, we propose a novel private blocking approach for PPRL based on dynamic k-anonymous blocking and Paillier cryptosystem. In dynamic k-anonymous blocking, our approach dynamically generates blocks satisfying k-anonymity and more accurate values to represent the blocks with varying k. We also propose a novel similarity measure method which performs on the numerical attributes and combines with Paillier cryptosystem to measure the similarity of two blocks in security, which provides strong privacy guarantees that none information reveals. Experiments conducted on a public dataset of voter registration records validate that our approach is scalable to large databases and keeps a high quality of blocking. We compare our method with other techniques and demonstrate the increases in security and accuracy.

People today may participate in multiple social networks (Facebook, Twitter, Google+, etc.). Predicting the correspondence of the accounts that refer to the same natural person across multiple social networks is a significant and challenging problem. Formally, social networks that outline the relationships of a common group of people are defined as aligned networks, and the correspondence of the accounts that refer to the same natural person across aligned networks are defined as anchor links. In this paper, we learn the problem of Anchor Link Prediction (ALP). Firstly, two similarity metrics (Bi-Similarity BiS and Reliability Similarity ReS) are proposed to measure the similarity between nodes in aligned networks. And we prove mathematically that the node pair with the maximum BiS has higher probability to be an anchor link and a correctly predicted anchor link must have high ReS. Secondly, we present an iterative algorithm to solve the problem of ALP efficiently. Also, we discuss the termination of the algorithm to give a tradeoff between precision and recall. Finally, we conduct a series of experiments on both synthetic social networks and real social networks to confirm the effectiveness of our approach.

Caching is an important technique to enhance the efficiency of query processing. Unfortunately, traditional caching mechanisms are not efficient for deep Web because of storage space and dynamic maintenance limitations. In this paper, we present on providing a cache mechanism based on Top-K data source (KDS-CM) instead of result records for deep Web query. By integrating techniques from IR and Top-K, a data reorganization strategy is presented to model KDS-CM. Also some measures about cache management and optimization are proposed to improve the performances of cache effectively. Experimental results show the benefits of KDS-CM in execution cost and dynamic maintenance when compared with various alternate strategies.

The paper presents a novel benefit based query processing strategy for efficient query routing. Based on DHT as the overlay network, it first applies Nash equilibrium to construct the optimal peer group based on the correlations of keywords and coverage and overlap of the peers to decrease the time cost, and then presents a two-layered architecture for query processing that utilizes Bloom filter as compact representation to reduce the bandwidth consumption. Extensive experiments conducted on a real world dataset have demonstrated that our approach obviously decreases the processing time, while improves the precision and recall as well.

In many web integration applications, there are usually some sources that depict the same entity object with different descriptions, which leads to lots of conflicts. Resolving conflicts and finding the truth can be used to improve the quality of integration or to build a high-quality knowledge base, etc. In the single-truth data conflicting scenario, existing methods have limitations to distinguish false negative, also named as data missing, and false positive. So their source quality measurements are inadequate. Therefore, in this paper, we use recall and false positive rate to measure source quality and present a method to discover truth. The experimental results on three real-word data sets show that the proposed algorithm can effectively distinguish the data missing and false positive and improve the precision of truth discovery.

To evaluate how much a pair of entities or documents are similar is a common problem for current applications. Most approaches for this problem are based on the co-occurrence. However, different terms or words may represent the same entity or similar semantic in the real world since a concept often has more than one way of expression. Existing works always focus on computing semantic relatedness of words. But relatedness cannot reflect the similarity most of the time, on the other hand, most of their corpus are from common data sources such as Wikipedia and are not useful for the specialized vocabulary. In this paper, we propose a novel unsupervised approach for evaluating the semantic similarity between words by mapping texts to vector space and computing prior information. In our approach, we construct a model that can identify the words representing the same entity in special context even though they don't belong to the same concept. At last, we construct a network of words in which paths between words can reflect the evolution process of concepts. Our experimental results show that that our approach gives an effective solution to discover the semantic relationship between words, especially for words in specialty domains.

Comprehensive analysis of multi-domain texts has generated an important effect on text mining. Although the objects described by these multi-domain texts belong to different fields, they sometimes are overlapped partially; and linking these texts fragments which are overlapped or complementary is a necessary step for many tasks, such as entity resolution, information retrieval and text clustering. Previous works for computing text similarity mainly focus on string-based, corpus-based and knowledge-based approaches. However cross-domain texts exhibit very special features compared to texts in the same domain: (1) entity ambiguity, texts from different domains may contain various references to the same entity; (2) content skewness, cross domain texts are overlapped partially. In this paper, we propose a novel fine-grained approach based on text graph for evaluating the semantic similarity of cross-domain texts to link the similar parts. The experiment results show that our approach gives an effective solution to discover the semantic relationship between cross domain text fragments.

Locality Sensitive Hashing (LSH) is a popular method for high dimensional indexing and search over large datasets. However, little efforts have put forward to utilizing LSH in mobile applications for processing spatio-textual similarity queries, such as find nearby shopping centers that have a top ranked hair salon. In this paper, we present hybrid-LSH, a new LSH method for indexing data objects according to both their spatial location and their keyword similarity. Our hybrid-LSH approach has two salient features: First our hybrid-LSH carefully combines the spatial location based LSH and textual similarity based LSH to ensure the correctness of the spatial and textual similarity based NN queries. Second, we present an adaptive query-processing model to address the fixed range problem of traditional LSH and to handle queries with varying ranges effectively. Extensive experiments conducted on both synthetic and real datasets validate the efficiency of our hybrid LSH method.

A great deal of research has been dedicated to discover overlapping communities, as in most real life networks such as social networks and biology networks, a node often involves in multiple overlapping communities. However, most work has focused on community detection, which takes the whole graph as input and derives all communities at one time. Community detection can only be used in offline analysis of networks and it is quite costly, not flexible and can not support dynamically evolving networks. Online community search which only finds overlapping communities containing given nodes is a flexible and light-weight solution, and also supports dynamic graphs very well. Thus, in this paper, we study an efficient solution for overlapping community search problem. We propose an exact algorithm whose performance is highly improved by considering boundary node limitation and avoiding duplicate computations of multiple input nodes, and we also propose three approximate strategies which trade off the efficiency and quality, and can be adopted in different requirements. Comprehensive experiments are conducted and demonstrate the efficiency and quality of the proposed algorithms.

Entity resolution is a key aspect of data quality, identifying which records correspond to the same real world entity in data sources. Entity resolution is a hot topic in both research communities and industries. We introduce three approaches to solve different aspects of entity resolution. The first approach learns entity resolution classifiers with genetic algorithm and active learning. The second approach proposes a solution for joint entity resolution. The third approach makes match decision for unsupervised entity resolution by graph clustering. All the three approaches are effective in entity resolution tasks.

To resolve multiple classes of related entity representations jointly promotes accuracy of entity resolution. We propose a graph-based joint entity resolution model: GB-JER, who exploits a dynamic entity representation relationship graph. It contracts the neighborhood of the matched pair, where enrichment of semantics provides new evidences for subsequent entity resolution iteratively. Also GB-JER is an incremental approach. The experimental evaluation shows that GB-JER outperforms existing the state-of-the-art joint entity resolution approach in accuracy.

Schema heterogeneity among individual peers is an important issue in PDMS (Peer Data Management System). Schema mapping is a key technology to find the semantic matching relationship between schemas, and it plays an important role in PDMS. In this paper, we address the problem of schema mapping in PDMS, a typical decentralized network. Aiming at the limitations of previous methods, we propose a schema mapping model based on peer interest, schema structure information and query log, and we also considers the uncertainty of schema mapping during query propagation among peers. In our model, the peers with same interest organize a community and the schema mapping is handled in the interest community. We propose a query processing strategy in which the uncertainty of schema mapping in taken into account. In order to supplement the matching and reasoning, we mine the query log to discover the relationship between schema elements and refine the schema mapping further. Experimental results show that our method is feasible and effective for schema mapping in decentralized network.