Frequent subgraph mining is a core graph operation used in many domains. Most existing techniques target static graphs. However, modern applications utilize large evolving graphs. Mining these graphs using existing techniques is infeasible because of the high computational cost. We propose IncGM+, a fast incremental approach for frequent subgraph mining on large evolving graphs. We adapt the notion of "fringe" to the graph context, that is, the set of subgraphs on the border between frequent and infrequent subgraphs. IncGM+ maintains fringe subgraphs and exploits them to prune the search space. To boost efficiency, IncGM+ stores a number of selected embeddings to avoid redundant expensive subgraph isomorphism operations. Moreover, the proposed system supports batch updates. Our results confirm that IncGM+ outperforms existing methods, scales to larger graphs and consumes less memory.

Frequent subgraph mining is a core graph operation used in many domains, such as graph data management and knowledge exploration, bioinformatics, and security. Most existing techniques target static graphs. However, modern applications, such as social networks, utilize large evolving graphs. Mining these graphs using existing techniques is infeasible, due to the high computational cost. In this paper, we propose IncGM+, a fast incremental approach for continuous frequent subgraph mining on a single large evolving graph. We adapt the notion of “fringe” to the graph context, that is the set of subgraphs on the border between frequent and infrequent subgraphs. IncGM+ maintains fringe subgraphs and exploits them to prune the search space. To boost the efficiency, we propose an efficient index structure to maintain selected embeddings with minimal memory overhead. These embeddings are utilized to avoid redundant expensive subgraph isomorphism operations. Moreover, the proposed system supports batch updates. Using large real-world graphs, we experimentally verify that IncGM+ outperforms existing methods by up to three orders of magnitude, scales to much larger graphs and consumes less memory.

Graph stores are becoming increasingly popular among NOSQL applications seeking flexibility and heterogeneity in managing linked data. Conceptually and in practice, applications ranging from social networks, knowledge representations to Internet of things benefit from graph data stores built on a combination of relational and non-relational technologies aimed at desired performance characteristics. The most common data access pattern in querying graph stores is to traverse from a node to its neighboring nodes. This paper studies the impact of such traversal pattern to common data caching policies in a partitioned data environment where a big graph is distributed across servers in a cluster. We propose and evaluate a new graph aware caching policy designed to keep and evict nodes, edges and their metadata optimized for query traversal pattern. The algorithm distinguishes the topology of the graph as well as the latency of access to the graph nodes and neighbors. We implemented graph aware caching on a distributed data store Apache HBase in the Hadoop family. Performance evaluations showed up to 15x speedup on the benchmark datasets preferring our new graph aware policy over non-aware policies. We also show how to improve the performance of existing caching algorithms for distributed graphs by exploiting the topology information.

