288 results on '"Ming-Syan Chen"'
Search Results
2. AlignQ: Alignment Quantization with ADMM-based Correlation Preservation
- Author
-
Ting-An Chen, De-Nian Yang, and Ming-Syan Chen
- Published
- 2022
3. Epidemic Spread Optimization for Disease Containment with NPIs and Vaccination
- Author
-
Ya-Wen Teng, Yishuo Shi, De-Nian Yang, Wang-Chien Lee, Philip S. Yu, Ying-Liang Lu, and Ming-Syan Chen
- Published
- 2022
4. Efficient Two-stream Action Recognition on FPGA
- Author
-
Jia-Ming Lin, Ming-Syan Chen, Bin-Ray Wu, and Kuan-Ting Lai
- Subjects
Hardware architecture ,Source code ,Artificial neural network ,business.industry ,Computer science ,media_common.quotation_subject ,Optical flow ,Field (computer science) ,Domain (software engineering) ,Action (philosophy) ,Computer engineering ,Artificial intelligence ,business ,Field-programmable gate array ,media_common - Abstract
Action recognition is an important research field that has many applications in surveillance, video search, autonomous vehicles, etc. However, current state-of-the-art action classifiers are still not widely adopted in embedded applications yet. The major reason is that action recognition needs to process both spatial and temporal streaming data to precisely identify actions, which is compute- intensive and power hungry. To solve this issue, researchers start using FPGA to run action recognition models with minimum power. In this paper, we propose a new hardware architecture of action recognition on FPGA. Our model is based on the popular two-stream neural network. By optimizing the optical flow and convolution operations in the temporal domain, our method can achieve similar accuracy with one order of magnitude less operations than other C3D baseline models. We have implemented our model on Xilinx Ultrascale+ ZCU102 and released the source code.
- Published
- 2021
5. Influence Maximization Based on Dynamic Personal Perception in Knowledge Graph
- Author
-
Yishuo Shi, Ming-Syan Chen, Ya-Wen Teng, De-Nian Yang, Wang-Chien Lee, and Chih-Hua Tai
- Subjects
Social and Information Networks (cs.SI) ,FOS: Computer and information sciences ,Computer science ,Process (engineering) ,business.industry ,media_common.quotation_subject ,Approximation algorithm ,Computer Science - Social and Information Networks ,Maximization ,Machine learning ,computer.software_genre ,Information engineering ,Viral marketing ,Reachability ,Perception ,Artificial intelligence ,business ,computer ,Social influence ,media_common - Abstract
Viral marketing on social networks, also known as Influence Maximization (IM), aims to select k users for the promotion of a target item by maximizing the total spread of their influence. However, most previous works on IM do not explore the dynamic user perception of promoted items in the process. In this paper, by exploiting the knowledge graph (KG) to capture dynamic user perception, we formulate the problem of Influence Maximization based on Dynamic Personal Perception (IMDPP) that considers user preferences and social influence reflecting the impact of relevant item adoptions. We prove the hardness of IMDPP and design an approximation algorithm, named Dynamic perception for seeding in target markets (Dysim), by exploring the concepts of dynamic reachability, target markets, and substantial influence to select and promote a sequence of relevant items. We evaluate the performance of Dysim in comparison with the state-of-the-art approaches using real social networks with real KGs. The experimental results show that Dysim effectively achieves at least 6 times of influence spread in large datasets over the state-of-the-art approaches.
- Published
- 2021
6. Structure-Aware Parameter-Free Group Query via Heterogeneous Information Network Transformer
- Author
-
Philip S. Yu, Ming-Syan Chen, Hong-Han Shuai, Chuan Shi, De-Nian Yang, Hsi-Wen Chen, and Wang-Chien Lee
- Subjects
Structure (mathematical logic) ,Context model ,Group cohesiveness ,Information engineering ,Information retrieval ,Computer science ,Group (mathematics) ,Node (networking) ,Free group ,Transformer (machine learning model) - Abstract
Owing to a wide range of important applications, such as team formation, dense subgraph discovery, and activity attendee suggestions on online social networks, Group Query attracts a lot of attention from the research community. However, most existing works are constrained by a unified social tightness k (e.g., for k-core, or k-plex), without considering the diverse preferences of social cohesiveness in individuals. In this paper, we introduce a new group query, namely Parameter-free Group Query (PGQ), and propose a learning-based model, called PGQN, to find a group that accommodates personalized requirements on social contexts and activity topics. First, PGQN extracts node features by a GNN-based method on Heterogeneous Activity Information Network (HAIN). Then, we transform the PGQ into a graph-to-set (Graph2Set) problem to learn the diverse user preference on topics and members, and find new attendees to the group. Experimental results manifest that our proposed model outperforms nine state-of-the-art methods by at least 51% in terms of F1-score on three public datasets.
- Published
- 2021
7. Highly Parallel Sequential Pattern Mining on a Heterogeneous Platform
- Author
-
Chun-Chieh Chen, Hong-Han Shuai, Ming-Syan Chen, and Yu-Heng Hsieh
- Subjects
Computer science ,0202 electrical engineering, electronic engineering, information engineering ,Bitmap ,020201 artificial intelligence & image processing ,02 engineering and technology ,Parallel computing ,computer.file_format ,General-purpose computing on graphics processing units ,Sequential Pattern Mining ,computer - Abstract
Sequential pattern mining can be applied to various fields such as disease prediction and stock analysis. Many algorithms have been proposed for sequential pattern mining, together with acceleration methods. In this paper, we show that a heterogeneous platform with CPU and GPU is more suitable for sequential pattern mining than traditional CPU-based approaches since the support counting process is inherently succinct and repetitive. Therefore, we propose the PArallel SequenTial pAttern mining algorithm, referred to as PASTA, to accelerate sequential pattern mining by combining the merits of CPU and GPU computing. Explicitly, PASTA adopts the vertical bitmap representation of database to exploits the GPU parallelism. In addition, a pipeline strategy is proposed to ensure that both CPU and GPU on the heterogeneous platform operate concurrently to fully utilize the computing power of the platform. Furthermore, we develop a swapping scheme to mitigate the limited memory problem of the GPU hardware without decreasing the performance. Finally, comprehensive experiments are conducted to analyze PASTA with different baselines. The experiments show that PASTA outperforms the state-of-the-art algorithms by orders of magnitude on both real and synthetic datasets.
- Published
- 2018
8. Toward Green Computing: Striking the Trade-Off between Memory Usage and Energy Consumption of Sequential Pattern Mining on GPU
- Author
-
Ming-Syan Chen and Yu-Heng Hsieh
- Subjects
Energy conservation ,Green computing ,Knowledge extraction ,Computer science ,business.industry ,Distributed computing ,Data center ,Energy consumption ,General-purpose computing on graphics processing units ,business ,Scheduling (computing) ,Efficient energy use - Abstract
The energy consumption of the data centers grows rapidly in the recent years, especially due to the increasing usage of the energy consuming GPU. Note that reducing the energy consumption can not only lower the operating cost but also increase the capacity of the data center. Therefore, it is important to explore the energy efficiency of an algorithm. In this work, we analyze a trade-off between the mining efficiency and the energy consumption of parallel sequential pattern mining on GPU. Sequential pattern mining is an important topic in the field of knowledge discovery since accelerating sequential pattern mining enables the possibility of various real-time recommendation systems and many other applications. The knowledge of the trade-off helps to decide the best hardware configuration for data centers as well as develop a task scheduling algorithm in a heterogeneous environment with better energy efficiency. We first study how the memory usage affects the execution time with a program profiler. Then, we apply GPU power models to find the relationship between the memory usage and the energy consumption. Finally, we conduct extensive experiments on both synthetic and real datasets to validate our results.
- Published
- 2018
9. Massive parallelism for non-linear and non-stationary data analysis with GPGPU
- Author
-
Ming-Syan Chen, Chun-Chieh Chen, and Chih-Ya Shen
- Subjects
010504 meteorology & atmospheric sciences ,Computer science ,Data stream mining ,Volume (computing) ,Parallel computing ,010502 geochemistry & geophysics ,01 natural sciences ,Instruction set ,Parallel processing (DSP implementation) ,Scalability ,Algorithm design ,General-purpose computing on graphics processing units ,Massively parallel ,0105 earth and related environmental sciences - Abstract
In recent years, a large volume of natural signal data has become available for scientists because of the maturity of sensor techniques. However, the sensor data can form huge data streams that are non-linear and non-stationary. Existing methods cannot process such a large volume of data efficiently with a single CPU because of the high complexity of the algorithms. In this paper, we present Massive Parallelism GPU-Optimized Adaptive Data Analysis (MG-ADA), a new parallel signal data analysis algorithm that utilizes General-Purpose Graphics Programming Unit (GPGPU) to improve data scalability and reduce computation time for large non-linear and non-stationary datasets. We propose effective strategies to significantly improve the efficiency and scalability of MG-ADA. Our experimental results show that MG-ADA provides high scalability and significantly reduces the processing time in large datasets compared to other baseline algorithms.
- Published
- 2016
10. Client as a first-class citizen: Practical user-centric network MIMO clustering
- Author
-
Kun Tan, Kate Ching-Ju Lin, Ming-Syan Chen, and Wei-Liang Shen
- Subjects
3G MIMO ,Computer science ,business.industry ,Distributed computing ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,05 social sciences ,MIMO ,Testbed ,050801 communication & media studies ,020206 networking & telecommunications ,Throughput ,02 engineering and technology ,Spatial multiplexing ,0508 media and communications ,0202 electrical engineering, electronic engineering, information engineering ,business ,Cluster analysis ,Communication channel ,Computer network - Abstract
Recent advances have demonstrated the potential of network MIMO (netMIMO), which combines a practical number of distributed antennas as a virtual netMIMO AP (nAP) to improve spatial multiplexing of an WLAN. Existing solutions, however, either simply cluster nearby antennas as static nAPs, or dynamically cluster antennas on a per-packet basis so as to maximize the sum rate of the scheduled clients. To strike the balance between the above two extremes, in this paper, we present the design, implementation and evaluation of FlexNEMO, a practical two-phase netMIMO clustering system. Unlike previous per-packet clustering approaches, FlexNEMO only clusters antennas when client distribution and traffic pattern change, as a result being more practical to be implemented. A medium access control protocol is then designed to allow the clients at the center of nAPs to have a higher probability to gain access opportunities, but still ensure long-term fairness among clients. By combining on-demand clustering and priority-based access control, FlexNEMO not only improves antenna utilization, but also optimizes the channel condition for every individual client. We evaluated our design via both testbed experiments on USRPs and trace-driven emulations. The results demonstrate that FlexNEMO can deliver 94.7% and 93.7% throughput gains over static antenna clustering in a 4-antenna testbed and 16-antenna emulation, respectively.
- Published
- 2016
11. Ensemble of Diverse Sparsifications for Link Prediction in Large-Scale Networks
- Author
-
Yi-Ling Chen, Ming-Syan Chen, and Philip S. Yu
- Subjects
business.industry ,Computer science ,Approximation algorithm ,Algorithm design ,Artificial intelligence ,Data mining ,Machine learning ,computer.software_genre ,business ,Cluster analysis ,computer ,Classifier (UML) - Abstract
Previous research has aimed to lower the cost of handling large networks by reducing the network size via sparsification. However, when many edges are removed from the network, the information that can be used for link prediction becomes rather limited, and the prediction accuracy thereby drops significantly. To address this issue, we propose a framework called Diverse Ensemble of Drastic Sparsification (DEDS), which constructs ensemble classifiers with good accuracy while keeping the prediction time short. DEDS includes various sparsification methods that are designed to preserve different measures of a network. Therefore, DEDS can generate sparsified networks with significant structural differences and increase the diversity of the ensemble classifier, which is key to improving prediction performance. When a network is drastically sparsified to 0.1% of the original one, DEDS effectively relieves the drop in prediction accuracy and raises the AUC value from 0.52 to 0.70. With a larger sparsification ratio, DEDS is even able to outperform the classifier trained from the original network. As for the efficiency, more than 95% prediction cost can be saved when the network is sparsified to 1% of the original one. If the original network is disk-resident but can fit into main memory after being sparsified, as much as 99.94% of the prediction cost can be saved.
- Published
- 2015
12. Reducing Communication and Merging Overheads for Distributed Clustering Algorithms on the Cloud
- Author
-
Chun-Chieh Chen, Jen-Wei Huang, Ming-Syan Chen, and Tze-Yu Chen
- Subjects
Computer science ,business.industry ,Distributed computing ,Big data ,Cloud computing ,Load balancing (computing) ,Data dependency ,Data stream clustering ,CURE data clustering algorithm ,Scalability ,Canopy clustering algorithm ,Data synchronization ,business ,Cluster analysis - Abstract
Many distributed clustering algorithms have been proposed to speed up data clustering on huge database. However, the existing distributed clustering algorithms still suffer from many issues on distributed system such as data synchronization, insufficient scalability, and maintenance difficulties. In this paper, we propose two distributed clustering algorithms named DDC and DGC, which are based on the cloud computing technique. The main ideas of proposed algorithms are to achieve load balance according to an efficient data partition, to cluster more data on many machines in parallel without data dependency, and to merge the result on a machine efficiently with minimal information overlap. The experimental results show that DDC and DGC are able to reduce the execution time and achieve great scalability on the cloud.
- Published
- 2015
13. Modeling social influences from call records and mobile web browsing histories
- Author
-
Ming-Syan Chen, Jihg-Hong Lin, Jhao-Yin Li, and Mi-Yen Yeh
- Subjects
World Wide Web ,Social network ,business.industry ,Computer science ,Big data ,Mobile search ,Mobile Web ,Mobile telephony ,business ,Construct (philosophy) ,Heuristics ,Social influence - Abstract
Nowadays, companies are usually strongly interested in discovering the latent social influences among their customers since the information is highly valuable to their marketing strategies. In this paper, we study how to model the influence probabilities among the customers of a telecommunication company by analyzing their call records and mobile web browsing histories. We first construct a directed network using the phone call records. We verify whether the statistical properties of our constructed network follow the commonly known social network properties. Next, we propose several heuristics to measure the influence probabilities between users in the constructed network by analyzing both the call records and the mobile web browsing histories. Finally, we evaluate our proposed measurements by two prediction tasks, including predicting the lengths of a call and estimating the number of common website visits between two users. The results show that our proposed measurements are effective with better prediction accuracy.
- Published
- 2015
14. Revenue maximization for telecommunications company with social viral marketing
- Author
-
Hong-Han Shuai, Hsiang-Chun Hsu, De-Nian Yang, Chih-Ya Shen, Jihg-Hong Lin, Chung-Kuang Chou, and Ming-Syan Chen
- Subjects
Return on marketing investment ,Marketing mix modeling ,Digital marketing ,Social network ,Computer science ,business.industry ,Marketing effectiveness ,Marketing strategy ,Online advertising ,Marketing management ,Viral marketing ,Revenue ,Social media ,Marketing ,Marketing research ,business ,Telecommunications ,Relationship marketing - Abstract
Viral marketing, a marketing strategy that leverages the influence power in intimate relationship, has become more prevalent due to the popularity of online social networking services in recent years. Consumers are more likely to make a purchase based on social media referrals. Since marketing through social media and traditional channels may target on different audiences, how to maximize the revenue of a telecommunications company by employing different advertising ways and selecting initial users for advertisements is a critical problem. Therefore, in this paper, we formulate a new research problem, namely Cost-Aware Multi-wAy Influence maXimization (CAMAIX) to address the need mentioned above. We design a 1/2-approximation algorithm with various pruning and budget allocation strategies to solve CAMAIX efficiently. We conduct extensive experiments on a large-scale real dataset from a telecommunications company. The results show that our proposed algorithm outperforms the baseline algorithms in both solution quality and efficiency.
- Published
- 2015
15. Deadline-aware envy-free admission control in shared datacenter networks
- Author
-
Jiann-Min Ho, Pi-Cheng Hsiu, and Ming-Syan Chen
- Subjects
Service (systems architecture) ,Computer science ,business.industry ,Distributed computing ,Transport layer ,Batch processing ,Overhead (computing) ,Throughput ,Admission control ,Greedy algorithm ,business ,Protocol (object-oriented programming) ,Computer network - Abstract
Meeting flow deadlines is crucial for a business running its interactive applications in a shared datacenter. Current deadline-aware transport protocols fall short in terms of throughput and fairness, when datacenter tenants compete for network capacity by their deadline-sensitive traffic. This paper presents an admission control mechanism to work with a deadline-aware transport protocol. Following pay-as-you-use paradigm, we model a revenue-maximizing problem for the mechanism to admit a right fraction of deadline-constrained traffic to the underlying transport layer, while respecting per-flow fairness by an economic notion, envy-free pricing. To tackle fast-changing traffic, we propose a greedy algorithm for the problem in the mechanism, which can easily adopt a batch processing method to mitigate the incurred overhead. By packet-level simulation, we demonstrate that the admission control mechanism sustains high application throughput and good revenues in heavy traffic loads. In addition, we present two service policies, each of which is demonstrated to have a desirable service property in dynamic environments.
- Published
- 2015
16. Improving Serviceability for Virtual Clusters in Bandwidth-Constrained Datacenters
- Author
-
Jiann-Min Ho, Pi-Cheng Hsiu, and Ming-Syan Chen
- Subjects
Optimization problem ,Serviceability (computer) ,business.industry ,Virtual machine ,Computer science ,Distributed computing ,Real-time computing ,Virtual cluster ,Data center ,business ,computer.software_genre ,computer - Abstract
Virtual cluster is a useful resource descriptive model, in terms of virtual machines (VMs) and link bandwidth, for many data center applications that require predictable performance. Bandwidth-constrained data centers often use reservation schemes to statically allocate underlying physical resources to virtual clusters. However, due to highly varying workloads, existing reservation schemes may place VMs improperly, causing a waste of bandwidth reservation and eventually leading to rejecting new virtual cluster requests even the VM capacity is sufficient. In this paper, we propose a mechanism to detect and rectify such bandwidth-wasting VM placements via VM reshuffling. To compute a new VM placement accommodating new requests as many as possible, we formulate an optimization problem, with the objective of minimizing the reservations of limited bandwidth. The problem is NP-hard. We propose two efficient algorithms for a practical special case and the general case of the problem respectively. To evaluate our mechanism, we conduct simulation with the settings close to real data center environments. The results show that our mechanism with VM reshuffling achieves a significant reduction in rejecting virtual cluster requests and increases data center throughput over various high loads.
- Published
- 2015
17. Machine learning based rate adaptation with elastic feature selection for HTTP-based streaming
- Author
-
Kate Ching-Ju Lin, Yu-Lin Chien, and Ming-Syan Chen
- Subjects
computer.internet_protocol ,business.industry ,Computer science ,Real-time computing ,Feature selection ,Video quality ,Machine learning ,computer.software_genre ,Dynamic Adaptive Streaming over HTTP ,Video encoding ,Server ,Bandwidth (computing) ,Real Time Streaming Protocol ,Quality of experience ,Artificial intelligence ,business ,Adaptation (computer science) ,computer - Abstract
Dynamic Adaptive Streaming over HTTP (DASH) has become an emerging application nowadays. Video rate adaptation is a key to determine the video quality of HTTP-based media streaming. Recent works have proposed several algorithms that allow a DASH client to adapt its video encoding rate to network dynamics. While network conditions are typically affected by many different factors, these algorithms however usually consider only a few representative information, e.g., predicted available bandwidth or fullness of its playback buffer. In addition, the error in bandwidth estimation could significantly degrade their performance. Therefore, this paper presents Machine Learning-based Adaptive Streaming over HTTP (MLASH), an elastic framework that exploits a wide range of useful network-related features to train a rate classification model. The distinct properties of MLASH are that its machine learning-based framework can be incorporated with any existing adaptation algorithm and utilize big data characteristics to improve prediction accuracy. We show via trace-based simulations that machine learning-based adaptation can achieve a better performance than traditional adaptation algorithms in terms of their target quality of experience (QoE) metrics.
- Published
- 2015
18. SIEVE: Scalable user grouping for large MU-MIMO systems
- Author
-
Kate Ching-Ju Lin, Kun Tan, Ming-Syan Chen, and Wei-Liang Shen
- Subjects
Beamforming ,Coherence time ,Heuristic (computer science) ,Computer science ,business.industry ,Distributed computing ,MIMO ,Multi-user MIMO ,Bottleneck ,law.invention ,Sieve ,law ,Wireless ,Capacity loss ,business ,Communication channel - Abstract
Multi-user multiple input and multiple output (MU-MIMO) is one predominate approach to improve the wireless capacity. However, since the aggregate capacity of MU-MIMO heavily depends on the channel correlations among the mobile users in a beamforming group, unwisely selecting beamforming groups may result in reduced overall capacity, instead of increasing it. How to select users into a beamforming group becomes the bottleneck of realizing the MU-MIMO gain. The fundamental challenge for user selection is the large searching space, and hence there exists a tradeoff between search complexity and achievable capacity. Previous works have proposed several low complexity heuristic algorithms, but they suffer a significant capacity loss. In this paper, we present a novel MU-MIMO MAC, called SIEVE. The core of SIEVE design is its scalable multi-user selection module that provides a knob to control the aggressiveness in searching the best beamforming group. SIEVE maintains a central database to track the channel and the coherence time for each mobile user, and largely avoids unnecessary computing with a progressive update strategy. Our evaluation, via both small-scale testbed experiments and large-scale trace-driven simulations, shows that SIEVE can achieve around 90% of the capacity compared to exhaustive search.
- Published
- 2015
19. Distributed algorithms for k-truss decomposition
- Author
-
Chung-Kuang Chou, Ming-Syan Chen, and Pei-Ling Chen
- Subjects
Theoretical computer science ,business.industry ,Computer science ,Distributed algorithm ,Big data ,Graph (abstract data type) ,Truss ,Cloud computing ,business ,Tree decomposition ,Graph ,Vertex (geometry) - Abstract
k-truss, a type of cohesive subgraphs of a network, is an important measure for a social network graph. However, with the emergence of large online social networks, the running time of the traditional batch algorithms for k-truss decomposition is usually prohibitively long on such a graph with billions of edges and millions of vertices. Moreover, the size of a graph becomes too large to load into the main memory of a single machine. Currently, cloud computing has become an imperative way to process the big data. Thus, our aim is to design a scalable algorithm of k-truss decomposition in the scenario of cloud computing. In this paper, we first improve the existing distributed k-truss decomposition in the MapReduce framework. We then propose a theoretical basis for k-truss and use it to design an algorithm based on graph-parallel abstractions. Our experiment results show that our method in the graph-parallel abstraction significantly outperforms the methods based on MapReduce in terms of running time and disk usage.
- Published
- 2014
20. Diversified ranking on graphs from the influence maximization viewpoint
- Author
-
Ming-Syan Chen and Li-Yen Kuo
- Subjects
Diffusion problem ,business.industry ,Maximization ,Recommender system ,computer.software_genre ,Machine learning ,Random walk ,Graph ,Dilemma ,Ranking SVM ,Learning to rank ,Data mining ,Artificial intelligence ,business ,computer ,Mathematics - Abstract
To characterize the relationship between items, graph-based ranking algorithms are widely used in various applications, such as information retrieval, recommender system, and natural language processing. Many ranking approaches tackle the dilemma between relevance and diversity. Diversity is considered as a critical objective of reducing redundancy and retrieving prestige information that has high coverage. However, the traditional evaluation of diversification is found to be deficient. In this paper, we address the coverage problem from a viewpoint of influence diffusion. Firstly, we transform the coverage problem into the diffusion problem and propose a novel measure called essential influence that combines relevance and diversity into a single function. Next, we propose a reinforced random walk, InfRank, of which the heuristic function is based on the essential influence. We applied InfRank on two applications, ranking in networks and tag recommendation. Our approach outperforms existing network-based ranking methods.
- Published
- 2014
21. Cluster cascades: Infer multiple underlying networks using diffusion data
- Author
-
Ming-Hao Yang, Chung-Kuang Chou, and Ming-Syan Chen
- Published
- 2014
22. Video Event Detection by Inferring Temporal Instance Labels
- Author
-
Kuan-Ting Lai, Felix X. Yu, Shih-Fu Chang, and Ming-Syan Chen
- Subjects
Computer science ,business.industry ,Video tracking ,Pooling ,Search engine indexing ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Pattern recognition ,Latent variable ,Artificial intelligence ,Representation (mathematics) ,business ,Event (probability theory) - Abstract
Video event detection allows intelligent indexing of video content based on events. Traditional approaches extract features from video frames or shots, then quantize and pool the features to form a single vector representation for the entire video. Though simple and efficient, the final pooling step may lead to loss of temporally local information, which is important in indicating which part in a long video signifies presence of the event. In this work, we propose a novel instance-based video event detection approach. We represent each video as multiple 'instances', defined as video segments of different temporal intervals. The objective is to learn an instance-level event detection model based on only video-level labels. To solve this problem, we propose a large-margin formulation which treats the instance labels as hidden latent variables, and simultaneously infers the instance labels as well as the instance-level classification model. Our framework infers optimal solutions that assume positive videos have a large number of positive instances while negative videos have the fewest ones. Extensive experiments on large-scale video event datasets demonstrate significant performance gains. The proposed method is also useful in explaining the detection results by localizing the temporal segments in a video which is responsible for the positive detection.
- Published
- 2014
23. On Pattern Preserving Graph Generation
- Author
-
De-Nian Yang, Ming-Syan Chen, Philip S. Yu, Hong-Han Shuai, and Chih-Ya Shen
- Subjects
Degree (graph theory) ,Computer science ,Graph theory ,computer.software_genre ,Degree distribution ,Graph ,Graph bandwidth ,Clique-width ,Graph (abstract data type) ,Algorithm design ,Data mining ,Cluster analysis ,computer ,Complement graph ,MathematicsofComputing_DISCRETEMATHEMATICS ,Clustering coefficient - Abstract
Real datasets always play an essential role in graph mining and analysis. However, nowadays most available real datasets only support millions of nodes. Therefore, the literature on Big Data analysis utilizes statistical graph generators to generate a massive graph (e.g., billions of nodes) for evaluating the scalability of an algorithm. Nevertheless, current popular statistical graph generators are properly designed to preserve only the statistical metrics, such as the degree distribution, diameter, and clustering coefficient of the original social graphs. Recently, the importance of frequent graph patterns has been recognized in the various works on graph mining, but unfortunately this crucial criterion has not been noticed in the existing graph generators. To address this important need, we make the first attempt to design a Pattern Preserving Graph Generation (PPGG) algorithm to generate a graph including all frequent patterns and three most popular statistical parameters: degree distribution, clustering coefficient, and average vertex degree. The experimental results show that PPGG, which we have released as a free download, is efficient and able to generate a billion-node graph in approximately 10 minutes, much faster than the existing graph generators.
- Published
- 2013
24. An Efficient Approach to Updating Closeness Centrality and Average Path Length in Dynamic Networks
- Author
-
Mi-Yen Yeh, Chia-Chen Yen, and Ming-Syan Chen
- Subjects
Discrete mathematics ,Shortest path problem ,K shortest path routing ,Directed graph ,Centrality ,Random walk closeness centrality ,Average path length ,Algorithm ,Longest path problem ,Distance ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Closeness centrality measures the communication efficiency of a specific vertex within a network while the average path length (APL) measures that of the whole network. Since the nature of these two measurements is based on the computation of all-pair shortest path distances, one can perform the breadth-first search method starting at every vertex and obtain the two measurements. However, as the edge counts in the real-world networks like Facebook increase over time, this naive way is obviously inefficient. In this paper, we proposed CENDY, an efficient approach to updating Closeness centrality and average path length in Dynamic networks when there is an edge insertion or deletion. In CENDY, we derived some theoretical properties to quickly identify a set of vertices whose shortest path changed after an edge update, and then update the closeness centralities of those vertices only as well as the APL of the graph by a few of single-source shortest path computations. We conducted extensive experiments to show that, when compared to the existing methods of computing exact or approximate values, CENDY outperformed others in significantly low update time while providing exact values of the two measurements on various real-world graph datasets.
- Published
- 2013
25. Efficient large graph pattern mining for big data in the cloud
- Author
-
Chun-Chieh Chen, Kuan-Wei Lee, De-Nian Yang, Ming-Syan Chen, and Chih-Chieh Chang
- Subjects
Graph database ,business.industry ,Computer science ,Data stream mining ,Big data ,Graph partition ,Cloud computing ,Graph theory ,computer.software_genre ,Graph ,Data set ,Scalability ,Graph (abstract data type) ,Data mining ,business ,computer - Abstract
Mining big graph data is an important problem in the graph mining research area. Although cloud computing is effective at solving traditional algorithm problems, mining frequent patterns of a massive graph with cloud computing still faces the three challenges: 1) the graph partition problem, 2) asymmetry of information, and 3) pattern-preservation merging. Therefore, this paper presents a new approach, the cloud-based SpiderMine (c-SpiderMine), which exploits cloud computing to process the mining of large patterns on big graph data. The proposed method addresses the above issues for implementing a big graph data mining algorithm in the cloud. We conduct the experiments with three real data sets, and the experimental results demonstrate that c-SpiderMine can significantly reduce execution time with high scalability in dealing with big data in the cloud.
- Published
- 2013
26. Query by Impression: A Novel Place Query System with Adjacency Constraints
- Author
-
Shih-Han Lin, Chi-Yao Tseng, and Ming-Syan Chen
- Subjects
Spatial query ,Query expansion ,Web search query ,Information retrieval ,Web query classification ,Computer science ,Sargable ,Query language ,Query optimization ,computer ,RDF query language ,computer.programming_language - Abstract
Place query is one of the most fundamental applications, and traditional use cases include finding the exact spatial location of a place and searching for a specific type of places in a given spatial range. On the other hand, there is another possibility that you may want to recommend a visited place to friends but forget the complete name of it. You have vague impressions on it and only remember the information of the place type, the rough range of the place, and some places near it. To enable the capability of query by impression that has not been fully explored in the literature, we define a new place query problem called Place Query with Adjacency Constraints (abbreviated as PQAC). We propose a naive approach and two enhancement algorithms, distance pre-calculating algorithm and grid indexing algorithm, to achieve greater efficiency that can satisfy the real-time need of this place query service. We implement the Query By Impression (abbreviated as QBI) system with a real metropolitan place dataset consisting of more than 40,000 place records from Google Place API. Several experiments are conducted to validate the efficiency and effectiveness of the proposed QBI system.
- Published
- 2013
27. Sample-Specific Late Fusion for Visual Category Recognition
- Author
-
Ming-Syan Chen, Guangnan Ye, Dong Liu, Kuan-Ting Lai, and Shih-Fu Chang
- Subjects
Fusion ,Image fusion ,Contextual image classification ,business.industry ,Computer science ,Category recognition ,Cognitive neuroscience of visual object recognition ,Pattern recognition ,Machine learning ,computer.software_genre ,Categorization ,Artificial intelligence ,business ,computer ,Classifier (UML) - Abstract
Late fusion addresses the problem of combining the prediction scores of multiple classifiers, in which each score is predicted by a classifier trained with a specific feature. However, the existing methods generally use a fixed fusion weight for all the scores of a classifier, and thus fail to optimally determine the fusion weight for the individual samples. In this paper, we propose a sample-specific late fusion method to address this issue. Specifically, we cast the problem into an information propagation process which propagates the fusion weights learned on the labeled samples to individual unlabeled samples, while enforcing that positive samples have higher fusion scores than negative samples. In this process, we identify the optimal fusion weights for each sample and push positive samples to top positions in the fusion score rank list. We formulate our problem as a L∞ norm constrained optimization problem and apply the Alternating Direction Method of Multipliers for the optimization. Extensive experiment results on various visual categorization tasks show that the proposed method consistently and significantly beats the state-of-the-art late fusion methods. To the best knowledge, this is the first method supporting sample-specific fusion weight learning.
- Published
- 2013
28. Highly Scalable Sequential Pattern Mining Based on MapReduce Model on the Cloud
- Author
-
Chun-Chieh Chen, Ming-Syan Chen, and Chi-Yao Tseng
- Subjects
Computer science ,business.industry ,Big data ,Cloud computing ,AC power ,Load balancing (computing) ,computer.software_genre ,Upgrade ,Virtual machine ,Scalability ,Algorithm design ,Data mining ,business ,computer - Abstract
Sequential pattern mining is an essential data mining technique that has been widely applied to many real world applications. However, traditional algorithms generally suffer from the scalability problem when dealing with big data. In this paper, we aim to significantly upgrade the scale and propose Sequential PAttern Mining algorithm based on MapReduce model on the Cloud (abbreviated as SPAMC). Derived from the prior SPAM algorithm, we design an iterative MapReduce framework to efficiently generate and prune candidate patterns when constructing the lexical sequence tree. This framework not only distributes the sub-tasks of tree construction to independent mappers in parallel, but also enables the parallel processing of support counting. We conduct extensive experiments on the cloud environment of 32 virtual machines with up to 12.8 million transactional sequences. Experimental results show that SPAMC can significantly reduce mining time with big data, achieve extremely high scalability, and provide perfect load balancing on the cloud cluster.
- Published
- 2013
29. Privacy-Preserving SimRank over Distributed Information Network
- Author
-
Yu-Wei Chu, Ming-Syan Chen, Chih-Hua Tai, and Philip S. Yu
- Subjects
Information privacy ,business.industry ,Computer science ,Privacy software ,Cryptographic protocol ,Similarity measure ,Encryption ,computer.software_genre ,SimRank ,Similarity (network science) ,Data mining ,Cluster analysis ,business ,computer - Abstract
Information network analysis has drawn a lot attention in recent years. Among all the aspects of network analysis, similarity measure of nodes has been shown useful in many applications, such as clustering, link prediction and community identification, to name a few. As linkage data in a large network is inherently sparse, it is noted that collecting more data can improve the quality of similarity measure. This gives different parties a motivation to cooperate. In this paper, we address the problem of link-based similarity measure of nodes in an information network distributed over different parties. Concerning the data privacy, we propose a privacy-preserving Sim Rank protocol based on fully-homomorphic encryption to provide cryptographic protection for the links.
- Published
- 2012
30. An efficient sequential pattern mining algorithm for motifs with gap constraints
- Author
-
Ming-Syan Chen and Vance Chiang-Chi Liao
- Subjects
Molecule mining ,PrefixSpan ,Biological data ,ComputingMethodologies_PATTERNRECOGNITION ,Computer science ,Functional significance ,Data mining ,Sequential Pattern Mining ,computer.software_genre ,Algorithm ,computer - Abstract
Mining biological data can provide insight into various realms of biology, such as finding co-occurring biosequences, which is essential for biological analyses and data mining. Sequential pattern mining reveals all-length implicit motifs, which have specific structures and are of functional significance in biological sequences. Traditional sequential pattern mining algorithms are inefficient for small alphabets and long sequences, such as DNA and protein sequences; therefore, it is necessary to move away from these algorithms. An approach called the Depth-First Spelling algorithm for mining sequential patterns (motifs) with Gap constraints in biological sequences (referred to as DFSG) is proposed in this work. In biological sequences, DFSG runtime is substantially shorter than that of GenPrefixSpan, where GenPrefixSpan is a method based on PrefixSpan (PrefixSpan is one of the fastest algorithms in traditional sequential pattern mining algorithms).
- Published
- 2012
31. On reconfigurable association rule mining
- Author
-
Wen-Tsai Liao and Ming-Syan Chen
- Subjects
Random access memory ,Speedup ,Knowledge extraction ,Association rule learning ,Computer science ,InformationSystems_DATABASEMANAGEMENT ,Reconfigurable hardware architecture ,Graph (abstract data type) ,Data mining ,Architecture ,computer.software_genre ,computer - Abstract
As one of the most important techniques for knowledge discovery, association rule mining is known to be very computational intensive. Many hardware architectures were proposed to speed up association rule mining. Generally, theses methods are based on the usage of systolic arrays with preserved hardware resources. In this paper, we propose a reconfigurable hardware architecture which is designed to use the hardware resources more efficiently than existing methods. Explicitly, our platform can dynamically allocate cell resources according to the number of items of a candidate itemset. At the same time, our platform is able to deal with the generation of initial frequent itemsets. Note that the number of frequent itemsets with fewer items is much larger than that of frequent itemsets with more items. In view of this, our platform is designed to use less hardware resources to deal with frequent itemsets with fewer items and reconfigure the hardware with more resources to handle frequent itemsets with more items. As such, we can process more frequent itemsets than those employing the architecture with preserved resources. In view of the growing complexity of graph mining, it has become essential to explore the approach of hardware assisted mining for better mining efficiency.
- Published
- 2012
32. Efficient mining structural motifs for biosequences with intra- and inter-block gap constraints
- Author
-
Vance Chiang-Chi Liao and Ming-Syan Chen
- Subjects
Matrix (mathematics) ,Computer science ,Process (computing) ,Functional significance ,Table (database) ,Structural motif ,Formal verification ,Algorithm ,Block size ,Block (data storage) - Abstract
Among the biological sequences, sequential pattern mining reveals implicit motifs/patterns, which are of functional significance and have specific structures. Small alphabets and long sequences, such as DNA and protein sequences, are difficult to handle by traditional sequential pattern mining algorithms. Furthermore, the intra- and inter-blocked gap constraints can deal with the substitutions, insertions, loops, and deletions in evolution process. Hence we propose an approach called Depth-first spelling algorithm for mining structural motifs with Intra- and inter-Block gap constraints in biological sequences (referred to as DIB). DIB has two execution steps. First, it constructs a three-dimensional table of sequences by scanning the given dataset once. Second, DIB-Exuberance generates intra- and inter-blocked gap sequential patterns. Candidate intra- and inter-blocked gap sequential pattern spelling and pattern verification are carried out by DIB-Exuberance in a depth-first manner. Intra and inter gap constraints are handled by the intra- and inter-block counting matrices. The block size matrix deals with intra- and inter-block size constraints. In biological sequences, DIB's runtime is much shorter than BASIC.
- Published
- 2012
33. SocFeedViewer: A Novel Visualization Technique for Social News Feeds Summarization on Social Network Services
- Author
-
Ming-Syan Chen, Yu-Jen Chen, and Chi-Yao Tseng
- Subjects
Social network ,Multimedia ,business.industry ,Computer science ,media_common.quotation_subject ,Social web ,computer.software_genre ,Automatic summarization ,Information overload ,Visualization ,World Wide Web ,Data visualization ,Reading (process) ,Web service ,business ,computer ,media_common - Abstract
Online social network services, such as Facebook and Twitter, have become increasingly popular recently. More and more users are accustomed to regularly reading the latest news feeds and interacting with friends on these social websites. However, when the number of friends increases to a large extent, users will receive hundreds of messages in a day and may be overwhelmed by the information overload. To alleviate this problem, we propose a novel visualization technique for social news feeds summarization on social web services. The proposed system SocFeedViewer can produce an egocentric network graph based on the news feeds generated in an arbitrary period of time. This graph provides an overview of those who have generated news feeds during this time period. To enhance the reading experience, we incorporate community detection, connectivity analysis, and importance analysis into our system to make users capable of preferentially surfing news feeds that are more significant and interesting.
- Published
- 2012
34. Operating electric taxi fleets: A new dispatching strategy with charging plans
- Author
-
Ming-Syan Chen, Jun-Li Lu, Yu-Ching Hsu, Shun-Neng Yang, Chai-Hien Gan, and Mi-Yen Yeh
- Subjects
Transport engineering ,Waiting time ,Working hours ,Engineering ,Power demand ,Order (business) ,business.industry ,Taxis ,Public policy ,business - Abstract
In this paper, we propose a dispatching strategy with charging plans upon the client requests for a commercial fleet of pure electric taxis. To boost the green industry, promoting the development of electrical vehicles is one of the most important policies of many governments. In a new scenario that the commercial taxi fleets run electrical vehicles as the main transportation, traditional dispatching policies for general gasoline taxis are no longer effective. It is because those policies do not need to consider the newly generated issues for the electrical vehicles such as the endurance and the related charging problems when dispatching them. In addition, taxi drivers may doubt whether their working hours would be occupied by the possibly long waiting time of power recharging and thus decrease the chances to carry clients. To overcome the above issues, this paper proposes a new dispatching policy in consideration of the taxi demand, the remaining power of electrical taxis, and the availability of battery charging/switching stations in order to lower the waiting time of power recharging and thus increase the workable hours for taxi drivers. Simulation results show that our dispatching strategy can effectively reduce the waiting time for charging and increase the chances of taking clients compared to some random dispatching strategy.
- Published
- 2012
35. Identities Anonymization in Dynamic Social Networks
- Author
-
Peng-Jui Tseng, Chih-Hua Tai, Ming-Syan Chen, and Philip S. Yu
- Subjects
Information privacy ,Social network ,Privacy by Design ,Computer science ,business.industry ,Privacy software ,Internet privacy ,Data publishing ,Adversary ,Computer security ,computer.software_genre ,business ,computer ,Anonymity - Abstract
Privacy in social network data publishing is always an important concern. Nowadays most prior privacy protection techniques focus on static social networks. However, there are additional privacy disclosures in dynamic social networks due to the sequential publications. In this paper, we first show that the risks of vertex and community re-identification exist in a dynamic social network, even if the release at each time instance is protected by a static anonymity scheme. To prevent vertex and community re-identification in a dynamic social network, we propose novel dynamic k^w-structural diversity anonymity, where w is the time that an adversary can monitor a victim. This scheme extends the k-structural diversity anonymity to a dynamic scenario. We also present a heuristic to anonymize the releases of networks to satisfy the proposed privacy scheme. The evaluations show that our approach can retain much of the characteristics of the networks while confirming the privacy protection.
- Published
- 2011
36. FISIP: A Distance and Correlation Preserving Transformation for Privacy Preserving Data Mining
- Author
-
Ming-Syan Chen, Jen-Wei Huang, and Jun-Wei Su
- Subjects
Privacy preserving ,Correlation ,Information privacy ,Third party ,Computer science ,Data mining ,Information loss ,computer.software_genre ,First order ,computer - Abstract
This paper devises a transformation scheme to protect data privacy in the case that data have to be sent to the third party for the analysis purpose. Most conventional transformation schemes suffer from two limits, i.e., the algorithm dependency and the information loss. In this work, we propose a novel privacy preserving transformation scheme without these two limitations. The transformation is referred to as FISIP. Explicitly, by preserving three basic properties, i.e., the first order sum, the second order sum and inner products, of the private data, mining algorithms which depend on these three properties can still be applied to public data. Specifically, any distance-based or correlation-based algorithm has the same performance on the transformed public data as on the original private data. Special perturbation can be added into FISIP transformations to increase the protection level. In the experimental results, FISIP attains data usefulness and data robustness at the same time. In summary, FISIP is able to provide a privacy preserving scheme that preserves the distance and the correlation of the private data after the transformation to the public data.
- Published
- 2011
37. PISAR: Progressive image search and recommendation system by auto-interpretation and user behavior
- Author
-
Ming-Syan Chen, Meng-Cheng Chen, Chi-Yao Tseng, and Jen-Wei Huang
- Subjects
Information retrieval ,Association rule learning ,Computer science ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Recommender system ,Semantics ,computer.software_genre ,Image (mathematics) ,Support vector machine ,Search engine ,Feature (computer vision) ,Data mining ,computer ,Image retrieval ,Semantic gap - Abstract
Many image search engines nowadays still struggle with the semantic gap between low level image features and high level image concepts. Some solutions are proposed to bridge the gap by using surrounding texts of images or by adding tags on images by single user. However, they can only provide obscure or limited information about images. Another problem is that users may not know exactly what they want when they search for images. In this work, we proposed a Progressive Image Search And Recommendation system, named as PISAR, to reduce the semantic gap by incorporating the auto-interpretation and user behavior. PISAR is able to progressively improve the interpretation of images and provide a list of recommendation. The evaluation results show that with the help of auto-interpretation and user behavior, the performance of search results and recommendation results can be progressively improved.
- Published
- 2011
38. Orientation histogram of SIFT displacement for recognizing actions in broadcast videos
- Author
-
Chaur-Heh Hsieh, Kuan-Ting Lai, Ming-Syan Chen, and Mao-Fu Lai
- Subjects
Orientation (computer vision) ,business.industry ,Feature extraction ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Optical flow ,Scale-invariant feature transform ,Pattern recognition ,Frame rate ,Field (computer science) ,Displacement (vector) ,Histogram ,Computer vision ,Artificial intelligence ,business ,Mathematics - Abstract
Human actions are diversified and complicated, and hence difficult to be recognized by artificial intelligence systems. Recognizing actions in broadcast videos is even more challenging due to low resolution and frame rate. During the past decades, many talented researchers are devoted to this field, and several promising algorithms are developed to achieve great performance. The well known methods include optical flow, 3D Harris, Cuboid detector, 3D SIFT, to name a few. Inspired by preceding algorithms, we propose using SIFT displacement between consecutive frames to extract human motions in broadcast videos. Motion descriptors are orientation histogram computed from displacement vectors voted by moving distances. Geometric information is also employed by dividing frames into sub-regions. Experimental results indicate that the proposed approach is effective and outperforms other state-of-the-art methods.
- Published
- 2011
39. Photo identity tag suggestion using only social network context on large-scale web services
- Author
-
Ming-Syan Chen and Chi-Yao Tseng
- Subjects
World Wide Web ,Upload ,Social network ,Computer science ,business.industry ,Process (engineering) ,Identity (object-oriented programming) ,Context (language use) ,Web service ,business ,computer.software_genre ,computer ,Ranking (information retrieval) - Abstract
Recently, uploading photos and adding identity tags on social network services are prevalent. Although some researchers have considered leveraging context to facilitate the process of tagging, these approaches still rely mainly on face recognition techniques that use visual features of photos. However, since the computational and storage costs of these approaches are generally high, they cannot be directly applicable to large-scale web services. To resolve this problem, we explore using only social network context to generate the top-k list of photo identity tag suggestion. The proposed method is based on various co-occurrence contexts that are related to the question of who may appear in this photo. An efficient ranking algorithm is designed to satisfy the real-time needs of this application. We utilize public album data of 400 volunteers from Facebook to verify that our approach can efficiently provide accurate suggestions with less additional storage requirement.
- Published
- 2011
40. Time-critical event dissemination in geographically distributed clouds
- Author
-
Jan-Ming Ho, Ming-Syan Chen, and Chi-Jen Wu
- Subjects
business.industry ,Computer science ,Distributed computing ,Data management ,Interoperability ,Scalability ,Capital cost ,Cloud computing ,Overlay ,Intercloud ,Latency (engineering) ,business ,Computer network - Abstract
Cloud computing has rapidly become a new infrastructure for organizations to reduce their capital cost in IT investment and to develop planetary-scale distributed applications. One of the fundamental challenges in geographically distributed clouds is to provide efficient algorithms for supporting intercloud data management and dissemination. In this paper, we present Plume, a generic distributed intercloud overlay for time-critical event dissemination services. Plume aims at improving the interoperability of interclouds in time-critical event dissemination services, such as computing policy updating, message sharing, event notifications and so forth. Plume organizes these distributed clouds into a novel quorum ring overlay to support a constant event dissemination latency. Our numerical results show that the proposed Plume greatly improves the efficiency as compared to a DHT-based overlay approach and provides better scalability than the fully-meshed approach.
- Published
- 2011
41. Le Festin: Shop sign recognition assisted food recommendation system
- Author
-
Ming-Syan Chen, I-Chun Liu, and I-Chun Chen
- Subjects
Mobile radio ,World Wide Web ,business.industry ,Computer science ,Server ,Feature extraction ,Sentiment analysis ,Wearable computer ,The Internet ,Recommender system ,business ,Mobile device - Abstract
As the popularity of smart phone, Web 2.0 data, and 3G mobile networks, people are getting used to search for information from the Internet anytime and everywhere. However, typing text query on mobile device and digesting a large number of retrieved user-generated data are both inconvenient for users. To overcome these troubles, we develop a wearable system, Le Festin, which is a shop sign recognition assisted food recommendation system. In Le Festin, food recommendation list and restaurant-related information can be easily obtained by just snapping restaurant signboard. The system is composed of two main techniques: Chinese character recognition (CCR) and blog mining. We integrate a powerful CCR algorithm which has the accuracy about 90% and propose a new blog mining method which is combined with food name extraction and sentiment analysis. By merging the above two functions, a convenient system is built.
- Published
- 2010
42. A two-phase hybrid codebook generation technique for vector quantization
- Author
-
Chia-Chen Yen, Chih-Ya Shen, and Ming-Syan Chen
- Subjects
Linde–Buzo–Gray algorithm ,Image quality ,business.industry ,Vector quantization ,Codebook ,Pattern recognition ,k-nearest neighbors algorithm ,Local optimum ,Computer Science::Computer Vision and Pattern Recognition ,Distortion ,Artificial intelligence ,business ,Time complexity ,Mathematics - Abstract
In general, the codebook generation for vector quantization emphasizes two major topics: minimizing the distortion error to improve the quality of the reconstructed image and reducing the time cost to enhance the efficiency. LBG is one of the famous codebook generation techniques proposed in recent decades. LBG was widely utilized due to its simplicity. However, it only guarantees a local optimum. To be an alternative to LBG, the pair-wise nearest neighbor (PNN) algorithm was devised to obtain better results. By the fully searching operation, PNN needs a large amount of calculations. In this paper, a Two-Phase Codebook Generation (TPCG) technique based on the relative pixel magnitudes is presented. With the pre-process of image decomposition, TPCG applies a simple quantifier to divide low frequency blocks in linear time, and then employs a new proposed k-nearest neighbor graph construction approach with Double Linked Algorithm instead of PNN for high frequency blocks. The experiments reveal that TPCG has accuracy approximates to that of PNN while keeping a low time cost.
- Published
- 2010
43. Time-Critical Data Dissemination in Cooperative Peer-to-Peer Systems
- Author
-
Chi-Jen Wu, Kai-Hsiang Yang, Jan-Ming Ho, Cheng-Ying Li, and Ming-Syan Chen
- Subjects
business.industry ,Computer science ,Distributed computing ,Peer-to-peer ,computer.software_genre ,Network topology ,Server ,The Internet ,business ,Adaptation (computer science) ,Protocol (object-oriented programming) ,computer ,Dissemination ,Computer network - Abstract
How to rapidly disseminate a large-sized file to many recipients is a fundamental problem in many applications, such as updating software patches and distributing large scientific data sets. In this paper, we present the Bee protocol, which is a cooperative peer-to-peer data dissemination protocol aiming at minimizing the maximum dissemination time for all peers to obtain time-critical data, such as critical patch updates. Bee is a decentralized protocol that organizes peers into a randomized mesh-based overlay and each peer only works with local knowledge. We devise a slowest peer first strategy to boost the speed of dissemination, and a topology adaptation algorithm that provides the most efficient utilization of the network capacity. Bee is designed to support network heterogeneity and deal with the flash crowd arrival pattern without sacrificing the dissemination speed. We present experimental results on the performance of Bee in terms of dissemination time and show that its performance can approach lower bound of the maximum dissemination time.
- Published
- 2009
44. Language-model-based detection cascade for efficient classification of image-based spam e-mail
- Author
-
Ming-Syan Chen and Jen-Hao Hsia
- Subjects
Information retrieval ,Contextual image classification ,Probabilistic latent semantic analysis ,Computer science ,business.industry ,Feature extraction ,Pattern recognition ,Filter (signal processing) ,Image spam ,Object detection ,ComputingMethodologies_PATTERNRECOGNITION ,Bag-of-words model ,Overhead (computing) ,Artificial intelligence ,business - Abstract
A new challenge in the spam email detection is the emergence of image spam, which consists in embedding the advertising messages into attached images to defeat the conventional text-based anti-spam technologies. New techniques are needed to filter these spam messages. In this paper, we proposed a prototype system to automatically classify an image directly as being spam or ham. The proposed method extracts latent topics in image to train a binary classifier for detecting spam images, and achieves more promising detection accuracy than conventional antispam approaches. In addition, a detection cascade is proposed to further reduce the computation overhead of the spam filter. Our algorithm is experimentally evaluated under a public spam image dataset, and shown to significantly improve both the detection accuracy and execution efficiency over the baseline approach.
- Published
- 2009
45. AAA: Asynchronous, Adaptive, and Asymmetric Power Management for Mobile Ad Hoc Networks
- Author
-
Chung-Min Chen, Szu-Wei Wu, and Ming-Syan Chen
- Subjects
Power management ,Computer science ,business.industry ,Wireless ad hoc network ,Distributed computing ,ComputerSystemsOrganization_COMPUTER-COMMUNICATIONNETWORKS ,Mobile computing ,Mobile ad hoc network ,Grid ,Network topology ,Asynchronous communication ,Wireless ,business ,Efficient energy use ,Computer network - Abstract
The Quorum-based Power Saving (QPS) protocols have been proposed to increase the energy efficiency of wireless communication. However, it remains challenging to apply existing QPS protocols to the Mobile Ad Hoc Networks (MANETs) as the timers of nodes are usually asynchronous, the incurred delay are expected to be adaptive, and the network topology is asymmetric. In this paper, we propose an Asynchronous, Adaptive, and Asymmetric (AAA) power management protocol that fulfills the unique requirements of MANETs. We present the asymmetric grid quorum system, a generalization of traditional grid-based quorum systems, to ensure the network connectivity. Theoretical analysis is conducted to demonstrate the benefits of AAA over previous arts.
- Published
- 2009
46. On the Energy Efficiency for Heterogeneous Data Broadcasting
- Author
-
Yu-Fen Chen, Ming-Syan Chen, and Chung-Hua Chu
- Subjects
Atomic broadcast ,Tree (data structure) ,Bandwidth allocation ,Computer science ,business.industry ,Distributed computing ,Bandwidth (signal processing) ,Scalability ,Search engine indexing ,Broadcasting ,business ,Database index - Abstract
Data broadcast is an advanced technique to realize large scalability and bandwidth utilization in a mobile computing environment. In the heterogeneous data broadcast, the data size is variant with time in multiple broadcast channels. However, traditional indexing schemes do not consider variant data size to design indexing techniques in the multiple channels. Therefore, the above drawback leads to large power consumption in the heterogeneous data broadcast. In this paper, we remedy the problem of devising an indexing technique to index the data of variant size via the multiple channels. In view of the characteristics of variant data size in the multiple channels, we propose an indexing technique using an index tree to minimize average waiting time and average tuning time. Experimental results show that our approach is able to generate broadcast programs including data indices with high quality and is very efficient in the heterogeneous data broadcast.
- Published
- 2009
47. Incremental SVM Model for Spam Detection on Dynamic Email Social Networks
- Author
-
Chi-Yao Tseng and Ming-Syan Chen
- Subjects
Scheme (programming language) ,Computer science ,InformationSystems_INFORMATIONSYSTEMSAPPLICATIONS ,media_common.quotation_subject ,computer.software_genre ,Electronic mail ,Support vector machine ,Feature (machine learning) ,Data mining ,Email spoofing ,computer ,Reputation ,media_common ,computer.programming_language - Abstract
Recently, the huge number of email spams has caused serious problems in essential email communication. Traditional spam filters aim at analyzing email content to characterize the features that are commonly included in spams. However, it is observed that crafty tricks designed to avoid content-based filters will be endless owing to the economic benefits of sending spams. In view of this situation, there has been much research effort toward doing spam detection based on the reputation of senders rather than what is contained in emails. Motivated by the fact that spammers are prone to have unusual behavior and specific patterns of email communication, exploring email social networks to detect spams has received much attention. Nevertheless, previous works generally suffer from two problems: (1) the system is not robust in diverse environments, and (2) no update scheme is provided to catch the feature changes of evolving networks. In this paper, we propose an incremental support vector machine (SVM) model for spam detection on dynamic email social networks. A complete spam detection system MailNET is devised to better adjust to diverse networks. Several features of each user in the network are extracted to train an SVM model. Moreover, to catch the evolving nature of email communication, we present an incremental update scheme to efficiently re-train an SVM model. We evaluate MailNET on a live data set from a university-scale email server and show that the proposed model is efficient and effective, thus applicable to the real world.
- Published
- 2009
48. Releasing the SVM Classifier with Privacy-Preservation
- Author
-
Ming-Syan Chen and Keng-Pei Lin
- Subjects
Training set ,Structured support vector machine ,Computer science ,business.industry ,Pattern recognition ,Quadratic classifier ,Machine learning ,computer.software_genre ,Support vector machine ,Kernel (linear algebra) ,ComputingMethodologies_PATTERNRECOGNITION ,Ranking SVM ,Margin classifier ,Quadratic programming ,Artificial intelligence ,business ,computer ,Classifier (UML) - Abstract
Support vector machine (SVM) is a widely used tool in classification problem. SVM solves a quadratic optimization problem to decide which instances of training dataset are support vectors, i.e., the necessarily informative instances to form the classifier. The support vectors are intact tuples taken from the training dataset. Releasing the SVM classifier to public use or shipping the SVM classifier to clients will disclose the private content of support vectors, violating the privacy-preservation requirement in some legal or commercial reasons. To the best of our knowledge, there has not been work extending the notion of privacy-preservation to releasing the SVM classifier. In this paper, we propose an approximation approach which post-processes the SVM classifier to protect the private content of support vectors. This approach is designed for the commonly used Gaussian radial basis function kernel. By applying this post-processor on the SVM classifier, the resulted privacy-preserving SVM classifier can be publicly released without exposing the private content of support vectors and is able to provide comparable classification accuracy to the original SVM classifier.
- Published
- 2008
49. A Novel Language-Model-Based Approach for Image Object Mining and Re-ranking
- Author
-
Jen-Hao Hsiao, Chu-Song Chen, and Ming-Syan Chen
- Subjects
Information retrieval ,Computer science ,business.industry ,Relevance feedback ,Query optimization ,computer.software_genre ,Query language ,Query expansion ,Bag-of-words model ,Web query classification ,Visual Word ,Artificial intelligence ,Language model ,business ,Image retrieval ,computer ,Natural language processing ,RDF query language ,computer.programming_language - Abstract
One leading framework for image object mining is the bag-of-words (BOW) approach. The idea is to encode an image as a collection of visual words of the quantized local patches. Objects in the image can then be retrieved through inferring the semantic topics associated with the set of visual words. However, the visual BOW mining framework is apt to suffer from the so-called term-mismatch problem (a.k.a. vocabulary problem). This is caused by the poverty of query information, and consequently becomes an obstacle to deal with synonymy (i.e., different visual words for describing the same object). In this paper, we propose a novel language-model-based approach with pseudo-relevance feedback for addressing the vocabulary problem in visual BOW mining. We employ the pseudo positive images produced in response to the original query as a set of "cues" to gradually refine the query language model. Unlike traditional approaches that only ruggedly append feedback information into the original query, the proposed approach reconstructs the query language model with finer granularities so that the query concepts can be captured more accurately. The proposed approach is experimentally evaluated using two different types of image object databases. Our algorithms are shown to bring significant improvement in the retrieval accuracy over a non-feedback baseline, and achieve better performance than conventional feedback approaches.
- Published
- 2008
50. Visual-word-based duplicate image search with pseudo-relevance feedback
- Author
-
Jen-Hao Hsiao, Chu-Song Chen, and Ming-Syan Chen
- Subjects
business.industry ,Computer science ,ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION ,Process (computing) ,Vector quantization ,Relevance feedback ,Pattern recognition ,Image (mathematics) ,Visualization ,Histogram ,Computer vision ,Visual Word ,Artificial intelligence ,business ,Image retrieval - Abstract
We aim to improve the bag-of-visual-words (BOW) model for near-duplicate image retrieval, by introducing a more fine-grained pseudo-relevance feedback process. The BOW method is based on vector quantization of affine invariant descriptors of image patches. Despite its popularity and simplicity, the retrieval performance of BOW is often unsatisfactory due to the large and diverse variations of near-duplicate images. We thus propose an information-theoretic feedback framework that employs available cues in the search result to find more relevant duplicate images which are hard to retrieve by using conventional BOW approaches. Our algorithm is experimentally evaluated under a severely attacked image database, and shown to significantly improve the retrieval accuracy over a non-feedback baseline.
- Published
- 2008
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.