6432483
Evaluating GML support for spatial databases
This work presents a study on Geography Markup Language (GML), the issues that arise from using GML for spatial databases and solutions that have been proposed. We concentrate on three aspects of GML, including storage, parsing, and querying. GML is an XML encoding for storing geographic data. It has been developed by the OpenGIS as a medium for uniform geographic data storage and exchange among diverse applications. The underlying concepts of XML therefore can also be applied to GML data. This results in both advantages and disadvantages, which are discussed In the work. GML is a comparatively new language in the field of geographic information systems and still in its developmental stage. Most of the data processing techniques need to be further developed in order for GML to be an efficient medium for geographic data storage and processing.
18415730
Multivariate Spatial Outlier Detection
A spatial outlier is a spatially referenced object whose non-spatial attribute values are significantly different from the values of its neighborhood. Identification of spatial outliers can lead to the discovery of unexpected, interesting, and useful spatial patterns for further analysis. Previous work in spatial outlier detection focuses on detecting spatial outliers with a single attribute. In the paper, we propose two approaches to discover spatial outliers with multiple attributes. We formulate the multi-attribute spatial outlier detection problem in a general way, provide two effective detection algorithms, and analyze their computation complexity. In addition, using a real-world census data, we demonstrate that our approaches can effectively identify local abnormality in large spatial data sets.
429860
Spatial Weighted Outlier Detection
Spatial outliers are the spatial objects with distinct features from their surrounding neighbors. Detection of spatial outliers helps reveal valuable information from large spatial data sets. In many real applications, spatial objects can not be simply abstracted as isolated points. They have different boundary, size, volume, and location. These spatial properties affect the impact of a spatial object on its neighbors and should be taken into consideration. In this paper, we propose two spatial outlier detection methods which integrate the impact of spatial properties to the outlierness measurement. Experimental results on a real data set demonstrate the effectiveness of the proposed algorithms.
8614779
AITVS: Advanced Interactive Traffic Visualization System
Transportation and the highway network form the backbone of the total public infrastructure system. As such, planning and monitoring for an effective transportation system is crucial in the building and maintenance of a region’s economy and safety. However, demand for road travel continues to expand as population increases (particularly in the metropolitan areas) while new constructions have not kept pace. According to the Federal Highway Administration, it is forecasted that the volume of freight movement alone is to nearly double by 2020 [1]. Congestion and looming gridlock crises seriously threaten any region’s mobility, safety and economic vitality. A crucial component in addressing these concerns is the development of specific technologies to monitor, model, and optimize traffic flow.
2968463
Making Data Mining Models Useful to Model Non-paying Customers of Exchange Carriers
Due to both limitations of technologies and the nature of the problems, data mining may not be able to solve a problem completely in a way as one wishes. When this happens, we need to first understand the actual need of business, characteristic of available partial solution, and then make compromises between the technology solution and business needs. A majority of the papers published in data mining conferences and journals seem to concentrate only on the success side of the story. In this paper, we discuss our experiences and the complete process from near failure to success when applying inductive learning techniques to predict non-paying customers of competitive local exchange carriers (CLEC’s), currently at 20%. Experiments with a number of stateof-the-art methods and algorithms found that most customers were labeled as paying on time. Cost-sensitive learning is not possible since the target company cannot define a cost-model. Finally, after discussing with the billing department, a compromised but still useful solution is to predict the probability that someone will default. The billing team can use the predicted score to prioritize collection efforts as well as to predict cash flow. We have found that two randomized decision tree ensemble methods (Fan’s random decision tree and a probabilistic extension of Breiman’s random forest) are consistently more accurate in posterior probability estimation than single decision tree based probability calibration methods. The software, both Fan’s RDT and probabilistic extension of random forest, as well as a longer version of this paper will be made available by the contacting author.
1234945
Spatial Databases - Accomplishments and Research Needs
Spatial databases, addressing the growing data management and analysis needs of spatial applications such as geographic information systems, have been an active area of research for more than two decades. This research has produced a taxonomy of models for space, spatial data types and operators, spatial query languages and processing strategies, as well as spatial indexes and clustering techniques. However, more research is needed to improve support for network and field data, as well as query processing (e.g., cost models, bulk load). Another important need is to apply spatial data management accomplishments to newer applications, such as data warehouses and multimedia information systems. The objective of this paper is to identify recent accomplishments and associated research needs of the near term.
7786870
Construction of a hierarchical classifier schema using a combination of text-based and image-based approaches
Web document hierarchical classification approaches often rely on textual features alone even though web pages include multimedia data. We propose a new hierarchical integrated web classification approach that combines image-based and text-based approaches. Instead of using a flat classifier to combine text and image classification, we perform classification on a hierarchy differently on different levels of the tree, using text for branches and images only at leaves. The results of our experiments show that the use of the hierarchical structure improved web document classification performance significantly.
11606897
Malicious ICMP Tunneling: Defense against the Vulnerability
This paper presents a systematic solution to the problem of using ICMP tunneling for covert channel. ICMP is not multiplexed via port numbers and the data part of the ICMP packet provides considerable bandwidth for malicious covert channels. These factors make it an integral part of many malicious software like remote access and denial of service attack tools. These tools use ICMP to establish covert communication channels. In this paper a stateless model is proposed to prevent ICMP tunneling. A Linux kernel module was implemented to demonstrate the proposed stateless solution. The module enforces a fixed payload policy for ICMP packets and virtually eliminates ICMP tunneling which arises due to the data carrying capability of ICMP. The performance impact on end hosts and routers due to the stateless monitoring model is described.
7343346
Solving the Weighted Efficient Edge Domination Problem on Bipartite Permutation Graphs
Abstract Given a simple graph G = (V,E), an edge (u, v)ϵ E is said to dominate itself and any edge (u,x) or (v,x), where xϵ V. A subset D⊂-E is called an efficient edge dominating set of G if all edges in E are dominated by exactly one edge of D. The efficient edge domination problem is to find an efficient edge dominating set of minimum size in G. Suppose that each edge eϵ E is associated with a real number w(e), called the weight of e. The weighted efficient edge domination problem is to calculate an efficient edge dominating set D of G such that the weight w(D) of D is minimum, where w(D) = ∑{w(e)¦eϵD} . In this paper, we show that the problem of determining whether G has an efficient edge dominating set is NP-complete when G is restricted to a bipartite graph. Consequently, the decision problem of efficient (vertex) domination remains NP-complete for the line graphs of bipartite graphs. Moreover, we present a linear time algorithm to solve the weighted efficient edge domination problem on bipartite permutation graphs, which form a subclass of bipartite graphs, using the technique of dynamic programming.
1071507
On greedy geographic routing algorithms in sensing-covered networks
Greedy geographic routing is attractive in wireless sensor networks due to its efficiency and scalability. However, greedy geographic routing may incur long routing paths or even fail due to routing voids on random network topologies. We study greedy geographic routing in an important class of wireless sensor networks that provide sensing coverage over a geographic area (e.g., surveillance or object tracking systems). Our geometric analysis and simulation results demonstrate that existing greedy geographic routing algorithms can successfully find short routing paths based on local states in sensing-covered networks. In particular, we derive theoretical upper bounds on the network dilation of sensing-covered networks under greedy geographic routing algorithms. Furthermore, we propose a new greedy geographic routing algorithm called Bounded Voronoi Greedy Forwarding (BVGF) that allows sensing-covered networks to achieve an asymptotic network dilation lower than 4:62 as long as the communication range is at least twice the sensing range. Our results show that simple greedy geographic routing is an effective routing scheme in many sensing-covered networks.
16028942
On monotone planar circuits
In this paper we show several results about monotone planar circuits. We show that monotone planar circuits of bounded width, with access to negated input variables, compute exactly the functions in non-uniform AC/sup 0/. This provides a striking contrast to the non-planar case, where exactly NC/sup 1/ is computed. We show that the circuit value problem for monotone planar circuits, with inputs on the outerface only, can be solved in LOGDCFL/spl sube/SC, improving a LOGCFL upper bound due to Dymond and Cook. We show that for monotone planar circuits, with inputs on the outerface only, excessive depth compared to width is useless; any function computed by a monotone planar circuit of width w with inputs on the outerface can be computed by a monotone planar circuit of width O(w) and depth w/sup O(1)/. Finally, we show that monotone planar read-once circuits, with inputs on the outerface only, can be efficiently learned using membership queries.