In graph theory, k-core is a key metric used to identify subgraphs of high cohesion, also known as the `dense' regions of a graph. As the real world graphs such as social network graphs grow in size, the contents get richer and the topologies change dynamically, we are challenged not only to materialize k-core subgraphs for one time but also to maintain them in order to keep up with continuous updates. Adding to the challenge is that real world data sets are outgrowing the capacity of a single server and its main memory. These challenges inspired us to propose a new set of distributed algorithms for k-core view construction and maintenance on a horizontally scaling storage and computing platform. Our algorithms execute against the partitioned graph data in parallel and take advantage of k-core properties to aggressively prune unnecessary computation. Experimental evaluation results demonstrated orders of magnitude speedup and advantages of maintaining k-core incrementally and in batch windows over complete reconstruction. Our algorithms thus enable practitioners to create and maintain many k-core views on different topics in rich social network content simultaneously.

Big, rich graph data is increasingly captured through the interactions among people (email, messaging, social media), objects (location/map, server/network, product/catalog) and their relations. Graph data analytics, however, poses several intrinsic challenges that are ill fitted to the popular Map Reduce programming model. This paper presents System G, a graph data management system that supports rich graph data, accepts online updates, complies with Hadoop, and runs efficiently by minimizing redundant data shuffling. These desirable capabilities are built on top of Apache HBase for scalability, updatability and compatibility. This paper introduces several exemplary target graph queries and global feature algorithms implemented using the newly available HBase Coprocessors. These graph algorithmic coprocessors execute on the server side directly on graph data stored locally and only communicates with remote servers for the dynamic algorithmic state, which is typically a small fraction of the raw data. Performance evaluation on real-world rich graph datasets demonstrated significant improvement over traditional Hadoop implementation, as prior works observed in their no-graph-shuffling solutions. Our work stands out at achieving the same or better performance without introducing incompatibility or scalability limitations.

Reading and perceiving complex SQL queries has been a time consuming task in traditional database applications for decades. When it comes to decision support systems with automatically generated and sometimes highly nested SQL queries, human understanding or tuning of these workloads becomes even more challenging. This demonstration explores visualization methods to represent queries as graphs. We developed the QueryScope tool to help visualize and understand critical elements of a query, thereby cutting down the learning curve. We show how the tool allows the user to drill down on particular queries or to find similarly structured queries that may exhibit similar tuning opportunities. The queries shown in the demonstration are taken from real tuning engagements.

In response to the widespread use of the XML format for document representation and message exchange, major database vendors support XML in terms of persistence, querying and indexing. Specifically, the recently released IBM DB2 9 (for Linux, Unix and Windows) is a hybrid data server with optimized management of both XML and relational data. With the new option of storing and querying XML in a relational DBMS, data architects face the the decision of what portion of their data to persist as XML and what portion as relational data. This problem has not been addressed yet and represents a serious need in the industry. Hence, this paper describes ReXSA, a schema advisor tool that is being prototyped for IBM DB2 9. ReXSA proposes candidate database schemas given an information model of the enterprise data. It has the advantage of considering qualitative properties of the information model such as reuse, evolution and performance profiles for deciding how to persist the data. Finally, we show the viability and practicality of ReXSA by applying it to custom and real usecases.

The wide spread of databases for managing structured data, compounded with the expanded reach of the Internet, has brought forward interesting data retrieval and analysis scenarios to RDBMS. In such settings, queries often take the form of k-constrained optimization, with a Boolean constraint and a numeric optimization expression as the goal function, retrieving only the top-k tuples. This paper proposes the concept of supporting such queries, as their nature implies, by a functional optimization machinery over the search space of multiple indices. To realize this concept, we combine the dual perspectives of discrete state search (from the view of indices) and continuous function optimization (from the view of goal functions). We present, as the marriage of the two perspectives, the OPT* framework, which encodes k-constrained optimization as an A* search over the composite space of multiple indices, driven by functional optimization for providing tight heuristics. By processing queries as optimization, OPT* significantly outperforms baseline approaches, with up to 3 orders of magnitude margins.

Assume a database storing N objects with d numerical attributes or feature values. All objects in the database can be assigned an overall score that is derived from their single feature values (and the feature values of a user-defined query). The problem considered here is then to efficiently retrieve the k objects with minimum (or maximum) overall score. The well-known threshold algorithm (TA) was proposed as a solution to this problem. TA views the database as a set of d sorted lists storing the feature values. Even though TA is optimal with regard to the number of accesses, its overall access cost can be high since, in practice, some list accesses may be more expensive than others. We therefore propose to make TA access cost aware by choosing the next list to access such that the overall cost is minimized. Our experimental results show that this overall cost is close to the optimal cost and significantly lower than the cost of prior approaches.

Health activity monitoring (HAM) has received increasing attention due to the rapid advances of both hardware and software technologies and strong environmental and public health needs. In this paper, we describe the architecture and implementation of the Epi-SPIRE prototype, which is a novel health activity monitoring system that generates alerts from environmental, behavioral, and public health data sources. A model-based approach is used to develop disease and behavior models from multi-modal heterogeneous data sources. Furthermore, a model-based indexing technique has been developed to speed up the data access and retrieval. This system has been successfully applied to various genuine and simulated diseases outbreaks scenarios'.

Economics research has long recognized that bundling enables savings in production and transaction costs, promotes complementary among the bundle components and sorts consumers according to their valuations. Sellers employ market analysis and intelligence to extract the most surplus. In the age of electronic commerce with low product information access cost, buyers can take advantage of the benefits of bundling by performing dynamic composition of goods from multiple companies offering heterogeneous products and services. These goods, with the proper mix of sources and quantity, may offer additional discounts and benefits, which would not have risen should purchase decisions were made independently. A prominent example is packaged travel, which often involves air, hotel and car rentals. An optimal travel package search not only takes advantage of the lowest available prices of air, hotel and car rental individually but also exploits various discounts through business partnerships between service providers.Today's database infrastructure to support the search of dynamically bundled goods, however, is insufficient. The complex search operations involving cross join of many product categories with hundreds or thousands of offerings can be formulated as SQL queries. But executing these queries in a traditional database is inefficient. This paper proposes an I/O conscious, dynamic programming based algorithm for bundle search. The proposed algorithm finds the top-K combinations of goods abstracted by a linear relationship graph. Experimental results indicate that the proposed algorithm achieves more than two orders of magnitude speedup over cross join, and it is more than an order of-magnitude faster than the simple dynamic programming solution. The performance gap further widens as the number of product categories and the number of offerings within each category increase. This paper characterizes the computational and I/O complexity of the proposed algorithm and suggests extensions to search bundles with more complex relationships.

Forestry management requires careful and intensive planning efforts to ensure optimal yield, ecological stability, and regulatory compliance. We describe a method of identifying wetlands and producing maps of their extent from commonly available, remotely-sensed imagery. This method provides a large labor savings over both field inspections and manual photo inspections. The enhanced accuracy translates into better timber harvest planning and better conservation of the wetlands.

In this paper, we describe a novel content-based retrieval application which permits astrophysicists to search large image sequence archives for solar phenomenon, such as solar flares, based on the spatio-temporal behavior of the solar phenomenon. Specifically, images are preprocessed to identify bright and dark spots based on their relative intensity with respect to their neighboring regions. Temporally persistent objects are then extracted from the collection of spots, and their spatio-temporal behavior represented as intensity and size time series. Users define a query in terms of a model of spatio-temporal behaviors through a Web-based interface. The stored intensity and size time series are searched, and series segments that match the specified specified spatio-temporal behavior are returned. The benchmark results based on 2500 satellite images show that the proposed methodology demonstrated better than 85% accuracy on a solar phenomenon previously identified by astrophysicists.

We describe methods for content-based searching of images using MPEG-7 descriptions. The search problems range from matching of images based on global features to matching based on multiple objects, multiple features, and structural or semantic constraints and relationships. We provide a taxonomy of the different searching and matching problems and present query methods for each type. Furthermore, we examine methods for computing approximate answers for some of the searching problems in order to allow a trade-off of query response time and precision.

As the earth science data and information products begin to proliferate due to the increased number of earth observing instruments and platforms, it has become increasingly difficult for the end consumer to leverage the wide variety of available earth science data and information products. In this paper, we propose an innovative infrastructure to enable the consumers to locate and tradeoff possible alternative earth science data and information sources in an electronic marketplace setting. Specifically, this architecture provides mechanisms to annotate the requests and offerings of the data and information products, to decompose the concepts of the requests and offerings to facilitate the matchmaking and inferencing. Based on the knowledge models developed for each application domain and science discipline, the matchmaking mechanism will be able to fuse and combine multiple alternative data and information sources so that the quality of the results can be maximized while the cost for data acquisition is minimizing.

As Internet information portals become prevalent for both Internet and Intranet, most existing Internet Application Server architectures are not scalable to support the large amount of personalization, customization and content adaptation required. We propose a framework to capture the information and content dissemination process. Furthermore, we propose a methodology to map this process to a distributed application server environment. By fully exploiting the intersections of user preference at multiple content processing stages, this new framework enables high hit ratio on processing, storage, and transmission of content and thus scales well to support a large number of clients.

This paper describes the Onion technique, a special indexing structure for linear optimization queries. Linear optimization queries ask for top-N records subject to the maximization or minimization of linearly weighted sum of record attribute values. Such query appears in many applications employing linear models and is an effective way to summarize representative cases, such as the top-50 ranked colleges. The Onion indexing is based on a geometric property of convex hull, which guarantees that the optimal value can always be found at one or more of its vertices. The Onion indexing makes use of this property to construct convex hulls in layers with outer layers enclosing inner layers geometrically. A data record is indexed by its layer number or equivalently its depth in the layered convex hull. Queries with linear weightings issued at run time are evaluated from the outmost layer inwards. We show experimentally that the Onion indexing achieves orders of magnitude speedup against sequential linear scan when N is small compared to the cardinality of the set. The Onion technique also enables progressive retrieval, which processes and returns ranked results in a progressive manner. Furthermore, the proposed indexing can be extended into a hierarchical organization of data to accommodate both global and local queries.

Multimedia traffic sources with tight latency constraint, arising in sessions such as data query, image and video transmissions, can be very bursty and are inefficient to be serviced with a dedicated high-speed link. On wireline networks, bursty traffic is statistically multiplexed to fully utilize the link capacity. In light of recent proposals for wideband CDMA (WCDMA) to service multimedia data, there is a similar need to develop wireless network architectures with flexible bandwidth allocation to facilitate statistical multiplexing. To address this issue, we compared the throughput performance of two promising WCDMA configurations, high speed CDMA (HS-CDMA) and multi-code CDMA (MC-CDMA). HS-CDMA assigns each user a single code with small spreading gain to enable a high transmission rate when it is needed. In contrast, MC-CDMA employs codes with a large spreading gain but permits a user to acquire more than one code. As expected, the throughput of a configuration depends on the receiver structure as well as the operation scenarios like power and SNR constraints. When matched filter receivers are applied, HS-CDMA fares better in most occasions. When multi-user receivers are used, both configurations deliver the same throughput except the situation when the total power is bounded.

Digital video coding has traditionally used frame-by-frame synchronous reconstruction. The transport must then be delay-jitter-free, forcing the modern integrated service packet network such as the Internet to operate in an inefficient "circuit emulation" mode. This mode results in a jitter-free delay representative of the worst-case network delay, which is problematic for delay-sensitive interactive applications. In response, we have proposed and demonstrated a "delay cognizant" model of video coding (DCVC) that operates in an asynchronous reconstruction mode. DCVC minimizes the perceptual delay observed by the user, and still achieves good quality and high compression. Furthermore, the feasibility of asynchronous reconstruction is evidenced by vision science studies of spatiotemporal masking in human visual systems at the temporal edges of video.

The widely popular World Wide Web along with advances in desktop computers has brought the world into a new age of computing and communications. Low bit-rate video applications across the Internet are quickly emerging. The ITU-T H.263 standard was designed for low bit-rate video conferencing across phone lines and is an ideal candidate to be extended for Internet video applications. This paper focuses on the error robustness issue of compressed H.263 video streams when transmitted over the Internet. The traditional approach of inserting intra-coded frames increases the error resilience at the expense of bursty output traffic, lower picture quality, and uneven frame dropping. By extending the macroblock force update feature of the H.263 standard, we developed a scheme that complies with the standard and increases the robustness of the video stream. This macroblock updating scheme analyzes the temporal dependencies of macroblocks in successive frames and selectively updates the macroblocks which have the most impact on later frames. The performance evaluation of the proposed technique demonstrates that it achieves a good balance between error recovery speeds and video quality.